Maths Olympiad Prep

Library / Iranian Mathematical Olympiad /2 of 270

Iranian Mathematical Olympiad

Combinatorics Difficulty 4.9 AIME Prove it Iran

A circle divided into 2n2n arcs, we intend to write 0,1,…,n−10, 1, \dots, n-1 on these arcs such that each number is used exactly two times and for 0≤i≤n−10 \le i \le n-1 from one direction there are exactly ii arcs between two arcs such that ii is written on them. Prove that this is impossible for n=1399n = 1399.

Solution

We number the arcs with 0,1,2,…,2n−10, 1, 2, \dots, 2n - 1, clockwise and assume that the arcs with numbers aia_i and bib_i have ii written on them. By the problem's assumption
ai+bi≡ai−bi≡±(i+1)≡i+1(mod2). a_i + b_i \equiv a_i - b_i \equiv \pm(i + 1) \equiv i + 1 \pmod{2}.
Then by adding up these equalities modulo 22 we have
∑i=0n−1(i+1)≡∑i=02n−2(ai+bi)=∑i=02n−1i  ⟹  n(n+1)2≡n(2n−1). \begin{align*} \sum_{i=0}^{n-1} (i+1) &\equiv \sum_{i=0}^{2n-2} (a_i + b_i) = \sum_{i=0}^{2n-1} i \\ &\implies \frac{n(n+1)}{2} \equiv n(2n-1). \end{align*}
The number 13991399 does not satisfy the last equation and this concludes the proof. ■

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.