#5 Pigeonhole Principle I

There are \(12\) months and \(13\) people. By the pigeonhole principle, some month contains at least two birthdays.

The boxes are last digits \(0,1,\ldots,9\). There are \(11\) numbers, so two fall into the same box.

Assume no color appears three times. Then each color appears at most \(2\), so there are at most \(4\) socks, but we have \(5\). Contradiction.

There are \(n\) residues modulo \(n\). Among \(n+1\) numbers, two have the same residue. Their difference is divisible by \(n\).

Pairs: \((1,10),(2,9),(3,8),(4,7),(5,6)\). Six numbers are chosen and there are five pairs, so one pair is fully chosen. Its sum is \(11\).

There are \(8\) residue classes. If each contains at most \(2\) numbers, the total is at most \(16\), but there are \(17\). Hence some class contains at least \(3\).

Each person has \(0\) to \(5\) acquaintances. If someone has \(0\), no one has \(5\); if someone has \(5\), no one has \(0\). Thus at most \(5\) values are possible for \(6\) people. By pigeonhole, two values coincide.

Each number has the form \(2^k m\), where \(m\) is odd. There are only \(9\) possible odd parts in \(1,\ldots,18\). Among \(10\) chosen numbers, two have the same odd part. Then they are \(2^a m\) and \(2^b m\), and the smaller divides the larger.

There are \(100\) residues modulo \(100\). Among \(101\) integers, two have the same residue, so their difference is divisible by \(100\).

There are \(10\) pairs, each with sum \(21\). Since \(11\) numbers are chosen, one pair is fully chosen.

After dividing into \(4\) unit squares, \(5\) points force two points into one small square. The distance between any two points in a unit square is at most its diagonal \(\sqrt{2}\).

Let \(s_i\) be the sum of the first \(i\) numbers. If some \(s_i\) is divisible by \(10\), done. Otherwise the \(10\) partial sums have only \(9\) nonzero residues, so two have the same residue. Their difference is the sum of a consecutive block divisible by \(10\).

Consider \(s_1,\ldots,s_n\). If some \(s_i\equiv0\pmod n\), the first \(i\) numbers work. Otherwise all \(s_i\) have one of \(n-1\) nonzero residues. Two sums have the same residue; their difference is the sum of a nonempty consecutive block and is divisible by \(n\).

There are \(6\) boxes of residues: \(0\), \(5\), and opposite residue pairs. Seven numbers put two in the same box. If their residues are equal, the difference is divisible by \(10\). If opposite, the sum is divisible by \(10\).

Each point has parity type \((x\bmod2,y\bmod2)\), only \(4\) types. Among \(5\) points, two have the same type. Then the sums of their \(x\)-coordinates and \(y\)-coordinates are even, so the midpoint has integer coordinates.

Choose a person \(A\). Among the other \(5\), either \(3\) are acquainted with \(A\), or \(3\) are not. In the first case, if among those three there is an acquainted pair, together with \(A\) they form three mutual acquaintances; if not, those three are mutual strangers. The second case is analogous: if among three strangers to \(A\) there is a stranger pair, together with \(A\) they form three mutual strangers; otherwise those three are mutual acquaintances.

Join the midpoints of the sides to obtain \(4\) small equilateral triangles of side \(1\). Five points force two into one small triangle. The distance between any two points in such a triangle is at most \(1\).

There are \(50\) pairs of consecutive numbers. Since \(51\) numbers are chosen, one pair is fully chosen. These two numbers are consecutive.

There are \(5\) residues modulo \(5\). Among \(6\) integers, two have the same residue, so their difference is divisible by \(5\).

There are \(2^{10}-1=1023\) nonempty subsets. Any subset sum lies between \(1\) and \(1000\), so there are at most \(1000\) possible sums. By pigeonhole, two different nonempty groups have the same sum.

There are \(1023\) nonempty subsets. Their sums lie from \(1\) to \(990\), at most \(990\) possible sums. Thus two different nonempty subsets have equal sum. Remove their common elements. The remaining parts still have equal sums; they are not both empty, otherwise the original subsets were equal. Hence we get two nonempty disjoint groups with equal sum.

Choose any person \(A\). Among the other \(9\), each is either acquainted with \(A\) or not. There are two boxes: acquaintances and strangers. By the strengthened pigeonhole principle, one contains at least \(\lceil9/2 ceil=5\) people. Thus \(A\) has \(5\) acquaintances or \(5\) strangers.

List the numbers in any order and apply the partial-sum lemma to this sequence of length \(n\). We get a nonempty consecutive block whose sum is divisible by \(n\). This block is a subset of the chosen numbers.

For each number \(a_i\), write \((u_i,d_i)\), where \(u_i\) is the maximum length of an increasing subsequence starting at \(a_i\), and \(d_i\) the maximum length of a decreasing one. If there is no monotone subsequence of length \(4\), then \(u_i,d_i\in\{1,2,3\}\), only \(9\) pairs. Among \(10\) numbers, two pairs coincide; let \(iu_j\), contradiction. If \(a_i>a_j\), similarly \(d_i>d_j\). Contradiction.