, 2019

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
Let $\mathbb{N}=\{1,2,3, \ldots\}$ be the set of all positive integers, and let $f$ be a bijection from $\mathbb{N}$ to $\mathbb{N}$ . Must there exist some positive integer $n$ such that $(f(1), f(2), \ldots, f(n))$ is a permutation of $(1,2, \ldots, n)$ ?

Solution

Solution:
Answer: No
Consider the bijection $f$ defined by
$(f(1), f(2), f(3), f(4), \ldots)=(2,4,6,1,8,3,10,5,12, \ldots)$
which alternates between even and odd numbers after the second entry. (More formally, we define $f(n)=2n$ for $n=1,2$ , $f(n)=n+3$ for odd $n \geq 3$ and $f(n)=n-3$ for even $n \geq 4$ .) No such $n$ can exist for this $f$ as the largest number among $f(1), f(2), \ldots, f(n)$ is more than $n$ for all $n$ : for $k \geq 2$ , the maximum of the first $2k-1$ or $2k$ values is achieved by $f(2k-1)=2k+2$ . (Checking $n=1$ and $n=2$ is trivial.)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.