Pigeonhole and Extremal Arguments

A drawer holds red, blue and black socks. How many must you take, without looking, to be sure of a matching pair? Objects: socks drawn; boxes: the $3$ colors. Four socks in three boxes force two of one color. Three are not enough, since they could be one of each. So the answer is $4$ — and "three are not enough" is part of the answer, because "sure" means the smallest number that always works.

Among any $n + 1$ integers chosen from $\{1, \ldots, 2n\}$, two are consecutive. Boxes: $\{1, 2\}, \{3, 4\}, \ldots, \{2n - 1, 2n\}$ — $n$ boxes for $n + 1$ numbers, so two chosen numbers share a box, and numbers in the same box are consecutive. $\blacksquare$

Among any $n$ integers $a_1, \ldots, a_n$, some non-empty block $a_{i+1} + \cdots + a_j$ has sum divisible by $n$. Consider the partial sums $s_1 = a_1$, $s_2 = a_1 + a_2$, …, $s_n$. If one leaves remainder $0$ mod $n$, done. Otherwise $n$ sums fall into the $n - 1$ nonzero remainders, so two agree: $s_i \equiv s_j$ with $i < j$, and $s_j - s_i = a_{i+1} + \cdots + a_j$ is divisible by $n$. $\blacksquare$

Among $30$ people, at least $\lceil 30/7\rceil = 5$ were born on the same day of the week. If each of the $7$ days had at most $4$ people, there would be at most $28$ people.

Among any $6$ integers, two differ by a multiple of $5$. Boxes: the $5$ remainders on division by $5$. Six integers, five boxes: two share a remainder, and then their difference leaves remainder $0$, that is, it is a multiple of $5$. $\blacksquare$

Ten points lie in an equilateral triangle of side $3$. Prove two of them are at distance at most $1$. Boxes: lines parallel to the sides cut the triangle into $9$ equilateral triangles of side $1$. Ten points, nine pieces: two points lie in the same piece. The greatest distance between two points of a side-$1$ equilateral triangle is $1$ (the length of a side), so those two points are at most $1$ apart. $\blacksquare$

Numbers are placed at the vertices of a polygon so that each equals the average of its two neighbors. Prove they are all equal. Take the largest value $M$. Its two neighbors average to $M$ and are each at most $M$, so both equal $M$. Repeat around the polygon: all equal $M$. $\blacksquare$

A finite set of at least three points in the plane, no three on a line. Prove some three of them form a triangle containing no other point of the set. Take any two points $A, B$, and among the remaining points choose $C$ at the smallest distance from the line $AB$. Suppose some other point $X$ of the set lay in triangle $ABC$. Moving from $C$ toward the side $AB$ only brings a point closer to line $AB$, so $X$ would be strictly closer to $AB$ than $C$ — contradicting the choice of $C$. $\blacksquare$

Among the divisors of $n$ that are greater than $1$ (there is at least one, $n$ itself), let $d$ be the smallest. If $d$ were not prime, it would have a divisor $a$ with $1 < a < d$, and $a$ would also divide $n$ — a smaller divisor greater than $1$. So $d$ is prime. $\blacksquare$

Find all integer solutions of $x^2 = 2y^2$. If there is a solution with $x \ne 0$, take one with the smallest $|x| > 0$. Then $x^2$ is even, so $x = 2x_1$, giving $4x_1^2 = 2y^2$, so $y^2 = 2x_1^2$ and $y = 2y_1$; then $x_1^2 = 2y_1^2$, a solution with $0 < |x_1| < |x|$. Contradiction. The only solution is $(0, 0)$. $\blacksquare$

Prove the only integer solution of $x^2 + y^2 = 3z^2$ is $x = y = z = 0$. Suppose not. If $z = 0$ then $x^2 + y^2 = 0$ forces $x = y = 0$, so a non-zero solution has $z \ne 0$; choose one with $|z|$ as small as possible. Since $3 \mid x^2 + y^2$, both $x$ and $y$ are multiples of $3$ (Direct Proof, squares mod $3$). Then $9 \mid x^2 + y^2 = 3z^2$, so $3 \mid z^2$ and $3 \mid z$. Now $(x/3, y/3, z/3)$ is a solution with a smaller non-zero $|z|$. Contradiction. $\blacksquare$

Claim: among any $7$ integers, two have a sum or a difference divisible by $10$. Failed attempt: "use the $10$ remainders mod $10$ as boxes" — $7$ objects in $10$ boxes guarantees nothing. Right boxes: $\{0\}, \{5\}, \{1, 9\}, \{2, 8\}, \{3, 7\}, \{4, 6\}$ — six boxes for the remainders. Seven integers in six boxes: two land in the same box. If they have the same remainder, their difference is divisible by $10$. If their remainders are $r$ and $10 - r$, their sum is. $\blacksquare$ The boxes were built so that "same box" already means "the property holds".