For each letter in the English alphabet, William assigns an English word which contains that letter. His first document consists only of the word assigned to the letter $A$. In each subsequent document, he replaces each letter of the preceding document by its assigned word. The fortieth document begins with “Till whatsoever star that guides my moving.” Prove that this sentence reappears later in this document.
Problem
Source: Tournament of Towns 2007 - Fall - Junior A-Level - P7
Tags: combinatorics unsolved, combinatorics
gmail.com
31.03.2019 07:02
Does anyone have a solution to this (currently) unsolved problem?
AforApple
31.03.2019 19:26
Lemma: The first letter of document $38$ appears later in the document. Proof: Assume the contrary. From here, we know that the first word of document $38$ is unique because it is the only word that has this particular letter. Then going backwards tells us that the first letter of document $37$ is unique because it determines first word of document $38$. Now we know that the first word of document $37$ is is unique, so the first letter of document $36$ is unique. We can continue this logic down all the way down to document $1$. Now we know all the documents from $1$ to $38$ have a unique first letter. It is clear that the word assigned to the letter A cannot start with A, otherwise all documents will start with A, and "Till" does not start with A , so assume WLOG it's B. This means that word assigned to the letter A has both A and B in it, and since A is not at the beginning of document $1$, we know both A and B appear in document $2$, neither of which are at the beginning. This means that the first letter of document $2$ cannot be A or B, so let it be C. We know that in document $2$ contains A and B not at the beginning, and since the letter B is assigned to a word with the letter C, we know that document $3$ has the letters A, B, and C, none of which are at the beginning. Document $3$ cannot start with A, B, or C, so let it start with D. Using inductive reasoning, it is clear that every document from $1$ to $38$ must start with a different letter. However, this is a contradiction because there are only $26$ letters in the alphabet, so the lemma is true. Now for the main problem. Consider this first word of document $39$, which has to start with T, I, or L. Of the first seven words in document $40$, only "Till" and "that" have this property. But it can't be "Till" because "whatsoever" doesn't have an I, and it can't be "that" because the letter T would be assigned to two different words, namely "Till" and "that". This means that the first word of document $39$ is not any of the first seven words of document $40$. And if it was seven letters or shorter, then we can't assign a letter to this word because the first letter was already assigned to "Till", the second letter was already assigned to "whatsoever" and so on up to the seventh letter, which was already assigned to "moving". This is a contradiction because we know that this word is not any of these words, so this word is at least eight letters long, which was determined by the first letter of document $38$. Finally, since the first letter of document $38$ appears later in the document, the first eight letters of document $39$ appear in order later in the document, and the first eight words of document $40$ appear in order later in the document (Which was actually one word more than what they wanted us to prove) $\blacksquare$ Special thanks to gmail.com for bringing this problem to my attention.