Welcome to Thunderdome

Last week, you were introduced to an online game, Guess My Word, in which you tried to guess a secret word by typing in other words. After each guess, you were told whether the secret word was alphabetically before or after your guess. The game stopped and congratulated you once you had guessed the secret word.

The secret word was randomly chosen from a dictionary with exactly 267,751 entries. If you had this dictionary memorized and played the game as efficiently as possible, how many guesses should you have expected to make to uncover the secret word?

Most solvers recognized that the most efficient strategy was a binary search, where you first guessed the middle word in the dictionary. If the secret word came later, you then guessed the middle word in the second half of the dictionary. But if the secret word came earlier, you guessed the middle word in the first half of the dictionary. With each guess, you narrowed the possibilities by approximately half, and there was also a chance that the guess itself was the secret word.

The sequence of guesses could therefore be structured as a complete binary tree whose top node was your first guess (the exact middle word in the dictionary). If the secret word came earlier in the dictionary, you moved to the right; if the secret word came later in the dictionary, you moved to the left. Eventually, you’d find the secret word.

Now that you had the optimal guessing strategy, all that was left was calculating the average number of guesses. In your binary tree, one word — the middle word in the dictionary — would be guessed on the very first attempt. Two words required two guesses, four words required three guesses, eight words required four guesses, 16 words required five guesses, and so on. For each additional guess, there were twice as many words.

It turned out that the number of words in the dictionary, 267,751, was 1 + 21 + 22 + 23 + … + 216 + 217 + 5608. And each term in the sum required one more guess than the term before it. To find the average number of guesses, you had to divide each of these terms by 267,751 and then multiply by the corresponding number of guesses. In the end, the average was approximately 17.042 guesses.

GORDON wrote: I see.

I suppose this isn't really a question of skill... just read books now and then, and have a decent vocabulary. Then get lucky with your guesses.

Leisher wrote: 17 on hard too because I tricked myself into thinking the target start letter must be followed by a vowel.

Leisher wrote: They got me today. Fuckers. It genuinely made me laugh.

GORDON wrote: 10.5.2020

easy - 10 guesses, <2 minutes
hard - 19, 8 minutes

Leisher wrote: 10/6/2020
13 on easy. 8 were in the letter.

22 for the hard one. 18 of them were in the letter...

11 of those had the first 3 or 4 letters...

Leisher wrote: 12 and 13 today.