Here’s an interesting mind bender for you (do note that this question is used in a lot of job interviews) –
A warlord has captured 1000 villagers, and has decided to put their wits to test. He has put 4 different coloured hats (say Red, Blue, Black and White) on these thousand villagers and arranged them randomly in a long queue. The arrangement of this queue is such that each villager can see all the villager’s hats in front of him, but he cannot see the villagers behind him.
Each of them now have to guess what colour their hat is. If it is the right colour then the villager is allowed to live and is freed, if not … then let’s just say he won’t be having any more headaches.
The villagers are allowed to discuss as a group to decide on a protocol (an algorithm of sorts) to decide how to call the colours so that the maximum no. of villagers survive. What is this algorithm and how many villagers will survive?
Hint: The title of the post
Taken from Wikipedia,
A parity bit is a bit that is added to ensure that the number of bits with the value one in a set of bits is even or odd. Parity bits are used as the simplest form of error detecting code.
The villagers have to use the concept of parity in their answers. Instead of taking a guess at what colour his hat is, the last villager is the parity bit. His answer gives an indication to everyone else in the queue as to what could be their colours. How? Here is so –
Each colour is denoted a no. (Red=1, Blue=2, Black=3, White=4). Since the last man can see all the hats in front of him, he takes a total of all the number before him and does an operation (total mod 4). This is the parity (or the error-correction answer). Now the man in front of him can see all the hats (except his of course) and also knows this value error-correction value. What he has to do is do the same operation for all the hats in front of him, and subtract that value from the previous mod. That’s the colour of his hat.
The cool thing about this is that even if there is one fool of a villager who miscalculates, the villager next to him can detect this error and can correct it immediately.
Now, where would we be using this? (In other words, why did I bother with this problem?)
Networks! Computer networks use the concept of parity bit to detect transmission errors for quite some time now (have you ever faced that pesky CRC error? That’s your parity bit right there).
Good Explanation Kidakaka.
Thanks Harshad!
The 1st thing I thought of when I noticed this problem was of timing sync bits (or delimiters) that are added to digital signals used in computer networks. How do you tell that a frame has finished, using a known sequence and have an escape code to indicate the occurrence of delimiter.
Fantastic solution….when I read the problem I somehow automatically neglected the first part and decided the problem to be “what should the villagers do to save the maximum number of people and what is the maximum number of people that can be saved”. :-) As they say, understand the problem before proposing a solution….
Thanks Rajat. I thought that it brings out the beauty of the parity bit concept very nicely.