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.
Week 3 Cantor's Diagonal Argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began.
The diagonal argument was not Cantor's first proof of the uncountability of the real numbers; it was actually published much later than his first proof, which appeared in 1874. However, it demonstrates a powerful and general technique that has since been used in a wide range of proofs, also known as diagonal arguments by analogy with the argument used in this proof. The most famous examples are perhaps Russell's paradox, the first of Gödel's incompleteness theorems, and Turing's answer to the Entscheidungsproblem.
Week 4 Game Theory
Game theory is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, engineering, political science, international relations, computer science (mainly for artificial intelligence), and philosophy. Game theory attempts to mathematically capture behavior in strategic situations, in which an individual's success in making choices depends on the choices of others. While initially developed to analyze competitions in which one individual does better at another's expense (zero sum games), it has been expanded to treat a wide class of interactions, which are classified according to several criteria. Today, game theory is a sort of umbrella or 'unified field' theory for the rational side of social science, where 'social' is interpreted broadly, to include human as well as non-human players (computers, animals, plants)" (Aumann 1987).
Traditional applications of game theory attempt to find equilibria in these games. In an equilibrium each player of the game has adopted a strategy that they are unlikely to change. Many equilibrium concepts have been developed (most famously the Nash equilibrium) in an attempt to capture this idea. These equilibrium concepts are motivated differently depending on the field of application, although they often overlap or coincide. This methodology is not without criticism, and debates continue over the appropriateness of particular equilibrium concepts, the appropriateness of equilibria altogether, and the usefulness of mathematical models more generally.
