I don’t know much about the problem in question, but there’s a related open problem in number theory.
Suppose I am thinking of a positive integer from 1 to n. You know this and know n. You want to figure out my number but are only allowed to ask if my number is in some range you name. In this game it is easy to see that you can always find out my number in less than 1+log2 n questions.
But what if I’m allowed to lie k times for some fixed k (that you know). Then the problem becomes much more difficult. A general bound in terms of k and n is open.
This suggests to me that working out problems involving lying, even in toy models, can quickly become complicated and difficult to examine.
Are you familiar with the seemingly similar question about the prisoners, king, and coin? I don’t know the name, but it goes like this:
There are n prisoners in separate rooms, each with a doorway to a central chamber (CC) that has a coin. One by one, the king takes a random prisoner into the CC (no one else can see what is going on), and asks the prisoner if the king has brought all prisoners into the CC by now. The prisoner can either answer “yes” or “I don’t know”. If he says the former and is wrong, all prisoners are executed. If he’s right, they’re released.
If If he says “I don’t know”, he can set the coin to heads or tails. The king may turn over the coin after a prisoner leaves (and before he brings the next in), but he may only do so a finite k number of times in total. (This is a key similarity to the number of lies in the problem you describe).
The prisoners may discuss a strategy before starting, but the king gets to listen in and learn their strategy. So long as the game continues, every prisoner will be picked inifinte times (i.e. every prisoner can always expect to get picked again).
Is it possible for the prisoners to guarantee their eventual release?
The answer is yes, and there’s a known bound on how long it takes. (Got this from slashdot a long time ago.)
Edit: Found it. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
Edit2: This also serves as a case study in how to present a problem as succinctly as possible. The only thing I got wrong about its statement was that the king chooses the order of the prisoners going into the CC (rather than it being random), although given the constraint that each prisoner is eventually brought in infinite times, and the strategy must work all the time, I don’t think it changes the problem.
Maybe I wasn’t clear. The blockquoted part is (my phrasing of) the problem statement. In the slashdot thread (and this is all from memory), several correct, bounded solutions were posted. I’ll try to find the thread. (IIRC the original phrasing had a cup instead of a coin.)
The intuition behind the existence of a solution is that the prisoners can effectively send infinite one-bit messages between each other, while the king can only block a finite number of them, so they just need to choose a leader and run some “message accumulator” protocol that will reach a certain state when all prisoners are certain to have been in the CC.
Edit: Wow, that was actually easy to find. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
I don’t know much about the problem in question, but there’s a related open problem in number theory.
Suppose I am thinking of a positive integer from 1 to n. You know this and know n. You want to figure out my number but are only allowed to ask if my number is in some range you name. In this game it is easy to see that you can always find out my number in less than 1+log2 n questions.
But what if I’m allowed to lie k times for some fixed k (that you know). Then the problem becomes much more difficult. A general bound in terms of k and n is open.
This suggests to me that working out problems involving lying, even in toy models, can quickly become complicated and difficult to examine.
Are you familiar with the seemingly similar question about the prisoners, king, and coin? I don’t know the name, but it goes like this:
The answer is yes, and there’s a known bound on how long it takes. (Got this from slashdot a long time ago.)
Edit: Found it. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
Edit2: This also serves as a case study in how to present a problem as succinctly as possible. The only thing I got wrong about its statement was that the king chooses the order of the prisoners going into the CC (rather than it being random), although given the constraint that each prisoner is eventually brought in infinite times, and the strategy must work all the time, I don’t think it changes the problem.
Doesn’t your comment on Slashdot indicate that there is no solution?
Maybe I wasn’t clear. The blockquoted part is (my phrasing of) the problem statement. In the slashdot thread (and this is all from memory), several correct, bounded solutions were posted. I’ll try to find the thread. (IIRC the original phrasing had a cup instead of a coin.)
The intuition behind the existence of a solution is that the prisoners can effectively send infinite one-bit messages between each other, while the king can only block a finite number of them, so they just need to choose a leader and run some “message accumulator” protocol that will reach a certain state when all prisoners are certain to have been in the CC.
Edit: Wow, that was actually easy to find. Here’s the discussion that spawned it, and here’s the thread that introduces this problem, and here’s a comment with a solution. Apparently, the problem has a name it goes by.
This is the comment that provoked mine. Your link and this do seem to be solutions, though.
There are some comments I wish I could delete from slashdot … and this site, for that matter … such as the parent.