Re:Steve Ballmer's incorrect binary search interview question
by wrvn on Tuesday September 03, 2024 @12:42PM
(#41436658)
That approach would still leave you weak to always picking 1 or 100.
Without proof, I believe the optimal guessing strategy would perform equal (on average) for every number, to not give the opponent any standout choice (common for optimal strategies, but not always the case). If my math serves me right, that would be an average of log2(100) = 6.64 guesses for any number, which would make you lose 0.64$ on average.
[ Parent
| on HN ]
Re:Steve Ballmer's incorrect binary search interview question
by wrvn on Tuesday September 03, 2024 @12:46PM
(#41436697)
Although upon further thinking, you could then sprinkle in some binomial searches to abuse the uniformity. So the -0.64$ is merely a lower bound.
Re:Steve Ballmer's incorrect binary search interview question
by gukoff on Thursday September 05, 2024 @07:18PM
(#41461248)
You forget that the quick guesses bring you more than $1!
As the original article says, on average you can win $0.20. But that's indeed the upper bound if we speak of the adversarial number picking.