Author |
Topic: Interesting Game problem (Read 784 times) |
|
lexandyacc
Newbie
Posts: 9
|
 |
Interesting Game problem
« on: Jan 21st, 2006, 2:43am » |
 Quote  Modify
|
Sachin and Rahul are playing the "guessing game". In this game, Rahul selects, in her mind, an integer between 1 and n (inclusive) , and then Sachin wins if he correctly guesses the integer that Rahul has selected. To make the correct guess, Sachin can only ask Rahul queries of this form: Sachin specifies a subset A of {1,2...n} and asks Rahul if his chosen number lies in this subset. Rahul usually replies truthfully to these queries, but he is allowed to lie at most k times.
Of course, Rahul can try to act clever, by not actually picking a number beforehand, but adapting his answers according to the queries asked by Sachin (as long as he is able to pretend that he had actually chosen a number beforehand).
Given N and K,
how will u find for each pair (n,k) such that 1<=n<=N and 0<=k<=K,
the minimum number of queries that Sachin should be allowed to ask so that he has a winning strategy.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
|
Re: Interesting Game problem
« Reply #1 on: Jan 21st, 2006, 5:23am » |
Quote Modify
|
It seems that Error Correcting Codes may help?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Game problem
« Reply #3 on: Jan 22nd, 2006, 8:44am » |
Quote Modify
|
The only thing I can think up is what I suggested in the thread Jock linked to. Use hamming codes, specifically with a minimum distance of 2K. However that doesn't directly translate to a minimum number of questions you need. (Nor in fact which questions, although that's an easier problem)
|
| « Last Edit: Jan 22nd, 2006, 8:46am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Game problem
« Reply #4 on: Jan 23rd, 2006, 4:44am » |
Quote Modify
|
I suppose it should be possible to find an approximation.
you need 2log(N) questions (i.e. bits of information) to find an answer if there aren't any lies.
Let's assume there are exactly K lies.
It would be sufficient to know which of the questions were lied to. Suppose you ask X questions. To find K lies among those X answers, you need distinguish the Choose(X, K) possible ways the lies are distributed.
So you need an additional 2log(Choose(X, K)) bits/questions.
This means X = 2log(N) + 2log(Choose(X, K))
Solve for X and you're done.
Accounting for the fact there may be fewer lies, shouldn't take a lot of adjustment.
|
| « Last Edit: Jan 23rd, 2006, 5:02am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print