In a circumference there are $99$ natural numbers. If $a$ and $b$ are two consecutive numbers in the circle, then they must satisfies one of the following conditions: $a-b=1, a-b=2$ or $\frac{a}{b}=2$. Prove that, in the circle exists a number multiple of $3$.
Problem
Source: Mathematics Regional Olympiad of Mexico Southeast 2016 P1
Tags: circles, combinatorics
x3yukari
26.10.2021 03:25
Consider $b \equiv 1 \pmod{3}.$ Then $a \equiv b+1 \equiv 2 \pmod{3}, a \equiv b+2 \equiv 0 \pmod{3}$ or $a \equiv 2b \equiv 2 \pmod{3}.$ Clearly $a \equiv 2 \pmod {3}.$ Now consider $b \equiv 2 \pmod{3}.$ Then $a \equiv b+1 \equiv 0 \pmod{3}, a \equiv b+2 \equiv 1 \pmod{3},$ or $a \equiv 2b \equiv 1 \pmod{3}.$ Clearly $a \equiv 1 \pmod{3}.$ It follows that for there to be no multiples of $3,$ the numbers must alternate $1, 2, 1, 2... \pmod {3}.$ But since there is an odd amount of numbers, there will be at least two numbers next to each other that are the same $\pmod{3},$ contradiction.
554183
26.10.2021 05:54
FTSOC assume that no number is 0 mod 3. Choose a 1 mod 3 number (say n) in the circle (if it exists). Notice that the numbers adjacent to it must be 2 mod 3 only since its only permissible neighbours must be 1+1, 2*1 and n/2 if n is even. However this means that n is 4 mod 6 so n/2 is 2 mod 3. In a very similar way, it’s easy to prove that the neighbours of any 2 mod 3 number must be 1 mod 3. However since there are 99(odd) natural numbers, one can find two neighbours leaving the same residue mod 3, contradiction.