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…

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.

Thanks Haran for giving me this cool riddle!

A cute and easy algorithmic riddle.

You have an array of N bit strings each of length M. You know that there is at least one element that appears more than N/8 times in the array. Using O(M+log(N)) memory and O(NM) time, find such an element.

An Easier Version

Well, its actually almost exactly the same, but solve the above riddle in case there is an element that appears more than N/2 times in the array. I managed to find 3 distinct solutions to this easier variation, but only one of which generalizes easily.

Thanks Nemo for giving me this riddle!