The problem is: it may be a lot less complicated to get a bound first, but it is a lot slower and I don't want my solution to be like this:
Impressively complicated solution, but in practice:
I love it!
And in fact, their solution looks a lot more complicated to me than my solution. Also, my scenarios ensure that everyone knows what scenario they're in, because the only time I split into scenarios is if everyone knows about which scenario we are going into at the time of the split.
Scenario 5: If there is less than 6 people, then one of P1
know it, because they received a signal on night 18. Now if one person knows, then there are 5 people, and if 2 people know, then there are 4 people.
Night 25: Those that received a signal on night 18, that are P1
, send a signal.
Nights 26-29: The person that sent a signal on night 25, and all those that received a signal on one of the nights 25-now, send a signal. This ensures that if there are five people or less, everybody knows. If someone didn't receive a signal at all on nights 25-29, he knows that there are 6 people, if everyone received a signal, then we have just narrowed it down to either 4 or 5.
Night 30: All the P4
('s) send a signal. If one of the P4
's receives a signal, then that person knows that there are 5 people, and he tells the warden that on this night. This makes sure that either they are released or there are two possibilities: a) that there are 4 prisoners, one P4
, and there are 2 people that will send a signal the next night, or there are 5 prisoners, 2 P4
's, and 4 people will send a signal the next night. I will not split into scenarios here, because nobody would know which scenario they are in.
Night 31: All the P4
('s), and everybody who received a signal on night 30, send a signal. If there are 5 people, then everybody will receive a signal by now (or be P4
), and there will be 3 people of the 4 that sent a signal this night that received a signal, I will refer to these later. If there are four people, then there is 1 P4
, and either a) all four people received a signal on nights 30-31 or are P4
, or b) 3 people either received a signal on nights 30-31 or are P4
, and 1 person didn't receive a signal and they aren't P4
. This person goes tells the warden that there are 4 people.The one person that sent a signal this night, and received a signal this night, cannot tell that to the warden because to him, he could be one of the 3 people, and there could be 5 people.
Night 32: The three (that don't exist if there are 4 people) people mentioned above now know that there are 5 people, tell the warden that, and are released. If there are 4 people, nothing happens.
Night 33: Since it has come to this, there must be four people, because if there were 5 people, then there would have been the 3 people that told that to the warden. So now they go tell the warden that there are 4 people, and they are released. I have now decided on four people in less than 2 months, whereas the other strategy took over 10000 years!
If you spot an error in the above post, please say so, I thought this up in my head and this is the first time I have written (typed) it down.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.