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?