Friday, February 27, 2009

Self-referential sentence

Here's one funny problem back from 1998 summer training camp for Russian IOI team hopefuls. Construct a sentence of form:

This sentence has one hundred and ninety letters, twenty one word, twelve commas, one dot, seventy five spaces, fifteen quotes, one word "This", seven words "word" and two words "twenty".

Which is completely true and has nothing missing. At the camp, there were only so many participants, so the results were checked by hand with help of a computer program, and thus some leeway was allowed in interpreting the problem statement. However, the problem doesn't suffer if we fix what's needed precisely: the sentence should be like the above but obviously with different numbers (but still spelled in "canonical" English way) and all words listed with correct amounts in case-sensitive way, with no word from the sentence missing.

I couldn't solve it back in 1998, and the solution looked like a very innovative idea to me at that time. It doesn't anymore, but I hope some of you will enjoy thinking about it. Any suggestions on the approach? Any solutions? :)

// I know that this is a well-known idea, and Googling the title of this post reveals a lot of examples and solutions :)

// To give you some context: here's me at the similar camp a year later in 1999:


  1. Man! how do you think up solutions so fast... do you work out a lot on paper or the solution just comes to you when you see the problem...
    (take the case of an SRM easy or medium)

  2. Have you ever tried your hand on Np-complete problems? take a day.. if you cant solve it .. more strong evidence that p!=np :)

  3. This sentence has four e's.


  4. Can you please give some hints?

  5. Well, the only hint I can think of without revealing the solution is that this is not a pure math problem; you're allowed to use computer, write some code, run some experiments and so on.

  6. This sentence has thirty-one letters. :D