5 ms·
My feeling without being rigorous is that something is wrong with this solution. Notably the size 13 case enumerated in the post, choosing 1 as the Chooser wil
by andrewla 2y ago
My feeling without being rigorous is that something is wrong with this solution.
Notably the size 13 case enumerated in the post, choosing 1 as the Chooser will always take 3 guesses (the most possible). Even in an iteration of a mixed strategy the Guesser will never guess 1 in fewer than 3. This is also true for 13.
- rachofsunshine 2y agoMax guesses for n=13 is floor(log2(13)) + 1 = 4, not 3. And in a Chooser-always-chooses-1-or-13 strategy, the Guesser has a trivial strategy ("guess 1, then guess 13") that takes much less than 3 guesses on average.
- andrewla 2y agoYou are correct -- this was my misreading of the preorder traversal.