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$.

  • 2
    $\begingroup$ Maybe I'm missing something obvious, but what does this have to do with linear algebra? $\endgroup$ – Jason DeVito Apr 3 '11 at 20:51
  • $\begingroup$ Could you write your solution please ? $\endgroup$ – Mahan Apr 3 '11 at 20:55
  • $\begingroup$ I deleted my answer, as being wrong, but I think the idea of supposing that $k < n$ and then constructing a word with length greater than 100 which can't be reduced using the dictionary could work. $\endgroup$ – alejopelaez Apr 3 '11 at 21:40
  • $\begingroup$ I`ll think on your idea , but now I just want to know , how we can translate the problem into linear algebra form ! Thanks in advance for your comments . $\endgroup$ – Mahan Apr 3 '11 at 21:44
  • $\begingroup$ From OP's comment to a deleted answer: "I think 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.)" $\endgroup$ – Yuval Filmus Apr 4 '11 at 1:47

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.

  • $\begingroup$ Thanks for your solution ! $\endgroup$ – Mahan Apr 4 '11 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.