Suppose we consider a variant of twenty questions game, where the answerer chooses two answers. On a query from the questioner, the answerer replies $0, 1$ or $2$, depending on the number of answers that satisfy the question.
The questioner queries the answerer in the same way as the original game, and wins if one guesses both answers correctly.
Example. Suppose that the two answers are apples and oranges. On a query "Is it a fruit?", the answerer replies $2$. On a query "Is it an orange?", the answerer replies $1$, and so on.
It is obvious that the game has gotten harder, but I got curious about how much it got harder. It is widely known that the answer for the original twenty questions game has $20$ bits of entropy, since the answerer replies 'Yes' or 'No' for each question.
Question. How many questions would we need to correctly identify the two answers? Would there be a (constructive) clever way to obtain them?
At first I mistakenly thought that the answer would be ordered, so I thought I could ask questions like "Is it the first answer and [some condition]?". Then the answerer obviously cannot reply $2$, so we can obtain the answers in $40$ questions. I got stuck after realizing my mistake.
This came up while playing the twenty questions game, so the above statement may lack additional assumptions. Feel free to leave a comment. Thanks in advance!
If there are $n$ objects, there are $\frac {n(n-1)}2$ pairs and you need to find one pair. Assuming you can make maximum use of each question, splitting the remaining possibilities evenly among the three answers, there are $3^{20}$ sets of answers, so we need to solve $$\frac {n(n-1)}2 =3^{20}$$ which Alpha says has $n \approx 83\ 508$
This compares with $2^{20}=1\ 048\ 576$ objects you can select one of in the original game.