The exact analysis for n=13 (instead of n=100) is presented--or rather, just the answer from the exhaustive search. The answer for n=100 is still unknown.
The punch line of this post is that if Ballmer defines the payouts so that the interviewee receives floor(lg N) dollars for hitting in one guess, then Ballmer's expected payout decreases as N increases — with a sharp step upward each time N reaches a power of two.
This is... exactly how the floor function is defined to behave!
The graphs would be much more enlightening if the artificial step function were removed. Instead of subtracting from floor(lg N), subtract from plain old lg N — or even don't subtract from anything at all, and just graph the number of guesses required.
Author of the linked article here; you're right that just the expected number of guesses is roughly monotonic. However, that expected number of guesses (along with Ballmer's expected payout) increases, not decreases, as N increases, with a sharp step downward, not upward, each time N reaches a power of two.
The intent here is to reasonably compare hypothetical job interview questions for different N. If N=100, then Ballmer offers 6 dollars in exchange for one dollar per guess, and the linked Gukov article shows that Ballmer's expected return is negative.
What if he instead challenged an interview candidate with N=127? What about N=255, or N=511, etc.? He presumably wouldn't continue to offer only 6 dollars to play in these cases, but also presumably a similarly nice round number of dollars... and now the question/conjecture is interesting: from the updated graph, it looks like Ballmer's expected return decreases as N=2^k-1 increases, but does it always remain positive? Or is there some sufficiently large key space beyond which even an optimal guesser can't ever win on average?
To me, this question seems easier to ask when the expected return is presented in this way. That is, does each sawtooth interval always span zero expected return?
I don't see why this can't be solved (approximated) recursively.
If I know the EV of 1 and 2 choices, then the 3 number situation is the same as whatever weight I assign to choosing the first number multipled by Ballmer's strategy multiplied by the EV of the 1 case when I pick 2, and the 2 case if I pick 1 or 3. Run this as a Counter Factual Regret minimization problem for each value from 3 through 100 with some sort of error threshold and you have a good enough answer.
I'm not 100% sure of that though. Perhaps there's a dependency in the two steps that confounds this approach?
It might be fun to play an iterated version of this game.
Also I'd be keen to see a web ui where you can play against an ai. Not quite sure how the ai would work though. You don't necessarily want the ai to play optimally (if the optimal strategy were even known) because the fun is in working out how to exploit the other player's flaws.
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.
Max 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.
The exact analysis for n=13 (instead of n=100) is presented--or rather, just the answer from the exhaustive search. The answer for n=100 is still unknown.