Originally posted by iamatigerIt also has to have the property that it will halt.
The solution merely needs to have the property that it will not halt until all prisoners have been chosen.
A stratetegy that had the property you name but not the property of halting would be incorrect.
For example, a strategy in which it is initially decided that the exclamation will never be made has the property that it will not halt until all prisoners have been chosen, and the additional property that it will not halt. That strategy would be incorrect.
It is the halting property that tojo doubts, not the property that if it halts, all prisoners will have been chosen. He remains unconvinced that given an infinite number of repetitions, each prisoner will certainly be chosen. Which is to say, he remains unconvinced that a fair coin is guaranteed to eventually land heads. He is not doubting that if your experiment terminates, you will have seen a heads -- he is doubting that it is guranteed to terminate.
The prisoners design that, for each 5 days, a different k cycle will be held. In it, only prisoner k will be able to turn on the light, and the next stage will be k+1. Any prisoner who comes in that stage and sees the light on adds prisoner k to their list. On the 5th day, the light is turned off and the next stage begins. When one prisoner has all other s in his list, game over. However, this is not optimal.
There is the simple solution of letting one be the counter and the others turn on the light when it is off and they haven't turned it yet, that is much better.
Edit: Oh, I saw Xanthos's solution. The first user to go to the room twice is the counter. That improves it - a lot.
Edit 2😲ops, it doesn't work. Unless we design some threshold, "people can't turn on the light until some days are passed".
How about 29?
Originally posted by fetofsThe original question doesn't allow for a prisoner knowing what number visitor he is to the room.
The prisoners design that, for each 5 days, a different k cycle will be held. In it, only prisoner k will be able to turn on the light, and the next stage will be k+1. Any prisoner who comes in that stage and sees the light on adds prisoner k to their list. On the 5th day, the light is turned off and the next stage begins. When one prisoner has all other s in ...[text shortened]... me threshold, "people can't turn on the light until some days are passed".
How about 29?
Originally posted by XanthosNZAs I read his solution, I think he means that the k-values are assigned during collaboration.
The original question doesn't allow for a prisoner knowing what number visitor he is to the room.
Just as the counter in the main solution is designated, it is designated that:
Prisoner A will be k = 1 and can only flip on days 1, 2, 3, 4, 5;
Prisoner B will be k = 2 and can only flip on days 6, 7, 8, 9, 10;
Prisoner C will be k = 3 and can only flip on days 11, 12, 13, 14, 15;
and so on, repeating with A again after the first 5N days have been assigned.
The prisoners don't just flip once but every time they are picked in their assigned days. Eventually each prisoner will be picked on one of his given days and another will be picked to view his flip (provided the guard doesn't always wait more than 5 days between picking - which is the main flaw in this system.)
I think his solution works given an upper bound of 5 days on how long the guard may delay the next pick, but it seems unnecessarily extravagant and certainly less efficient. I don't see what value comes from the cycle scheme, other than eliminating the need for a designated counter, which is kind of interesting.
Dr. S
P.S. Actually, I think there is another flaw. Between each 5-day period, there needs to be another 5-day period in which the switch is turned off by everybody who enters.
Originally posted by DoctorScribblesIn the last day the person has to turn off the lights. But if the problem doesn't allow counting the days...
As I read his solution, I think he means that the k-values are assigned during collaboration.
Just as the counter in the main solution is designated, it is designated that:
Prisoner A will be k = 1 and can only flip on days 1, 2, 3, 4, 5;
Prisoner B will be k = 2 and can only flip on days 6, 7, 8, 9, 10;
Prisoner C will be k = 3 and can only fl ...[text shortened]... e needs to be another 5-day period in which the switch is turned off by everybody who enters.
ok so if the prisoners are meeting to discuss the strategy they will know exactly how many prisoners there are, therefore by the end of the meeting N will be known...
... the adopting the strategy someone sugested on the first page whereby the prisoner will flick the switch only if it is the first time he has encountered it and it is in the UP position... one prisoner is designated at hte start to count the number of times he finds the switch in the DOWN position until he reaches the number N which is known.