wu :: forums « wu :: forums - Guessing game » Welcome, Guest. Please Login or Register. Jan 19th, 2022, 12:51pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, SMQ, ThudnBlunder, Grimbal, towr, william wu, Icarus)    Guessing game « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Guessing game  (Read 3623 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
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Guessing game   « Reply #1 on: Jan 23rd, 2006, 12:47am » Quote 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 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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »