Este es un ejercicio de Introducción a los Idiomas y la Teoría de la Computación, de John Martin.
Supongamos que $L$ es un lenguaje sobre $ \Sigma $ y $x_1, x_2, ... , x_n$ son cuerdas que son de pareja $L$ -distinguible. ¿Cuántas distintivas son necesarias para distinguir entre los $x_i$ 's? En En otras palabras, ¿cuál es el número más pequeño $k$ de tal manera que para algún conjunto $\{z_1, z_2, ...,z_k\}$ dos distintos $x_i$ son distinguidos, en relación con $L$ por algunos $z_l$ ? Demuestra tu respuesta.
El libro da una pista, que dice lo siguiente:
He aquí una forma de pensar sobre la cuestión que puede hacerla más fácil. Piensa en la $x_i$ como puntos en un trozo de papel, y piensa en el $z_l$ como latas de pintura, cada una $z_l$ representando un color primario diferente. Diciendo que $z_l$ distingue $x_i$ y $x_j$ significa que uno de esos dos puntos está coloreado con ese color primario y el otro no. Permitimos que a un solo punto se le aplique más de un color primario, y asumimos que dos combinaciones distintas de colores primarios producen diferentes colores resultantes. Entonces la pregunta es, ¿cuántos colores primarios diferentes se necesitan para colorear los puntos de modo que no haya dos puntos que terminen con el mismo color?
Aquí está mi respuesta a la pregunta sobre la coloración
Solución : Coloración $n$ para que no haya dos puntos que terminen del mismo color requiere $ \lceil \log_2 n \rceil $ colores primarios.
Primero enumere los puntos usando representaciones binarias, y deje que cada dígito corresponda a un color primario. Luego identificamos la combinación de colores para un punto dado como todos los colores primarios cuyo dígito correspondiente es 1. Cada uno de los puntos tiene una representación única, por lo que cada combinación de colores primarios será única.
Mi pregunta específica es: ¿puede probar que $ \lceil \log_2 n \rceil $ es suficiente? Que ningún valor inferior de $k$ funcionará es fácil: entonces el conjunto de energía de la $z_l$ tendrá una magnitud menor que $n$ así que por el Principio del Agujero de Paloma, habrá dos cuerdas que no se distinguirán ninguna de las $z_l$ 's. Así que $k \ge \log_2 n$ . Un límite superior fácil es $ \binom {n}{2}$ . Ya que las cuerdas son de dos en dos $L$ -distinguible, podemos elegir una cadena para un subconjunto de la $x_i$ de la talla dos.
Pero es $ \lceil \log_2 n \rceil $ ¿Realmente es todo lo que necesitas? Estoy buscando una prueba formal de que este es el caso, o un ejemplo de un lenguaje $L$ y $n$ por parejas $L$ -cadenas distinguibles para las que no existen $ \lceil \log_2 n \rceil $ cuerdas que distinguen las $x_i$ .
