# Recitation 16

In section C, I proved that there are the set of all prime numbers is infinite. The proof is a proof by contradiction Suppose there are only finitely many primes, say p_1, \ldots, p_n. Consider any prime factor of N = p_1\cdot\ldots\cdot p_n + 1. This prime factor must be one of those p_k. However, if we divide N by p_k, we always have a residue 1, which is a contradiction.

In section D, I presented two puzzles.

• n prisoners are arrested for a crime, but the jail is full and the jailer has nowhere to put them. He eventually comes up with the solution of giving them a puzzle so if they succeed they can go free but if they fail they are executed. Each prisoner is assigned a random hat, either red or blue, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be “red” or “blue”. If the word matches their hat color they are released, if not, they are killed on the spot. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, all prisoners will definitely survive except one whom has a 50/50 chance of survival. What is the plan to achieve the goal?
• In this variant, a countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?

For solutions and other variants, please refer to Prisoners and hats puzzle.