wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Guessing game
        
(Message started by: inexorable on Jan 22^nd, 2006, 8:54pm)

Title: Guessing game
Post by inexorable on Jan 22^nd, 2006, 8:54pm

A and B are playing the "guessing game". In this game, B selects, in his mind, an integer between 1 and n (inclusive) , and then A wins if he correctly guesses the integer that B has selected. To make the correct guess, A can only ask B queries of this form: A specifies a subset X of {1,2...n} and asks B if his chosen number lies in this subset. B usually replies truthfully to these queries, but he is allowed to lie at most k times.

Of course, B can try to act clever, by not actually picking a number beforehand, but adapting his answers according to the queries asked by A (as long as he is able to pretend that he had actually chosen a number beforehand).

Given n and k find the minimum number of queries that A should be allowed to ask so that he has a winning strategy. and what strategy shud A follow?

A relatied problem of 7 boolean questions has been discussed but I am not sure whether this has been asked.

Title: Re: Guessing game
Post by towr on Jan 23^rd, 2006, 12:47am

homework/competition sense tingling..
This was asked in nearly the exact same way yesterday: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1137840219

So what sparks this sudden interest in this problem?

Title: Re: Guessing game
Post by inexorable on Jan 23^rd, 2006, 4:01am

I wondered abt this version of problem when I first heard of 7 boolean questions problem.Seeing it in a competition sparked the interest again.