Álgebra lineal en un idioma

Question

Dejemos que $L$ sea una lengua cuyo alfabeto tiene $n$ cartas. Tenemos una lista de diccionario $k$ pares de palabras equivalentes, es decir $A_i \sim B_i$ pour $1 \leq i \leq k$ , donde $A_i$ y $B_i$ son palabras distintas. Sabemos que se puede reducir cualquier palabra de la lengua a una palabra de longitud como máximo $100$ , sustituyendo palabras similares (del listado del diccionario).

Demostrar que $k \geq n$ .

Answer 1

Dejemos que $a_i,b_i$ sean vectores en $\mathbb{Z}^n$ expresando el número de letras de cada tipo en $A_i,B_i$ . Si $k < n$ entonces podemos encontrar algún vector entero no nulo $v$ (sin divisor común) que es ortogonal a todos los $a_i - b_i$ . Esto significa que el producto interno con $v$ es invariable bajo las sustituciones $A_i \leftrightarrow B_i$ .

Ahora calcule el producto interno de $v$ con los histogramas de todas las palabras de longitud máxima $100$ y elegir algún número $M$ que no aparece en este conjunto de productos internos. Construir alguna palabra $w$ con un histograma cuyo producto interno con $v$ es $M$ (aquí utilizamos el hecho de que $v$ no tiene divisor común). La palabra $w$ no puede reducirse a $100$ letras o menos.

Obsérvese que siempre podemos encontrar tal $w$ que es una potencia de un solo carácter. Así que la intuición de la respuesta anterior era correcta.