Maths Olympiad Prep

Library / /3 of 299

Combinatorics Difficulty 4.9 AIME Prove it Iran

A circle divided into 2n2n arcs, we intend to write 0,1,,n10, 1, \dots, n-1 on these arcs such that each number is used exactly two times and for 0in10 \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,,2n10, 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+biaibi±(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=0n1(i+1)i=02n2(ai+bi)=i=02n1i    n(n+1)2n(2n1). \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,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.