There is a prize hidden in a box; the value of the prize is a positive integer b

Question

There is a prize hidden in a box; the value of the prize is a positive integer between 1 and N, and you are given N. To win the prize, you have to guess its value. Your goal is to do it in as few guesses as possible. You start with a number of chips (specied below). Each chip allows you one guess that’s too high. If you guess too high, and you have no chips, you lose. So, for example, if you start with no chips, then you can win in N guesses by simply guessing the sequence 1, 2, 3, ... .
Suppose you start with 1 chip. We can solve this in 2 N guesses. But, I want to solve it in less than 2N guesses. Can anyone solve this with better constant?

Hint: We need to take large interval at staring guesses and reduce the size as we go on. YOU MAY OR MAYNOT USE THIS HINT. THIS MAY BE WRONG

Explanation / Answer

You can solve this in log(n) steps by guessing half marks. Sort of like binary search. While you still have chips, guess N/2. If there are still chips left after this, If the number is too high, update N = (N + N/2) / 2 If the number is too low, update N = (N - N/2) / 2. Otherwise, you run out of chips, guess from N/2 to N by increments of one.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.