wu :: forums - Print Page


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

        riddles >> hard >> alphabet guessing
        
(Message started by: JocK on Jun 12^th, 2005, 5:30am)

Title: alphabet guessing
Post by JocK on Jun 12^th, 2005, 5:30am

I select a character out of the set of 26 characters {a, b, .. , z}. You have to guess the selected character by asking me yes/no questions. Obviously, you need 5 such binary questions to find out which character was selected provided I always answer your questions truthfully.

How many questions do you need when I am allowed to lie once?

Title: Re: alphabet guessing
Post by Barukh on Jun 12^th, 2005, 9:09am

A somewhat simpler version was discussed here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1116846660).

Title: Re: alphabet guessing
Post by towr on Jun 12^th, 2005, 9:29am

So how about if he can lie twice?

Title: Re: alphabet guessing
Post by JocK on Jun 12^th, 2005, 9:44am

on 06/12/05 at 09:29:17, towr wrote:

So how about if he can lie twice?

That was the follow-up question: How many questions do you need when I am allowed to lie n times?

You may want to try this first for the case of guessing between 2^k objects with k = {2, 3, 4}. When checking for n = 0, 1, 2, .. a very simple relationship between the required number of questions and k and N emerges.

For higher k-values this relationship breaks down however...

(which - even for just one allowed erroneous answer - makes the 26 characters guessing problem quite different from the guessing problem for 16 characters.)

So, decided not to remove this thread (wasn't aware of the fact that the 16 characters question was posted here before; thanks for mentioning Barukh).

Title: Re: alphabet guessing
Post by towr on Jun 12^th, 2005, 12:00pm

Well, the simplest solution seems to apply the solution to the first problem k times. Just remove one error at a time.

Title: Re: alphabet guessing
Post by TimMann on Jun 15^th, 2005, 7:59pm

Hmm. I wonder if you can reduce the number of check bits that would be needed in towr's method by observing that lying about the same bit more than once is not distinct from either lying or not lying about it. Maybe not -- I don't see offhand how to do it.

Title: Re: alphabet guessing
Post by towr on Jun 16^th, 2005, 1:57am

You can do so by using different hamming codes.
Put simply, you map each input string to a new codeword, in such a way that each codeword has a hammingdistance of at least 2n+1 to any other codeword. So given there are n errors or less, you know it belongs to the closest codeword.

Only I'm not sure you can get a mapping as nice as with at most one error (i.e. that certain bits immediately point out where, if at all, there is an error)

Title: Re: alphabet guessing
Post by towr on Jun 16^th, 2005, 2:51am

It also seems that applying one-bit error correction k times doesn't actually work.

Title: Re: alphabet guessing
Post by Earendil on Jun 17^th, 2005, 9:35am

on 06/12/05 at 12:00:05, towr wrote:

Well, the simplest solution seems to apply the solution to the first problem k times. Just remove one error at a time.

I) If the person lies always on the same question, you wont be able to detect which were the lies...

II) If you do it k+1 times, I think it doesn't work because for each possible result, there is a simmetrical result exchanging the number of lies the person used... For instance, if he lied 1 time in each of the k procedures, there is a simmetrical case, with equal results, in which he lied only once.

Title: Re: alphabet guessing
Post by Earendil on Jun 17^th, 2005, 2:11pm

I guess something slightly better would be the following:

I) You ask the first question until you've got the same answer n+1 times. After that, you are certain that the number of questions you asked less n+1 is the number of times he has lied, lets call it r. So he has n-r lies left

II) Ask the 2nd question until you obtain n-r+1 times the same answer... and so on...

Title: Re: alphabet guessing
Post by towr on Jun 19^th, 2005, 3:04pm

on 06/17/05 at 09:35:32, Earendil wrote:

I) If the person lies always on the same question, you wont be able to detect which were the lies...

What 'same' question?
Aside from that it wouldn't work anyhow, I don't think you understand what I meant. Repeating to process of adding parity bits doesn't entail repeating questions.

Title: Re: alphabet guessing
Post by Earendil on Jun 19^th, 2005, 3:53pm

on 06/19/05 at 15:04:54, towr wrote:

What 'same' question?
Aside from that it wouldn't work anyhow, I don't think you understand what I meant. Repeating to process of adding parity bits doesn't entail repeating questions.

I guess I got it all wrong but I still don't understand what's happening. I thought that when you said:

"Well, the simplest solution seems to apply the solution to the first problem k times. Just remove one error at a time."

You were saying something like: "do k binary searches". If that was right, then the person could always lie on the first question of each binary search. If you are applying the 'same solution', I thought it was always the same first question :P

Title: Re: alphabet guessing
Post by towr on Jun 20^th, 2005, 12:58am

The solution I was talking about was encoding the inputstring with single-error-correcting code

It takes five bits to find a letter, say 10011
then adding parity bits gives
10011 ->
__1_001_1 ->
101100111
A single error in this string can be found and corrected by checking the parity bits.

Repeating this process would only mean adding another set of parity bits (resulting from increasingly complicated questions)
101100111 ->
__1_011_00111 ->
0010011100111

But it doesn't work, so it's a moot point anyway.