March 18, 2009 at 13:55A difficult task about prisoners
They recently told me a super-task, it took several days to solve.
There are infinitely many prisoners (countable number), numbered by natural numbers. Each prisoner knows all the numbers, including his own. Prisoners are able to think infinitely quickly, and they have infinitely much memory. First, they have time to discuss the algorithm.
They are arranged in order, so that the first looks in the back of the second, the second in the back of the third, etc. Caps of two colors are put on them at the same time. Each prisoner sees what caps are worn on prisoners with large numbers (the first sees all caps except his own, the second sees everything except his own and the first, etc.). They no longer exchange any information. Further, each of them must simultaneously say with everyone what kind of cap it is on. Whoever does not guess is shot. How to make sure that only a finite number of prisoners are shot?
PSThere is not enough karma to move to the "Entertaining Tasks" blog. Thanks for the karma, moved to the blog "Entertaining puzzles."
UPD Solution in the comments .
There are infinitely many prisoners (countable number), numbered by natural numbers. Each prisoner knows all the numbers, including his own. Prisoners are able to think infinitely quickly, and they have infinitely much memory. First, they have time to discuss the algorithm.
They are arranged in order, so that the first looks in the back of the second, the second in the back of the third, etc. Caps of two colors are put on them at the same time. Each prisoner sees what caps are worn on prisoners with large numbers (the first sees all caps except his own, the second sees everything except his own and the first, etc.). They no longer exchange any information. Further, each of them must simultaneously say with everyone what kind of cap it is on. Whoever does not guess is shot. How to make sure that only a finite number of prisoners are shot?
PS
UPD Solution in the comments .