Week 1
Pigeonhole Principle
I decided to do some more research on the Pigeonhole Principle. It is also known as Dirichlet's box. This principle states that, given two natural numbers n and m with n > m, if n items are put into m pigeonholes, then at least one pigeonhole must contain more than one item. Another way of stating this would be that m holes can hold at most m objects with one object to a hole; adding another object will force one to reuse one of the holes, provided that m is finite. More formally, the theorem states that there does not exist an injective function on finite sets whose codomain is smaller than its domain.
The pigeonhole principle is an example of a counting argument which can be applied to many formal problems, including ones involving infinite sets that cannot be put into one-to-one correspondence. In Diophantine approximation the quantitative application of the principle to the existence of integer solutions of a system of linear equations goes under the name of Siegel's lemma.
The first statement of the principle is believed to have been made by Dirichlet in 1834 under the name Schubfachprinzip. In Italian too, the original name "principio dei cassetti" is still in use; in some other languages this principle is called the Dirichlet principle.
Week 2
The Monty Hall
The Monty Hall problem is a probability puzzle based on the American television game show Let's Make a Deal. The name comes from the show's host, Monty Hall. The problem is also called the Monty Hall paradox, as it is a veridical paradox in that the solution is counter intuitive.
A well-known statement of the problem was published in Parade magazine
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice? (Whitaker 1990)
It is assumed that the player prefers winning a car rather than a goat. Because there is no way for the player to know which of the two unopened doors is the winning door, most people assume that each door has an equal probability and conclude that switching does not matter. In fact, in the usual interpretation of the problem the player should switch—doing so doubles the probability of winning the car from 1/3 to 2/3. Switching is only not advantageous if the player initially chooses the winning door, which happens with probability 1/3. With probability 2/3, the player initially chooses one of two losing doors; when the other losing door is revealed, switching yields the winning door with certainty. The total probability of winning when switching is thus 2/3.
When the problem and the solution appeared in Parade, approximately 10,000 readers, including nearly 1,000 with Ph.D.s, wrote to the magazine claiming the published solution was wrong. Some of the controversy was because the Parade version of the problem is technically ambiguous since it leaves certain aspects of the host's behavior unstated, for example whether the host must open a door and must make the offer to switch. Variants of the problem involving these and other assumptions have been published in mathematical literature.
The standard Monty Hall problem is mathematically equivalent to the earlier Three Prisoners problem and both are related to the much older Bertrand's box paradox. These and other problems involving unequal distributions of probability are notoriously difficult for people to solve correctly, and have led to numerous psychological studies. Even when given a completely unambiguous statement of the Monty Hall problem, explanations, simulations, and formal mathematical proofs, many people still meet the correct answer with disbelief.
