HMMT 二月 2005 · GEN1 赛 · 第 8 题

HMMT February 2005 — GEN1 Round — Problem 8

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?

解析

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? Solution: 28 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 n be the largest integer in the circle. The greatest common divisor of its two neighbors is n − 1. Therefore, each of the two 2 neighbors is at least n − 1 but at most n , so since n − 1 - n for n − 1 ≥ 2, they must both be equal to n − 1. Let m be one of the numbers on the other side of n − 1 from n . Then gcd( n, m ) = n − 2. Since n − 2 ≥ 0, n − 2 | n only for n = 3 or 4. If n = 3, each number must be 2 or 3, and it is easy to check that there is no solution. If n = 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.