Author |
Topic: Guessing game (Read 3670 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Guessing game
« on: Jan 22nd, 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 22nd, 2006, 8:57pm by inexorable » |
 IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Guessing game
« Reply #2 on: Jan 23rd, 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
