wu :: forums
wu :: forums - Guessing game

Welcome, Guest. Please Login or Register.
Jan 19th, 2022, 12:51pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, SMQ, ThudnBlunder, Grimbal, towr, william wu, Icarus)
   Guessing game
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Guessing game  (Read 3623 times)
inexorable
Full Member
***





   


Posts: 211
Guessing game  
« on: Jan 22nd, 2006, 8:54pm »
Quote Quote Modify 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
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Guessing game  
« Reply #1 on: Jan 23rd, 2006, 12:47am »
Quote Quote Modify Modify

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_med ium;action=display;num=1137840219
 
So what sparks this sudden interest in this problem?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
inexorable
Full Member
***





   


Posts: 211
Re: Guessing game  
« Reply #2 on: Jan 23rd, 2006, 4:01am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board