Competition problem — Combinatorics

Library / /18 of 61

Combinatorics Difficulty 5.3 AIME, harder Prove it Ibero-American Mathematical Olympiad

Problem:
Let $A$ , $B$ be two sets of $N$ consecutive integers. If $N=2003$ , can we form $N$ pairs $(a,b)$ with $a \in A$ , $b \in B$ such that the sums of the pairs are $N$ consecutive integers? What about $N=2004$ ?

Solution

Solution:
Without loss of generality, let $A = B = \{1, 2, \ldots, N\}$ —if we have a solution for $A = \{a+1, a+2, \ldots, a+N\}$ and $B = \{b+1, b+2, \ldots, b+N\}$ , then subtracting $a$ from every element of $A$ and $b$ from every element of $B$ gives a solution for $A = B = \{1, 2, \ldots, N\}$ .

Suppose the sum set is $(m+1), (m+2), \ldots, (m+N)$ . It has sum $N(2m + N + 1)/2$ and $A$ and $B$ each have sum $N(N+1)/2$ , so we must have $2m = N + 1$ , hence $N$ must be odd. So we cannot do it for $N = 2004$ .

Suppose $N = 2M + 1$ , take the pairs $(1, M+1), (3, M), (5, M-1), \ldots, (2M+1, 1), (2, 2M+1), (4, 2M), \ldots, (2M, M+2)$ .

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.