Twenty Questions: some background

I occasionally read the newsgroup rec.puzzles, and on one such occasion I ran across a puzzle called the Self-referential aptitude test, by Jim Propp. It had a bunch of intertwined multiple-choice questions such as, "The number of questions with the answer A is...", or "The answer to this question is the same as the answer to question...".

The S.R.A.T. was an amusing puzzle, and I had fun solving it, but I was left thinking, if I were going to construct a puzzle like that, it would have this feature... So I constructed my puzzle, which I call "Twenty Questions". The last question illustrates the feature I had in mind:

20. The maximum score that can be achieved on this test is:
(A) 18
(B) 19
(C) 20
(D) indeterminate
(E) achievable only by getting this question wrong
I managed to find a friend willing to struggle through it in order to prove it could be solved by a method other than exhaustive search of all possible answers. (Thanks, Jim!) I also wrote a computer program to doublecheck that my solution was correct, and that there were no other possible solutions.

I posted the puzzle on rec.puzzles, but got absolutely no response from the readers there, just as I got no response other than dismay from the other friends I showed it to, so for a long time I had trouble finding an audience for this puzzle. Then one day another friend (thanks, Pavel!) was headed for a gathering of puzzle enthusiasts, and though the gathering was primarily focused on physically manipulated puzzles, I gave him a copy of Twenty Questions to share as he saw fit. One of the people who saw it there was Ed Pegg, who runs the excellent site He wrote to me about it, and with my permission published the puzzle on his site.

The mathpuzzle readership was definitely the right audience for me! Over time, I saw various proposed solutions. At first, they tended to be in error (e.g., in one case because the solver was working from a faulty translation), but over time I saw at least two solutions that appeared correct, yet different from the one I had in mind. I went back to the program I'd written to "prove" that the solution was unique, and using the two alternative solutions managed to find the bug in the program. (How embarrassing!)

It turned out there were on the order of 50 solutions, which was far too many. So with a bit of additional effort, I came up with a corrected version that I thought re-established the uniqueness of the solution. Alas, someone "cooked" this one also. I took a few additional swings at finding a version that retains certain features while not allowing any alternate solutions, but never found one I was willing to make any assertions about. :-(

That's where things sat for over ten years. Then, in 2013, Don Knuth came across my puzzle and we corresponded briefly about it. Two years later, he found more time to study it, and suggested a few minor changes that would yield a more constrained answer that, though different from what I had originally envisioned, has other interesting properties. Indeed, I believe Knuth plans to include a version of it in the problems section in one of the subvolumes of part 4 of The Art of Computer Programming. His elaboration there includes a small change that introduces the possibility of correctly answering D to question 20!

I'll leave Knuth's insights for him to expound upon elsewhere. For my part I'll settle for finally having this puzzle nailed down in a version that actually works.