Olympiad problems

Every positive integer has a unique representation $2^{a}m$ where $a\ge 0$ and $m$ is a positive odd integer. Write each of the $n+1$ chosen integers as $2^{a_i}{m}_i$ with $m_i$ odd. Since each chosen integer is at most $2n$ and is odd after removing all factors of $2$, each $m_i$ belongs to the set $\{1,3,5,\dots ,2n-1\}$, which has exactly $n$ elements. With $n+1$ odd parts among $n$ possible values, the pigeonhole principle gives two chosen integers sharing the same odd part: $x=2^{a}m$ and $y=2^{b}m$ for some odd $m$ and distinct exponents $a,b$. If $a<b$ then $x\mid y$; if $b<a$ then $y\mid x$.

For each index $k\in \{1,\dots ,mn+1\}$, let ${\mathrm{\ell }}_k$ be the length of the longest strictly increasing subsequence of $a_1,\dots ,a_{mn+1}$ that ends at $a_k$.

If ${\mathrm{\ell }}_k\ge m+1$ for any $k$, an increasing subsequence of length $m+1$ exists and we are done.

Otherwise ${\mathrm{\ell }}_k\in \{1,2,\dots ,m\}$ for all $k$. There are $mn+1$ indices and only $m$ possible values, so by the pigeonhole principle some $n+1$ indices $k_1<k_2<\cdots <k_{n+1}$ satisfy ${\mathrm{\ell }}_{k_1}={\mathrm{\ell }}_{k_2}=\cdots ={\mathrm{\ell }}_{k_{n+1}}=\mathrm{\ell }$.

We claim $a_{k_1}>a_{k_2}>\cdots >a_{k_{n+1}}$. Suppose for a contradiction that $a_{k_i}<a_{k_j}$ for some $i<j$. Then any strictly increasing subsequence of length $\mathrm{\ell }$ ending at $a_{k_i}$ can be extended by $a_{k_j}$ (which appears later in the sequence and is larger), giving ${\mathrm{\ell }}_{k_j}\ge {\mathrm{\ell }}_{k_i}+1=\mathrm{\ell }+1$. This contradicts ${\mathrm{\ell }}_{k_j}=\mathrm{\ell }$. Since the terms are distinct, the subsequence $a_{k_1},\dots ,a_{k_{n+1}}$ is therefore strictly decreasing, with length $n+1$.

Connect the midpoints of each pair of sides of the triangle. This subdivides it into four congruent equilateral triangles, each of side $1$. The five given points are distributed among these four smaller triangles (a point on a shared edge is assigned to either adjacent triangle). By the pigeonhole principle, at least one small triangle contains at least two of the five points.

It remains to note that the diameter of an equilateral triangle of side $1$ — the greatest distance between any two points in it or on it — equals $1$, since the three vertices are the farthest-apart pairs and each pair of vertices is distance $1$ apart. Hence the two points in the same small triangle are at distance at most $1$.

Consider the $N+1$ numbers $$\{0\cdot \alpha \}=0,\{\alpha \},\{2\alpha \},\dots ,\{N\alpha \},$$ where $\{x\}=x-\lfloor x\rfloor$ denotes the fractional part of $x$. All $N+1$ values lie in $[0,1)$. Partition $[0,1)$ into the $N$ subintervals $$[0,\frac{1}{N}),[\frac{1}{N},\frac{2}{N}),\dots ,[\frac{N-1}{N},1)\mathrm{.}$$ By the pigeonhole principle, two of the $N+1$ values fall in the same subinterval: say $\{r\alpha \}$ and $\{s\alpha \}$ with $0\le r<s\le N$ and $\mathrm{\mid }\{s\alpha \}-\{r\alpha \}\mathrm{\mid }<1\mathrm{/}N$.

Set $q=s-r$ and $p=\lfloor s\alpha \rfloor -\lfloor r\alpha \rfloor$. Then $1\le q\le N$ and $$\mathrm{\mid }q\alpha -p\mathrm{\mid }=\mid (s\alpha -\lfloor s\alpha \rfloor )-(r\alpha -\lfloor r\alpha \rfloor )\mid =\mathrm{\mid }\{s\alpha \}-\{r\alpha \}\mathrm{\mid }<\frac{1}{N}\mathrm{.}$$ Dividing both sides by $q$ gives ${\displaystyle \mid \alpha -\frac{p}{q}\mid <\frac{1}{qN}}$.

Let the ten integers be $a_1,\dots ,a_{10}$ and form the eleven partial sums $$S_0=0,S_k=a_1+a_2+\cdots +a_k(k=1,\dots ,10)\mathrm{.}$$ Each $S_k$ has a residue modulo $10$ in $\{0,1,\dots ,9\}$.

Case 1. $S_k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}10)$ for some $k\ge 1$. Then the non-empty subset $\{a_1,\dots ,a_k\}$ has sum divisible by $10$.

Case 2. $S_k\equiv ̸0(\mathrm{m}\mathrm{o}\mathrm{d}10)$ for all $k\ge 1$. Then $S_1,\dots ,S_{10}$ take values in $\{1,2,\dots ,9\}$, a set of only $9$ residues. Since there are $10$ sums, the pigeonhole principle gives $1\le i<j\le 10$ with $S_i\equiv S_j(\mathrm{m}\mathrm{o}\mathrm{d}10)$. Then $$a_{i+1}+a_{i+2}+\cdots +a_j=S_j-S_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}10),$$ so the non-empty subset $\{a_{i+1},\dots ,a_j\}$ has sum divisible by $10$.

In both cases a non-empty subset with the required property exists.

Fix any person $A$. Each of the other $5$ people is either acquainted with $A$ or not. By the pigeonhole principle, at least $\lceil 5\mathrm{/}2\rceil =3$ of them fall in the same category.

Case 1: $A$ is acquainted with $B_1,B_2,B_3$. If any two of $B_1,B_2,B_3$ are acquainted — say $B_1$ and $B_2$ — then $A,B_1,B_2$ are three mutually acquainted people. Otherwise $B_1,B_2,B_3$ are pairwise unacquainted, giving three mutually unacquainted people.

Case 2: $A$ is unacquainted with $B_1,B_2,B_3$. If any two of $B_1,B_2,B_3$ are unacquainted — say $B_1$ and $B_2$ — then $A,B_1,B_2$ are three mutually unacquainted people. Otherwise $B_1,B_2,B_3$ are pairwise acquainted, giving three mutually acquainted people.

In every case the required triple exists.

Let the $n$ integers be $a_1,\dots ,a_n$ and form the $n+1$ partial sums $$S_0=0,S_k=a_1+\cdots +a_k(k=1,\dots ,n)\mathrm{.}$$ These $n+1$ values have residues in $\{0,1,\dots ,n-1\}$, a set of $n$ elements.

If $S_k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$ for some $k\ge 1$, the subset $\{a_1,\dots ,a_k\}$ has sum divisible by $n$. Otherwise $S_1,\dots ,S_n$ all have non-zero residues; together with $S_0=0$ that is $n+1$ values in $n$ residue classes, so by the pigeonhole principle $S_i\equiv S_j(\mathrm{m}\mathrm{o}\mathrm{d}n)$ for some $0\le i<j\le n$. Since $i\ge 1$ is not guaranteed here, note that if $i=0$ then $S_j\equiv 0$, handled above; otherwise $1\le i<j\le n$ and $a_{i+1}+\cdots +a_j=S_j-S_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$, giving the required subset.

Each vertex of a simple graph on $n$ vertices has degree in $\{0,1,\dots ,n-1\}$. These are $n$ possible values for $n$ vertices, so if all degrees were distinct they would be exactly $\{0,1,2,\dots ,n-1\}$. But this is impossible: a vertex of degree $n-1$ is adjacent to every other vertex, which prevents any vertex from having degree $0$. Hence the $n$ degrees cannot all be distinct, and by the pigeonhole principle two vertices share a degree.

Partition $\{1,2,\dots ,2n\}$ into the $n$ complementary pairs $$\{1,2n\},\{2,2n-1\},\dots ,\{n,n+1\},$$ each of which sums to $2n+1$. The $n+1$ chosen integers are distributed among these $n$ pairs. By the pigeonhole principle two chosen integers belong to the same pair and therefore sum to $2n+1$.

Each lattice point $(x,y)$ belongs to exactly one of the four parity classes determined by the residues of $x$ and $y$ modulo $2$: $$(0,0),(0,1),(1,0),(1,1)\mathrm{.}$$ With $5$ points and only $4$ classes, the pigeonhole principle gives two points $(x_1,y_1)$ and $(x_2,y_2)$ in the same class: $x_1\equiv x_2$ and $y_1\equiv y_2(\mathrm{m}\mathrm{o}\mathrm{d}2)$. Their midpoint is $({\displaystyle \frac{x_1+x_2}{2}},{\displaystyle \frac{y_1+y_2}{2}})$, and both coordinates are integers because $x_1+x_2$ and $y_1+y_2$ are each divisible by $2$.