[TheDong]

Edit: Oops, nope, this comment is wrong, ty fgna for pointing that out!

I feel like there's an even simpler proof that you can beat adversarial-ballmer, with exactly the same expected positive outcome as binary search vs random ballmer.

I call my algorithm "randomly offset binary search". It goes like this:

1. Pick a random number between 0-100, call this 'offset'

2. Perform the binary search algorithm, except at each step add 'offset' to the value and mod by 100.

That's it. Now, even if Ballmer knows you're using this strategy, he can't make it perform any worse by selecting any specific number. Therefore your expected outcome is still $0.20 per game, beating the strategy proposed in this blog post.

[fgna]

Unfortunately the numbers are not circular :( By offsetting the initial number, the binary search does not work optimally right? Imagine the number is below 50, and you start by guessing 60, now you have to search for 30 numbers instead of 25, and thus the binary search is not optimal. reply

[TheDong]

Ah, yup, you're right. Ballmer's answer of "high or low" isn't in the offset number system, but the normal one, so my strategy doesn't work.

That's what I get for not thinking it through properly, thank you for pointing that out!

[n4r9]

Neat. A nice way to see this is to imagine that the numbers 1-100 are arranged around a clockface; you randomly spin the clock before doing a conventional binary search starting from the top.

[kikimora]

This is brilliant!