There are 100 soldiers standing in a line wearing a red or blue cap. Each one can see the color of the caps of all those standing before them, but nothing else.
A commander starts from the end of the line, asking the color of the cap of each person. The goal is to get a maximum number of right answers. Recall that they can only see the color of the caps of those in front of them, and can hear the answer to the questions of the commander.
All the soldiers together can plan a strategy beforehand. They have no control on what color cap they will get, and they can not see the color of their own caps.
a) Design a strategy so that at least 50 of them will get the right answer.
b) Design a strategy so that at least 99 of them get the right answer.
Previous Puzzle Solution:
Kshitij Sodani, a class X student of Delhi Public School, Gurgaon, has given a correct answer. Congratulations Kshitij, he wins an Amazon voucher of Rs. 500
a) the soldier standing at the end of the line will say the color which has higher number of caps in front of him (99 is odd so there can be only 1 color satisfying this). The other 99 soldiers will repeat that colour. This way at least ceil(99/2)=50 of them will get the right answer.
(Another Simpler Solution: A soldier who is at an even position will simply shout the color of the cap of the person just in front of him, and the person in front of him repeats)
(b) The soldier standing at the end of the line will say blue if there is an odd number of people ahead of him wearing blue caps. In the other case he will say red. By hearing the answers to the previous soldiers the soldier i (ith from beginning of line) knows the parity of the number of blue caps in range 1 to i then he can tell the answer since he can know the parity in the range 1 to i-1 by just looking. He will say blue if the two parities are different and red if the two parities are the same. This way the soldiers 1 to 99 are guaranteed to have correct answers.