wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Interesting Game problem
        
(Message started by: lexandyacc on Jan 21^st, 2006, 2:43am)

Title: Interesting Game problem
Post by lexandyacc on Jan 21^st, 2006, 2:43am

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.

Title: Re: Interesting Game problem
Post by Barukh on Jan 21^st, 2006, 5:23am

It seems that [hide]Error Correcting Codes[/hide] may help?

Title: Re: Interesting Game problem
Post by JocK on Jan 21^st, 2006, 5:38am

The case n = 26 was discussed in the hard forum half a year ago:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1118579442

but didn't result in a solution...

Title: Re: Interesting Game problem
Post by towr on Jan 22^nd, 2006, 8:44am

The only thing I can think up is what I suggested in the thread Jock linked to. Use [hide]hamming codes, specifically with a minimum distance of 2K[/hide]. 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)

Title: Re: Interesting Game problem
Post by towr on Jan 23^rd, 2006, 4:44am

I suppose it should be possible to find an approximation.
you need ²log(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 ²log(Choose(X, K)) bits/questions.
This means X = ²log(N) + ²log(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.