Steven Ballmer's guessing game - Help me understand.

[u/nullstring]

Recently on an Instagram doom scrolling session, I encountered this interview from Steve Ballmer where he describe his "guessing game", which he gave to interviewees at Microsoft. https://www.youtube.com/watch?v=svCYbkS0Sjk

The basics are:

• Steve Ballmer chooses a number between 1 and 100.
• The interviewee guesses a number, and Steve will tell you if it's high or low.
• If you get it correct on the first guess, then you get $5. Each additional guess reduces the prize by $1, until on the 7th guess you start paying him.

(watch the video if that's not clear)

Should you play this game?

Now, this analysis is pretty easy if Steve chooses a random number. The worst case binary search is lg(100), which rounded up is 7 gusses at worst. And it's easy to make a table of payout of each guess, sum it up and average.

Found on guess	Numbers	Payout	Subtotal
1	1	+$5	+$5
2	2	+$4	+$8
3	4	+$3	+$12
4	8	+$2	+$16
5	16	+$1	+$16
6	32	$0	$0
7	37	-$1	-$37
Total	100	—	+$20

So, on average you'll get $0.20 per game ($20/100). (So yes, you should play)

But that's not the game. The game is whether you should play this game if Steve is able to strategically choose which number. THAT game is much harder to figure out.

As Steve is going to try to choose numbers that are worst case for a binary search, the optimal search algorithm is NOT going to be to start with 50 every time. You would use an alternative search tree in order to optimize for Steve choosing numbers that require 7 guesses. And of course, Steve would then need to optimize his strategy further in kind.

So, as one does, I asked chatgpt how this would work.

Astonishingly, it's very confident that by using a pool of optimal binary search trees, you could get an average payout of $0.196 per game. Meaning we only lose ~1/2cent by allowing steve to choose strategically.

I understand the basics of the strategy, but when it comes to the math of calculating the average payout I am just lost. (Basically everything after and including 296 / 51)

Can anyone explain to me how this works? Or if chatgpt is off its rocker?

I especially can't get my head around the fact that chatgpt believes that Steve has no choices that are more optimal than others. No matter which number Steve chooses, it claims the randomized collection of search trees can make the expected payout exactly 0.196 (average) every time. That doesn't make any intuitive sense to me.

My answer is that you should still play. If both sides play optimally, your expected payout is about +$0.196 per game, or just under 20 cents.

The first thing to notice is that a normal, fixed binary search does not work against a strategic Steve. If you always use the same search tree, Steve can look at that tree, choose one of the numbers that requires 7 guesses, and guarantee that you lose $1.

The solution is to randomize which binary-search tree you use.

This does not mean picking a random number from 1-100 as your first guess. That would often produce a badly unbalanced search. Instead, you randomly choose from many different good binary-search trees. Each individual tree still finds every possible number within 7 guesses, but different numbers occupy the good and bad positions in different trees.

So, for example, 73 might take 7 guesses in one tree, 5 guesses in another, and 4 in another. Steve is allowed to know exactly how your randomized strategy works and choose 73 every single game if he thinks that is best. What he does not know is which search tree you privately selected for that particular game.

We can describe the problem mathematically. Let d(n) be the expected number of guesses needed if Steve chooses the number n. Steve will choose whichever number makes d(n) largest, while you want to choose your randomized strategy so that this largest value is as small as possible.

The optimum turns out to be:

296 / 51 = 5.803921568... guesses

Since the payout on guess k is 6 - k, the expected payout is therefore:

6 - 296/51 = 10/51 = $0.196078...

or about 19.6 cents per game.

The really important part is that this is not an average over Steve choosing different numbers. The randomized search strategy can be constructed so that every single number Steve could choose has the same expected result:

d(1) = d(2) = ... = d(100) = 296/51

So if Steve chooses 1 every game, your expected payout is $0.196078.... If he chooses 50 every game, it is $0.196078.... If he chooses 73, 99, or 100, it is still $0.196078....

In other words, Steve has no number that is better for him than any other. He can study your strategy as much as he wants and deliberately choose what he thinks is the worst number, but the randomized mixture of trees has equalized the expected payout across all 100 choices. Strictly speaking, every number is an equally good choice for Steve — but none of them reduces your expected payout below 19.6 cents.

There are two things that need to be shown for that number to be meaningful. First, you have to show that no strategy can do better. One way to do that is to temporarily imagine Steve assigning weight 2 to the numbers 1 and 100, and weight 1 to every number in between. That gives 102 total weight.

For any valid binary-search tree, you can calculate its weighted total number of guesses. The smallest possible weighted total is 592. Therefore even the best tree has weighted average depth:

592 / 102 = 296 / 51 = 5.803921568...

Randomizing between trees cannot beat that bound, because an average of several trees cannot have a lower weighted cost than the best individual tree for those weights. So no strategy can guarantee an expected search depth below 296/51.

The other half is showing that the bound can actually be reached. Solving the corresponding optimization problem gives a randomized mixture of valid search trees for which:

d(1) = d(2) = ... = d(100) = 296/51

In other words, every possible number has exactly the same expected search depth. Steve can choose whichever number he wants; there is no longer a particularly bad number for him to exploit.

I also checked this by simulation: 1,000,000 games for each of Steve's 100 possible fixed choices, for 100,000,000 games total. The results converge to the same expected payout of about +$0.196 per game.

So the answer is: yes, you should play. If Steve chooses randomly, the game is worth exactly 20 cents per play. If Steve chooses strategically and both sides play optimally, it is still worth about 19.6 cents per play to you.

[u/FireCire7]

Check this out:  https://rahne.si/optimisation/2026/01/07/steve-ballmer-interview.html

[u/nullstring → u/FireCire7]

Thank you! That helps tremendously.

[u/Pure-Passenger-6986]

The number Steve Ballmer picks is 100 if he plays strategically. It's a recursive problem.

Say you start from 1-100. If you and Steve play optimally, he will always pick a number that is guaranteed to be in the 7th guess for a binary tree search (by the 7th guess you have exhausted the tree).

So you know he's going to pick one of those (37?) numbers, but so does Steve know that you know, so you start a binary tree from those resulting sets and Steve does the same thing - he always picks a number from the set that is deepest to minimize his losses. But you know that too, so you repeat until you get to the 'deepest' guess, which is 100.

If Steve is a true logic genius, you always make $5 (or whatever it is).

It's a variation of the Nash Equilibrium / Prisoner's Dilemma.

[u/bayesian13 → u/Pure-Passenger-6986]

thank you. what are the 37 numbers on the binary tree? according to AI they are:

2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98, 100

...

For example, if the target number is 2:

Guess 50 (Too high) → Range becomes 1 to 49

Guess 25 (Too high) → Range becomes 1 to 24

Guess 12 (Too high) → Range becomes 1 to 11

Guess 6 (Too high) → Range becomes 1 to 5

Guess 3 (Too high) → Range becomes 1 to 2

Guess 1 (Too low) → Range becomes 2 to 2

Guess 2 (Correct on the 7th try)

[u/Pure-Passenger-6986 → u/bayesian13]

That may be accurate for the first round, but you now have to recurse that as a new tree. You won’t guess 50, 25 etc because Steve knows that is not optimal, so you’d start your guess with say 55, 24 (not sure on sight what the midpoint is) and you get it in 5 guesses. But Steve knows this fact, so you can ignore those numbers. Eventually you’ll get to 2, 100 with 100 being the “least” optimal choice, making it the only possible guess.

[u/Artistic-Flamingo-92 → u/Pure-Passenger-6986]

I feel like u/FireCire7 provides the better answer. Choosing 100 is clearly not a Nash equilibrium, and I don’t see this as a variation of the prisoner’s dilemma.

The trick here, on both sides, is that a mixed strategy is needed.

[u/Own_Pop_9711]

All the numbers being equally optimal is a standard style of result in these competitive zero sum games. If you had a strategy where Steve would prefer playing 19 over 27, then you could do better by shifting your tree choices to make 19 a little worse and 27 a little better.

[u/fr_dav → u/Own_Pop_9711]

The optimal strategy for Steve is to play 1 and 100 with probability 2/102, and all other (2...99) with uniform probability 1/102, because shifting the binary search tree in favor of 1 or 100 is difficult.

[u/Own_Pop_9711 → u/fr_dav]

Yes but each number is equally good for Steve to play. Steve has to play 1 and 100 more often so that every binary search tree is equally good for the candidate to play

[u/fr_dav → u/Own_Pop_9711]

Obviously we don't speak the same language. "Equally good" for me would mean the best mixed strategy has them with *equal* probability. I have no idea what you mean by "equally good" here.

[u/Own_Pop_9711 → u/fr_dav]

Equally good means your payoff under the equilibrium is the same no matter which one you happen to pick

[u/PuzzleheadedNose3666]

If an average you make about $.20 per game, you shouldn’t play at all.   If each game takes a minute, you’re only making $12 an hour. This is a poor use of your time and Steve Ballmer’s time.    If you could play in 30 seconds, you’d be up to $24 an hour, but still not great.   

[u/AMWJ → u/PuzzleheadedNose3666]

Well, at work I use Microsoft Teams and make Steve Ballmer money. Can you name a more efficient way to make Steve Ballmer lose money than by playing this game?

[u/reddithenry → u/AMWJ]

>Can you name a more efficient way to make Steve Ballmer lose money than by playing this game?

Make him CEO of Microsoft?

[u/nullstring → u/PuzzleheadedNose3666]

It's a computer science problem. How about we define it so that we can play 1000 games per second?

[u/MtlStatsGuy]

ChatGPT is absolutely correct. This is basic game theory. You can randomize between binary searches so that every number - even 50 - will be reached after 5.8 guesses on average between all your binary searches. So as long as you are not predictable in your strategy, you will win 20c per game on average over the long term.

[u/AMWJ]

I especially can't get my head around the fact that chatgpt believes that Steve has no choices that are more optimal than others.

I have not completely read nor understood all of ChatGPT's response. But what this quoted part is referring to is that Game Theory would have you pick your strategy such that no choice made by Steve is better than any other. That is, simply by your strategy being optimal, Steve must have no choice better than another.

The reason for this is that, if one option were better than the others, Steve would choose to do it 100% of the time. And, thus, you would've done better with a strategy of always guessing that one solution Steve always chooses. Since we've already assumed deterministic strategies aren't optimal, this is a contradiction. Therefore, no strategy can be more optimal than the others.

(A similar argument, I believe, applies to the opposite, with a few extra steps: that for an optimal strategy by you, no move by Steve can be worse than all the others.)

[u/kalmakka]

I'm not saying ChatGPT is correct in this case. It has not provided what kind of distribution you should use. But what it is saying makes sense in terms of game theory.

You distinguish between pure strategies (i.e. always behaving in a predictable manner) and mixed strategies (i.e. using a source of randomness to pick between different options). And when considering what mixed strategy you should use, you can assume that your opponent will always pick the pure strategy that is the best against your strategy: if your mixed strategy gives an expected payout of at least x when playing against any pure strategy, then it will also give an expected payout of at least x against any mixed strategy. Some times this means that you should find a strategy that scores you the same value against any choice your opponent makes, but there might be cases where your opponent has objectively bad strategies (dominated strategies, I think they are called) that you would score more than x against. In this situation, there are no objectively bad strategies for Steve, so the optimal mixed strategy will score the same value against all pure strategies employed by Steve, and therefore against any mixed strategy he could apply.

For instance, in rock-paper-scissors, if you decide on the mixed strategy of picking r-p-s with probabilities (0.4, 0.3, 0.3) then you will have an expected payout of -0.1 against the pure strategy of your opponent going paper. So if your opponent knows your strategy, they will always play paper, and you will lose in the long term. But if you pick (1/3, 1/3, 1/3) then no pure strategy will beat you (giving you a payout of 0), and so no mixed strategy can beat you neither.

[u/FireCire7]

Well, it described a valid strategy. Any mixed strategy can be described by a random distribution of binary trees and the largest expected value and a weighted average of such optimal trees which smooth it out amongst the numbers give lower and upper bounds. 

However, it provides zero details so there’s no way to ascertain if it actually did that strategy under the hood or if it’s hallucinating. Also, it’s not clear to me why its Steve strategy of just double weighting 1 and 100 is right - I’d naively have thought it to be more complicated.

[u/villageHeretic]

If you do the binary search you can find any number from 0 to 127 in 7 tries. If you can't do it in 7 tries and you made thru to an interview at Microsoft you definitely owe Balmer a dollar.

[u/rij1]

You need to ask him first if he writes down the number on a piece of paper (which will be shown at the end) and then we do this or not.

If he does not write down the number he can simply say that he has picked a number but then each time gives you the least informative answer to whatever number you give him which will lead to him always winning a dollar.

[u/TooLateForMeTF]

All mathematical analysis aside, my answer would be "yes, because I have a roughly one in six chance of winning money off of you, and at worst I'm going to owe you two dollars. And two dollars is an excellent price for a one-in-six chance of being able to say 'I won money off of Steve Ballmer.' Especially if I'm allowed to play the game more than once."

I would like to think he would be impressed both by the analytical and meta-analytical aspects of my answer...

[u/Miltnoid]

So I’m too lazy to go through what chatGPT said, but it makes sense to me that there is a solution that makes everything equivalent in expectation.

Consider taking the set of all possible total orderings of 1..100. Then, he chooses a number. The. You randomly select one of the total orderings. Then you do a BST with that total ordering.

Since in the set of in total orderings there is an automorphism based on swapping any two numbers, each number has equivalent probability to appear at any specific position in the tree.

[u/myaccountformath → u/Miltnoid]

I'm not sure I follow. If you choose a random ordering, his answer of higher or lower will still be relative to the standard ordering.

[u/Miltnoid → u/myaccountformath]

Fuck lol my bad ignore me

[u/cosmopoof]

Given that it doesn't specify base 10, I'll define base 2 and with only 7 options win easily.

[u/Gold_Ad8890]

I especially can't get my head around the fact that chatgpt believes that Steve has no choices that are more optimal than others.

it doesn't. it doesn't have beliefs at all. it's a machine for generating grammatically correct text and nothing else. to the extent that it "knows" anything at all, that "knowledge" is limited to what order words usually go in.

[u/nullstring → u/Gold_Ad8890]

Yes... very helpful...

I do, of course, understand how an LLM works. I'm just anthropomorphizing it in casual language rather than writing "the model generated the claim that..." every time.

[u/Gold_Ad8890 → u/nullstring]

the point is deeper than that you used the wrong words. i'm saying it's not doing any reasoning at all. its output doesn't mean anything because "meaning" is not a thing the machine is designed to be able to recognize. you shouldn't trust a text generator to tell you about logic. you shouldn't trust it to tell you anything, but especially not to be able to do logic.

[u/MidnightAtHighSpeed → u/Gold_Ad8890]

Normally I'd be able to resist the urge to be this pedantic, but given that we're in a math sub, what are the conditions that an entity must satisfy for us to ascribe it "beliefs" and "knowledge" and why does an LLM not satisfy them?

[u/nullstring → u/Gold_Ad8890]

I don't really understand what you're quibbling about. I agree with everything you're saying.

I didn't trust it do to anything. I asked a question and I didn't understand the output nor how it came to the conclusion. Which means I categorically should not trust it -> Thus, I came here looking for further information (after googling didn't come up with anything useful. )

[u/Gold_Ad8890 → u/nullstring]

if you weren't going to trust it, why bother asking it?

[u/nullstring → u/Gold_Ad8890]

I also don't trust reddit strangers.. doesn't mean their answers can't be helpful.

[u/johndburger → u/Gold_Ad8890]

it doesn't have beliefs at all.

True.

It's a machine for generating grammatically correct text and nothing else. to the extent that it "knows" anything at all, that "knowledge" is limited to what order words usually go in.

This isn’t true anymore, these things are now much more complicated. There is typically a harness that uses the core LLM at multiple levels to decide, for instance, which external tools to call, and these can do all kinds of things, because they’re code written by human beings, as is the harness (although that’s changing).

As an extremely simplistic example, you can ask these things to multiple several large numbers, and they will (usually) produce the correct answer. Knowing “what order words usually go in” is not sufficient to explain that.

[u/notsteve2247]

I’ve seen this floating around and have the same thought every time. You guys are all overthinking this. 

The question is “should you play this game?”

The correct answer is “no.”

It’s a business aptitude interview question not a math question. He holds the leverage because he made the rules and gets to pick the number. Don’t start a negotiation in that position. 

[u/nullstring → u/notsteve2247]

It’s a business aptitude interview question not a math question. He holds the leverage because he made the rules and gets to pick the number. Don’t start a negotiation in that position.

... that's not correct at all. It's a question he is asking to new software developer prospective hires. You're not likely to be able to accurately answer the question on the spot (unless you've considered it before). He just wants to understand your thought processes on it.

• Binary Search -> Lg(100) -> 6.5ish -> average of 6.5 guesses leans you towards "no" from the get go, but you'd explain it might not be that simple because the payouts from the lower guesses might offset that.

• But then you ask if he is giving you actual random numbers or if he is strategically choosing numbers that are going to take 7 guesses with a normal binary search. He will say yes.

• Then you'll answer that without doing the math, it's easy to conclude that "no" would be the right answer.

Even he thinks the answer is "no", when he is actually wrong. If the conversation continues, you could explain the method to actually know for sure. But I doubt it would.

[u/notsteve2247 → u/nullstring]

I’ve never dove deep on the Balmer quote but I don’t think I ever saw it specifically mentioned that it was for software engineering applicants. I’d like to think if someone were interviewing for a business side role with him and gave an answer like mine, he’d be pleased. 

He did primarily lead Sales teams anyway. I know he spent time managing developers, but that’s not where my head went personally when I saw the question. 

[u/nullstring → u/notsteve2247]

You know what, I might have made an assumption there. But you're right, how you would answer would depend on what you're interviewing for, for sure.

Understanding binary searches is like a bare minimum skill for a software developer though, so it'd be a fantastic question for that.