HMMT 二月 2005 · 代数 · 第 5 题

HMMT February 2005 — Algebra — Problem 5

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 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.