There are three prisoners and a guard. The guard has an infinite sequence that is either all 1′s (e.g. 1111111111…) or it starts with a finite number of 1′s and eventually turns into 2′s (e.g. 1112222222…). The guard creates 3 bit sequences (i.e. composed entirely of 0′s and 1′s) such that the sum of the i’th bit in the 3 sequences is equal to the i’th element in his sequence (1 or 2).

He then gives each of the 3 prisoners one of the 3 bit sequences. Each prisoner sees only his own sequence and has to guess whether the guard’s sequence consists only of 1′s or whether it turns into 2′s eventually. Devise a method that will make sure the majority of the prisoners (i.e. at least 2) guess correctly.

This is a hard riddle – it took me a couple of days (wall-time) to solve, but it was definitely worth it. Be warned – a certain mathematical maturity is needed.

Thanks Haran for giving me this cool riddle!