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; however, among those guesses, you may only make at most g guesses that are too high. The value g will be specified at the start of the game, and if you make more than g guesses that are too high, you lose. So, for example, if g = 0, then you can win in N guesses by simply guessing the sequence 1, 2, 3, … a. Suppose g = ceil(log N). What strategy minimizes the number of guesses? b. Suppose g = 1. Show that you can always win in O(N 1/2)

Explanation / Answer

a) If g = ceil(log N).

Strategy
Let value of prize be vp
consider an array of n numbers from 1 to n.

Suppose after certain point we are left with array from index i to index j and number of guesses left be f.

Always guess the number in the middle of the array(nmber at index k=(i+j)/2). let it's value be x and its index be k.
if x=vp : then we are done
else : if x<vp : then our array becomes array from index i to index k. Number of guesses becomes the same(i.e f) and repeat the process.
   else: then our array becomes array from index k to index j and number of guesses decreases by one(i.e f-1) and repeat the process.
in the worst case we use all the g and find the number.

b) If g=1;
stategy:
consider the array from 1 to n.
let i=1 ;
we always guess the i+n^(1/2)(let its value be x and index be k).
if x=vp : then we are done.
else : if x<vp : i = i+n^(1/2)+1 and repeat the process.
   else : consider array from index i to i+n^(1/2)-1. guess i,i+1,i+2 ..... .

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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