Prove that every convex polyhedron has at least two faces with the same number of edges.
Solution
A polyhedron has only finitely many faces. Some faces, among all of them, must have the maximal number of edges, say \(M.\) Take one of them and examine the \(M\) distinct faces adjacent to it along each of those edges. A face must have at least three edges, and at most \(M\) since \(M\) is maximal, so each of those \(M\) adjacent faces has either \(3\) or \(4\) or … or \(M\) edges itself. By the pigeonhole principle, at least two faces must have the same number of edges.
Stephen New
At a round-robin tournament each player plays every other player exactly once. During such a tournament, show that there must be some player in the unfortunate position that every other player either beat them, or beat someone else who beat them.
Solution
Select a player who lost the most number of games. Without loss of generality, suppose their name in Alvin. I claim Alvin is the unfortunate person. For indeed if, to the contrary, Alvin were not this person, there must be some other player, Brett, who not only lost to Alvin, but also lost to everyone who beat Alvin. This means Brett would have lost strictly more games than Alvin, which contradicts Alvin’s defining characteristic: that he is the one who lost the most games.
Stephen New
A finite number of polygons lie in the plane. Each pair of polygons shares at least one common point. Show that there is a line which intersects every polygon.
Solution
Suppose there are \(n\) polygons \(P_1, P_2, \dotsc, P_n\). Impose a coordinate system on the space, choose one of the coordinate axes, and for each polygon \(P_i\) let \([a_i, b_i]\) be the closed interval on the chosen axis on to which \(P_i\) projects.
Let \(a_r\) denote the right-most (max) of all the left-endpoints \(a_i\), and let \(b_\ell\) denote the left-most (min) of all the right-endpoints \(b_i\). Since the polygons \(P_\ell\) and \(P_r\) overlap, the intervals \([a_\ell, b_\ell]\) and \([a_r, b_r]\) must also overlap, and so \(a_r \leq b_\ell\). More importantly, \(a_i \leq a_r \leq b_\ell \leq b_i\) for every polygon \(P_i\)—which is to say that any point between \(a_r\) and \(b_\ell\) will be contained in every projection \([a_i, b_i]\). Choose such a point. The line through this point perpendicular to the axis will interest every polygon.
Putnam and Beyond
Prove that it is impossible to dissect a cube into finitely many smaller cubes, no two of which are the same size.
Solution
Suppose not! Suppose to the contrary that such a dissection into finitely many cubes exists. Consider a single square face of the cube. The dissection of this cube into smaller cubes will admit a dissection of this square into finitely many smaller squares.
Consider the smallest of these squares. This smallest square cannot lie along any edge of the face square; otherwise it would be adjacent to either (1) two edges of larger squares, or (2) one edge of a larger square and an edge of the face square, and this would force a square of equal or lesser area to exist in the “alley” between these two edges. So the smallest square is surrounded entirely by larger squares. Consider the small cube of which this smallest square is a face. Within the dissection of the cube this small cube is surrounded by larger cubes. Like the “alley” in the two-dimensional case, this small cube has a “corridor” above it that could only be filled by smaller cubes. This tiling of smaller cubes admits a dissection of a square face of our small cube into squares …
This process repeats indefinitely, giving us an ever-growing number of cubes in the dissection of our original cube, contradicting the finiteness supposed about the dissection.
Putnam and Beyond (Putnam 1965)
At a party assume that no boy dances with all the girls, but each girl dances with at least one boy. Prove that there are two girl-boy couples \(gb\) and \(g’b’\) such that \(g\) dances with \(b\) and \(g'\) dances with \(b',\) but \(b\) does not dance with \(g’,\) and \(g\) does not dance with \(b'.\)Solution
Among all the boys, there must be some boy who dances with a maximal number of girls; let \(B\) be that boy. Since no boy dances with all girls, there must be some girl \(G'\) who \(B\) does not dance with. Each girl dances with at least one boy though, so let \(B'\) be any one boy who dances with \(G'.\)
Since \(B\) dances with a maximal number of girls, he has danced with at least as many girls as \(B',\) and since \(B'\) dances with at least one girl \(B\) doesn’t, namely \(G',\) there must be some other girl \(G\) who dances with \(B\) but not with \(B'.\)
The couples \(GB\) and \(G'B'\) satisfy the requirements.