Author 
Topic: Guessing game (Read 3623 times) 

inexorable
Full Member
Posts: 211


Guessing game
« on: Jan 22^{nd}, 2006, 8:54pm » 
Quote Modify

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.

« Last Edit: Jan 22^{nd}, 2006, 8:57pm by inexorable » 
IP Logged 



inexorable
Full Member
Posts: 211


Re: Guessing game
« Reply #2 on: Jan 23^{rd}, 2006, 4:01am » 
Quote Modify

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.


IP Logged 



