Maths Olympiad Prep

Library / /449 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Ten positive integers are arranged around a circle. Each number is one more than the greatest common divisor of its two neighbors. What is the sum of the ten numbers?

A number or a short expression. Spacing and $ signs are ignored.

Solution

First note that all the integers must be at least 2, because the greatest common divisor of any two positive integers is at least 1. Let nn be the largest integer in the circle. The greatest common divisor of its two neighbors is n1n-1. Therefore, each of the two neighbors is at least n1n-1 but at most nn, so since n1nn-1 \nmid n for n12n-1 \geq 2, they must both be equal to n1n-1. Let mm be one of the numbers on the other side of n1n-1 from nn. Then gcd(n,m)=n2\operatorname{gcd}(n, m)=n-2. Since n20,n2nn-2 \geq 0, n-2 \mid n only for n=3n=3 or 4. If n=3n=3, each number must be 2 or 3, and it is easy to check that there is no solution. If n=4n=4, then it is again not hard to find that there is a unique solution up to rotation, namely 4322343223. The only possible sum is therefore 28.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.