Browse · MathNet
PrintIranian Mathematical Olympiad
Iran number theory
Problem
Is it possible to write natural numbers (not necessarily distinct) around a circle such that is used at least once and each number is the sum of the greatest common divisor of the two previous numbers and the greatest common divisor of the two next numbers? For example, if are five consecutive numbers on the circle then .
Solution
We shall show that this is impossible. Assume that there are such numbers. First of all, note that if we divide all the numbers by then the new numbers satisfy the second condition and one of them is a divisor of , so we can assume that the greatest common divisor of the numbers is .
Lemma. the gcd of each three consecutive numbers on the circle is .
Proof. Assume that are five consecutive numbers on the circle, if have a common divisor , then the equality implies that are also divisible by . Similarly all the numbers should be divisible by which is in contradiction with our assumption. This completes our proof.
Assume that is the maximum number on the circle, and be five consecutive numbers. We know that because at least one of the numbers should be a divisor of and is not divisible by . We have so at least one of the , should be at least . Without the loss of generality we can assume that .
If then , yielding . If then by the assumption we shall arrive at a contradiction hence we have . This implies that therefore which contradicts to the fact that .
So we have , let be the number before . From the lemma we know that and we have If is odd this contradicts to the fact that , if is even we have and . But we have Which contradicts to the fact that . ■
Lemma. the gcd of each three consecutive numbers on the circle is .
Proof. Assume that are five consecutive numbers on the circle, if have a common divisor , then the equality implies that are also divisible by . Similarly all the numbers should be divisible by which is in contradiction with our assumption. This completes our proof.
Assume that is the maximum number on the circle, and be five consecutive numbers. We know that because at least one of the numbers should be a divisor of and is not divisible by . We have so at least one of the , should be at least . Without the loss of generality we can assume that .
If then , yielding . If then by the assumption we shall arrive at a contradiction hence we have . This implies that therefore which contradicts to the fact that .
So we have , let be the number before . From the lemma we know that and we have If is odd this contradicts to the fact that , if is even we have and . But we have Which contradicts to the fact that . ■
Final answer
No, it is impossible.
Techniques
Greatest common divisors (gcd)Coloring schemes, extremal arguments