Each resident of Dot-town carries a red or blue dot on his (or her) forehead, but if he ever figures
out what color it is he kills himself. Each day the residents gather; one day a stranger comes and
tells them something—anything—non-trivial about the number of blue dots. Prove that eventually
every resident kills himself.
Comment: “Non-trivial” means here that there is some number of blue dots for which the
statement would not have been true.
Suppose there are R red dots and B blue dots in town. Then the R folks see B and R-1 dots, and conclude there are either B and R or B+1 and R-1 dots depending on their own, while the B folks by similar logic conclude there are either B and R or B-1 and R+1 dots.
If the non-trivial piece of information excludes either (B-1,R+1) or (B+1, R-1) then all the R or B folks (respectively) kill themselves because the info has excluded one of their two possibilities, leaving them with certain knowledge of their color.
If the info doesn't exclude either of these, then after the first day, everyone knows that nobody can exclude either situation.
In particular, each B knows that if the counts are indeed (B+1, R-1), then the R's are deciding between (B+1, R-1 and B+2, R-2) [and analogously opposite for each R]. If the info excludes (B+2, R-2), then each B knows by virtue of no deaths the previous night that (B+1, R-1) is not true after all, and so they know they are B's and suicide.
For every day that passes, B's and R's can extend this logic to (B+i, R-i), or to (B-i, R+i) as appropriate. But once B-i or R-i is zero, there are no longer two choices. At that point the logic all collapses and either all the B's or all the R's know their colors and kill themselves. The following day, the remaining people know they're all the other color and they too kill themselves, leaving nobody. The maximum time in days this town can survive is equal to the number of people.
|
|
Posted by Paul
on 2017-04-24 10:01:33 |
explanation (maybe not rigorous enough for proof)