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.
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.