$\textbf{Prisoners' Problem}$
One hundred prisoners will be lined up. Each one will be assigned either a red hat or a blue hat. No one can see the color of his or her own hat. However, each person is able to see the color of the hat worn by every person in front of him or her. That is, for example, the last person in line can see the colors of the hats on $99$ people in front of him or her; and the first person, who is at the front of the line, cannot see the color of any hat. Beginning with the last person in line, and then moving to the $99^{th}$ person, the $98^{th}$, etc., each will be asked to name the color of his or her own hat. He or she can only answer "red" or "blue". If the color is correctly named, the person lives; if not, the person is shot dead on the spot. Everyone in line is able to hear all the responses but not the gunshots. Before being lined up, the $100$ prisoners are allowed to discuss a strategy aiming to save as many of them as possible. How many people can be saved if they can agree on a good strategy?
As a more challenging question, what if the hats can have $100$ known different colors instead of $2$?
$\textbf{Answer}$
Regardless of the number of colors ($2$ or $100$), every one except the last person in line can be surly saved. Whether the last one can be saved or not is by chance.
$\textbf{Analysis}$
This is a remainder problem. Let's start by analyzing the case of two colors with an intuitive explanation and then using the remainder method. The remainder method will then be used to solve the multi-color scenario.
Let red indicate "an odd number" and blue indicate "an even number". Then the last person can say "red" if he sees the total number of red hats in front of him is odd, and say "blue" if the total number is even. He cannot save himself for sure, but everyone else can then figure out the color of his hat. For example, assuming the last person announce "red", then the $99^{th}$ can also count the number of red hats in front of him. If it is an even number, then his hat must be red. He can then say "red" to save himself. Meanwhile, everyone else will know the number of remaining red hat will be even. Otherwise, if the $99^{th}$ person see an odd number of red hats in front of him, then his hat must be blue. He can say "blue" to save himself and let everyone know the number of remaining red hats is still odd. This process can continue till the first person in line.
The essence of the previously described method is that "my value" can be computed by "subtracting" the "sum of the values before me" (observed by me) from the "sum of the values up to me" (announced by the person behind me). This is exactly what the remainder method can do.
Let red color be $1$ and blue color be $0$. These two numbers are the two possible remainders when the divisor is $2$ (because we have two colors here). Then, the problem becomes this: everyone is randomly assigned a number of either $1$ or $0$, and tries to guess own number.
In this case, the last person can sum all the previous numbers and announce the remainder of this sum divided by $2$ which must be either $0$ or $1$. Whether this remainder happens to match his own assigned number is entirely be chance, but everyone else can figure out his or her number from there. Readers should try a few examples to see how this method works.
Regardless of the number of colors, this remainder method always work. In the case of $100$ different colors, we can assign a value from $0$ to $99$ for each of them. These numbers are all the possible remainders when the divisor is $100$.
$\textbf{Note}$
The remainder method is a powerful and simple tool. It also has a wide range of applications in solving brain teasers as well as mathematical problems. A good introductory book is Modular Arithmetic in the Math All Star series.