Although Ballmer could still be incorrect, because a 'sufficiently logical' player would also presumably know that he could pick numbers that'll be the most difficult to find via binary-search, so by the same logic you could also meta-game it, and assume any number that can be found in 5 steps with a binary search is immediately out. This would narrow the search space to only 37 numbers, which can then easily be found within 5 guesses.

But he also knows that you know that he could pick numbers that will be the most difficult... So could then pick one of the numbers that actually are guessable within 5 guesses to trick you.

But then you also know that he knows that you know that he could pick difficult numbers too.

I'm not entirely sure if this invalidates Ballmer's advantage, but I would be interested to know what the 'perfect' strategy would be for this game considering the meta-game.

There isn't much of metagame if number is only in Ballmers mind. No matter what guesses you choose he can force you to make at least log_2(100) guesses. Doing anything except splitting in half will only increase amount of guesses. There are two things that can change the game, requiring Baller to write the number on a piece of paper before the start. Other thing you could do is writing a number on piece of paper yourself halfway during the game. If opponent is changing the number adversarially with goal of maximizing guesses you can force them to "pick" a specific number. Afterwards you can open the piece of paper and claim that you actually guessed the number with the first attempt.

This assumes Ballmer is cheating, rather than just behaving adversarially but within the rules.

If we accept cheating is allowed, we can also potentially accept other 'cheating' scenarios where the player repeatedly punches Ballmer in the face until he discloses the number, thus winning. Or where the player just refuses to pay at the end.

IMO the problem is only interesting if we assume any form of cheating isn't allowed.

Do you want to catch a chair to the side of the head? Because this is how you catch a chair to the side of the head.

Also the number only exists in Ballmer's mind, so if he wanted to, he could change it to be unfavourable should you make a lucky guess.

Here, you can play the game with me. Higher. Lower. Higher. Higher. Lower. Correct. Six guesses, you owe me $1.

Yes, and a SWE should consider external inputs untrusted until proven otherwise.

your point is valid but you cannot have a static answer list.

if I started off by guessing 50 twice you're cooked. or 50 and 52.

0$, as posed.

the article focuses on the next part of that sentence

> secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer

and given that the first rule still holds where he chooses hard numbers, then the expected value of the game is negative (aside from meta-gaming this, which is out of scope for a technical problem)

But if you know the number picker is going to choose these numbers you can optimize your algorithm.

but you don't know. Only he knows that he's going to pick numbers the binary search will fail on and he states as much as his reason that you shouldn't play the game.

How do you know that?