All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 The Dot-town Suicides (Posted on 2017-04-20)
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.

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 explanation (maybe not rigorous enough for proof) Comment 1 of 1
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

 Search: Search body:
Forums (0)