I'm not sure why would anyone listen to that clown.

The question is appropriate for an intern in a technical field. It's just a straightforward application of trivial binary search which takes approximately log2(n) tries to find the answer. The average number of tries is somewhat less (because every test splits the remaining set of numbers in three, not two, parts (<, >, and "got it") so you only need 6 questions to differentiate between 127 numbers, because 100 < 127, and because search stops early for some numbers. Given that he offers $5 for 1 try, and $0 for 6 tries you cannot lose. He is absolutely wrong in his statement that the game is a losing proposition.

He is also wrong in his statement that there are "much" more numbers resulting in longest search so he can specifically pick them (he cannot, as I can chose some random shifts in the search tree shape owing to the fact that I'm only required to consider 100 possibilities out of 127, a simple randomization strategy is to randomly choose to base my search on any range from [-26, 100] to [1, 128] and simply ignore the out-of-range part of the search tree). For 100 choices and simple greedy bottom-up construction of the search (3, 3*2+1=7, 7*2+1=15, etc) he gets 69 "hard" numbers for which he gives $0, not "many more". All in all, I'd expect to win 57 cents on average using randomized search tree strategy.

Aww yeah let's combine computer science with game theory.

Every student fresh off a campus being interviewed by Balmer is going to know about binary search and that binary search is the "correct" way to solve this problem. That student will probably not realize the usual assumption that the target numbers come from a random uniform distribution is false for this game. Instead the number gets chosen by an incentivized adversary who knows exactly what process the student has been taught to solve this problem.

So Balmer can know in advance the set of optimal guesses where he pays the student, and then choose around them. If an open guess range doesn't have a single pivot because it contains an even number of numbers, then he should rule both of them out.

That leaves a set of 41 numbers where Balmer would never lose money against an "optimal" binary search. (the range isn't quite wide enough for him to guarantee a positive win for himself though)

If the student then chooses to binary search that reduced set of 41 numbers then the expected gain is around $1.57 (some approximation due to being lazy about the rounding possibilities) and there is no chance of losing money.

Amusingly enough, if Balmer turns out to be an out-of-practice old man then he forgets the set of 41 "hard" numbers and instead picks a number that has a chance of being guessed in a standard binary search (such as 57, *cough* which could be an optimal 4th guess) then the counter strategy falls apart miserably.

I'm not sure why would anyone listen to that clown.

ReplyDeleteThe question is appropriate for an intern in a technical field. It's just a straightforward application of trivial binary search which takes approximately log2(n) tries to find the answer. The average number of tries is somewhat less (because every test splits the remaining set of numbers in three, not two, parts (<, >, and "got it") so you only need 6 questions to differentiate between 127 numbers, because 100 < 127, and because search stops early for some numbers. Given that he offers $5 for 1 try, and $0 for 6 tries you cannot lose. He is absolutely wrong in his statement that the game is a losing proposition.

He is also wrong in his statement that there are "much" more numbers resulting in longest search so he can specifically pick them (he cannot, as I can chose some random shifts in the search tree shape owing to the fact that I'm only required to consider 100 possibilities out of 127, a simple randomization strategy is to randomly choose to base my search on any range from [-26, 100] to [1, 128] and simply ignore the out-of-range part of the search tree). For 100 choices and simple greedy bottom-up construction of the search (3, 3*2+1=7, 7*2+1=15, etc) he gets 69 "hard" numbers for which he gives $0, not "many more". All in all, I'd expect to win 57 cents on average using randomized search tree strategy.

Aww yeah let's combine computer science with game theory.

ReplyDeleteEvery student fresh off a campus being interviewed by Balmer is going to know about binary search and that binary search is the "correct" way to solve this problem. That student will probably not realize the usual assumption that the target numbers come from a random uniform distribution is false for this game. Instead the number gets chosen by an incentivized adversary who knows exactly what process the student has been taught to solve this problem.

So Balmer can know in advance the set of optimal guesses where he pays the student, and then choose around them. If an open guess range doesn't have a single pivot because it contains an even number of numbers, then he should rule both of them out.

That leaves a set of 41 numbers where Balmer would never lose money against an "optimal" binary search. (the range isn't quite wide enough for him to guarantee a positive win for himself though)

If the student then chooses to binary search that reduced set of 41 numbers then the expected gain is around $1.57 (some approximation due to being lazy about the rounding possibilities) and there is no chance of losing money.

Amusingly enough, if Balmer turns out to be an out-of-practice old man then he forgets the set of 41 "hard" numbers and instead picks a number that has a chance of being guessed in a standard binary search (such as 57, *cough* which could be an optimal 4th guess) then the counter strategy falls apart miserably.

2 + 2 = 22...Am I hired?

ReplyDelete