Author |
Topic: alphabet guessing (Read 1870 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
alphabet guessing
« on: Jun 12th, 2005, 5:30am » |
 Quote  Modify
|
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?
|
| « Last Edit: Jun 12th, 2005, 8:32am by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: alphabet guessing
« Reply #1 on: Jun 12th, 2005, 9:09am » |
Quote Modify
|
A somewhat simpler version was discussed here.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: alphabet guessing
« Reply #3 on: Jun 12th, 2005, 9:44am » |
Quote Modify
|
on Jun 12th, 2005, 9:29am, 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 2k 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).
|
| « Last Edit: Jun 12th, 2005, 9:58am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: alphabet guessing
« Reply #4 on: Jun 12th, 2005, 12:00pm » |
Quote Modify
|
Well, the simplest solution seems to apply the solution to the first problem k times. Just remove one error at a time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: alphabet guessing
« Reply #5 on: Jun 15th, 2005, 7:59pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: alphabet guessing
« Reply #6 on: Jun 16th, 2005, 1:57am » |
Quote Modify
|
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)
|
| « Last Edit: Jun 16th, 2005, 2:24am 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: alphabet guessing
« Reply #7 on: Jun 16th, 2005, 2:51am » |
Quote Modify
|
It also seems that applying one-bit error correction k times doesn't actually work.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Earendil
Newbie
 
Gender:
Posts: 46
|
|
Re: alphabet guessing
« Reply #8 on: Jun 17th, 2005, 9:35am » |
Quote Modify
|
on Jun 12th, 2005, 12:00pm, 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.
|
| « Last Edit: Jun 17th, 2005, 9:42am by Earendil » |
IP Logged |
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: alphabet guessing
« Reply #9 on: Jun 17th, 2005, 2:11pm » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: alphabet guessing
« Reply #10 on: Jun 19th, 2005, 3:04pm » |
Quote Modify
|
on Jun 17th, 2005, 9:35am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: alphabet guessing
« Reply #11 on: Jun 19th, 2005, 3:53pm » |
Quote Modify
|
on Jun 19th, 2005, 3:04pm, 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 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: alphabet guessing
« Reply #12 on: Jun 20th, 2005, 12:58am » |
Quote Modify
|
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.
|
|
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