Shortlist JBMO, 2008

Number theory Difficulty 4.7 AIME Prove it JBMO

Problem:

Integers $1, 2, \ldots, 2n$ are arbitrarily assigned to boxes labeled with numbers $1, 2, \ldots, 2n$ . Now, we add the number assigned to the box to the number on the box label. Show that two such sums give the same remainder modulo $2n$ .

Solution

Solution:

Let us assume that all sums give different remainders modulo $2n$ , and let $S$ denote the value of their sum.

For our assumption,
$S \equiv 0 + 1 + \ldots + 2n - 1 = \frac{(2n - 1) 2n}{2} = (2n - 1)n \equiv n \pmod{2n}$
But, if we sum, breaking all sums into its components, we derive
$S \equiv 2(1 + \ldots + 2n) = 2 \cdot \frac{2n(2n + 1)}{2} = 2n(2n + 1) \equiv 0 \pmod{2n}$
From the last two conclusions we derive $n \equiv 0 \pmod{2n}$ . Contradiction.

Therefore, there are two sums with the same remainder modulo $2n$ .

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

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