2
$\begingroup$

Let $L$ be a language whose alphabet has $n$ letters. We have a dictionary listing $k$ equivalent pairs of words, i.e. $A_i \sim B_i$ for $1 \leq i \leq k$, where $A_i$ and $B_i$ are distinct words. We know that one can reduce any word from the language to a word of length at most $100$, by replacing similar words (from the listing of the dictionary).

Prove that $k \geq n$.

  • 0
    From OP's comment to a deleted answer: "I th$i$nk there isn't any short proof without linear algebra, and there exists a short one with that because it's the first exercise of a paper for introducing linear algebra. (That paper just has some problems and nothing more.)"2011-04-04

1 Answers 1

5

Let $a_i,b_i$ be vectors in $\mathbb{Z}^n$ expressing the number of letters of each type in $A_i,B_i$. If $k < n$ then we can find some non-zero integer vector $v$ (with no common divisor) which is orthogonal to all $a_i - b_i$. That means that the inner product with $v$ is invariant under the substitutions $A_i \leftrightarrow B_i$.

Now compute the inner product of $v$ with the histograms of all words of length at most $100$, and choose some number $M$ not appearing in this set of inner products. Construct some word $w$ with histogram whose inner product with $v$ is $M$ (here we use the fact that $v$ has no common divisor). The word $w$ cannot be reduced to $100$ letters or less.

Note that we can always find such a $w$ which is a power of a single character. So the intuition behind the earlier answer was correct.

  • 0
    Thanks for your solution !2011-04-04