Warm Up
(All-Russian Mathematical Olympiad 2014 Grade 9 Day 1 P1, AoPS, proposed by S. Berlov) On a circle, there are \(99\) positive integers. If \(a, b\) are any two neighbouring numbers on the circle, then \(a - b\) is equal to \(1\) or \(2\) or \( \frac{a}{b}=2 \). Prove that there exists a natural number on the circle that is divisible by \(3\).
Click here for the spoiler!
- Show that if none of the numbers on the circle is divisible by \(3\), then all the numbers on the circle are congruent to either \(1\) or \(2\) modulo \(3\).
- Using that \(99\) is odd, show that it is impossible to arrange \(99\) numbers on the circle such that none of them is divisible by \(3\) and any two neighbouring numbers are not congruent modulo \(3\).
Click here for the spoiler!
On the contrary, let us assume that none of the numbers on the circle is divisible by \(3\). Then, each number on the circle is congruent to either \(1\) or \(2\) modulo \(3\). The given conditions imply that any two neighbouring numbers on the circle are not congruent modulo \(3\). Since there are \(99\) numbers on the circle and \(99\) is odd, it is impossible to have such a configuration.
Some illustrations of Example 1.13 of the above handout may be found in the pdf below.
Lecture notes for Math Olympiad (IOQM, RMO, INMO)
Click on the icons below to download.
Topics Links Algebra Combinatorics Geometry Number Theory INMO Training Camp IMO Training Camp MOPSS Simon Marais Mathematics Competition Resources