Applications of the Pigeonhole Principle

Existence (pigeonhole argument). For each index $i \in \{1, \dots, rs+1\}$ define

Both are well-defined positive integers, since the single-term subsequence $(a_i)$ is always available, giving $u_i \ge 1$ and $v_i \ge 1$. Claim: the map $i \mapsto (u_i, v_i)$ is injective on $\{1,\dots,rs+1\}$. Suppose $i < j$ are two distinct indices with $(u_i,v_i) = (u_j,v_j)$. Since the $a_k$ are all distinct, either $a_i < a_j$ or $a_i > a_j$.

• If $a_i < a_j$: take the increasing subsequence of length $u_i$ ending at position $i$ and append $a_j$ to it (valid since $i<j$ and $a_i < a_j$). This produces an increasing subsequence of length $u_i + 1$ ending at $j$, so $u_j \ge u_i+1 > u_i$, contradicting $u_j = u_i$.
• If $a_i > a_j$: symmetrically, append $a_j$ to the longest decreasing subsequence ending at $i$ to get a decreasing subsequence of length $v_i+1$ ending at $j$, forcing $v_j \ge v_i + 1$, contradicting $v_j = v_i$.

Either way we reach a contradiction, so the claim holds: the $rs+1$ pairs $(u_i,v_i)$ are pairwise distinct. Now suppose, for contradiction, that the theorem's conclusion fails: there is no increasing subsequence of length $r+1$ and no decreasing subsequence of length $s+1$. Then for every $i$,

so each pair $(u_i,v_i)$ lies in the finite set $\{1,\dots,r\} \times \{1,\dots,s\}$, a set of exactly $rs$ elements. But we have $rs+1$ indices $i$, each mapped to a distinct element of this $rs$-element set — impossible, since an injective function from an $(rs+1)$-element domain into an $rs$-element codomain cannot exist (this is precisely the Pigeonhole Principle in its function formulation: $rs+1 > rs$ forces a repetition, contradicting injectivity). This contradiction shows the assumption was false, so an increasing subsequence of length $r+1$ or a decreasing one of length $s+1$ must exist. $\blacksquare$

Sharpness (explicit extremal construction). Arrange the numbers $1$ through $rs$ into an $r \times s$ array of blocks as follows. Partition $\{1,\dots,rs\}$ into $r$ consecutive blocks of size $s$:

Define the sequence by listing $B_r$ in increasing order, then $B_{r-1}$ in increasing order, ..., then $B_1$ in increasing order — that is, blocks appear in decreasing order of their values, but each block internally is written increasing. Concretely the sequence is:

No increasing subsequence of length $r+1$: any strictly increasing subsequence can use at most one element from each block. Indeed, within a block the values are consecutive integers in increasing position order, but distinct blocks are arranged so that all values in an earlier-positioned block exceed all values in a later-positioned block; hence an increasing subsequence, reading left to right, must have strictly decreasing block index — impossible to repeat a block and impossible to increase in value while moving to a later (smaller-valued) block. Thus an increasing subsequence takes at most one entry per block, and there are only $r$ blocks, so its length is at most $r$. No decreasing subsequence of length $s+1$: within a single block of size $s$, the entries are already listed in strictly increasing order, so a strictly decreasing subsequence can use at most one element from each block (two elements from the same block are increasing, not decreasing, in position order). Moving between blocks, the block appearing earlier has strictly larger values than any later block, so decreasing subsequences may certainly jump blocks — but within any one block only one term can be picked. Since a decreasing subsequence can select at most $s$ elements per each of its chosen positions across blocks only if it stays inside a single block (as just shown at most $1$ per block) — we must bound differently: a decreasing subsequence corresponds to choosing at most one element from each block only fails to bound it by $s$; instead observe the correct bound directly: within a block the increasing order forces at most $1$ element per block for a decreasing run, and there are $r$ blocks total, which bounds decreasing runs by $r$, not $s$. Let us instead verify sharpness the standard way, symmetric to the first case. Re-examine: a decreasing subsequence may pick at most one element from each block, since inside a block values increase left-to-right. There are $r$ blocks, so naively decreasing subsequences have length at most $r$ — but we want the bound $s$, so let us instead pick at most one element per position within a block, across blocks, using the standard argument: fix a decreasing subsequence; any two of its terms lying in the same block would have to be decreasing while the block itself is increasing, forbidden — so it has at most one term per block, i.e. length $\le r$. That bounds decreasing subsequences by $r$, and by the symmetric argument on increasing ones we get length $\le s$ (since increasing subsequences can pick at most one term per "column" — the position-within-block index, of which there are $s$ values, because two terms in the same relative position of two different blocks lie in different blocks with the later block position having smaller values, so an increasing subsequence moving left to right must strictly increase in block-order which is only possible... ) This double-indexing is easiest to settle by re-deriving it cleanly via the standard grid model. Index each of the $rs$ positions by a pair $(p,q)$ with $p \in \{1,\dots,r\}$ (block number, listed in the sequence order $B_r,B_{r-1},\dots,B_1$, so $p=1$ means block $B_r$, ..., $p=r$ means block $B_1$) and $q \in \{1,\dots,s\}$ (position within the block, increasing). Assign to the entry at $(p,q)$ the value $V(p,q) = (r-p)s + q$. As $p$ increases (moving right across blocks in sequence order) the block contributes a smaller base value $(r-p)s$, while within a fixed $p$, increasing $q$ increases $V$.

• A strictly increasing subsequence in value, read in increasing sequence-position order, needs both index coordinates constrained: if two terms have the same $p$, then increasing $q$ gives increasing $V$, so we can increase within a block — length up to $s$ within one block. If we move to a later block (larger $p$), the base value drops by $s$ per step, more than the maximum possible gain of $(s-1)$ from varying $q$ within the new block, so values must decrease when $p$ increases. Hence an increasing subsequence must stay within a single block, giving length $\le s$.
• A strictly decreasing subsequence must, symmetrically, either move to a strictly larger $p$ (since within one block values only increase with $q$, so decreases can't happen for fixed $p$), giving at most one term per value of $p$, hence length $\le r$.

This matches the theorem's roles with $r$ and $s$ swapped from the sloppy pass above; to align exactly with the theorem statement (no increasing subsequence of length $r+1$, no decreasing of length $s+1$), take $r$ blocks each of size $s$ as originally set up, and read the bound as: increasing subsequences have length $\le s$ and decreasing subsequences have length $\le r$. To match the theorem's naming exactly, simply relabel: build the array with $s$ blocks of size $r$ instead. Concretely, partition $\{1,\dots,rs\}$ into $s$ blocks of size $r$, list the blocks in decreasing value order, each block increasing internally; then by the argument above, increasing subsequences (constrained to a single block of size $r$) have length at most $r$, and decreasing subsequences (at most one term per block, $s$ blocks) have length at most $s$. This is a sequence of exactly $rs$ distinct integers with no increasing subsequence of length $r+1$ and no decreasing subsequence of length $s+1$, proving sharpness. $\blacksquare$

Every positive integer $m$ can be written uniquely as $m = 2^{k} \cdot t$ with $k \ge 0$ and $t$ odd; call $t$ the odd part of $m$, written $\operatorname{odd}(m)$. For $m \in \{1,\dots,2n\}$, the odd part $\operatorname{odd}(m)$ is an odd number in $\{1,3,5,\dots,2n-1\}$, a set of exactly $n$ odd numbers. Define $f : S \to \{1,3,5,\dots,2n-1\}$ by $f(m) = \operatorname{odd}(m)$. The domain has $|S| = n+1$ elements and the codomain has $n$ elements, so by the Pigeonhole Principle (function formulation) $f$ is not injective: there exist distinct $a,b \in S$ with $f(a) = f(b) = t$ for some common odd $t$. Write $a = 2^{i} t$ and $b = 2^{j} t$ with $i \ne j$ (they must differ, since $a \ne b$ and both share the same odd part $t$, forcing different powers of $2$). Without loss of generality $i < j$; then

and since $j - i$ is a positive integer, $a \mid b$. $\blacksquare$