6-я Международная Жаутыковская олимпиада, 2010 год

На доске выписаны натуральные числа от $1$ до $n$ ($n > 2$). Рассмотрим следующую операцию: стираются два произвольных числа, а вместо них на доску выписывается наименьший простой делитель их суммы. Операция проводится до тех пор, пока на доске не останется одно число. Найдите наименьшее возможное $n$, при котором оставшимся числом может быть число $97$.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     The biggest prime, which could be reached when $n$ is fixed, would not exceed the sum of the biggest odd positive integer smaller than $n$, all even integers from 2 to $n$ and some additional 2-es. It follows that if $n=14$, then the biggest prime number, which could be achieved, will not exceed the number $13+2+4+6+8+10+12+14+3\cdot 2=75$. On the other hand the operation under consideration is invariant with respect to the parity of the number of the odd positive integers which do not exceed $n$. It follows that if $n=15$ or $n=16$, the integer 97 could not be the last. Let $n=17$. The sum of all even positive integers less than 17 is equal to 72. The odd positive integers less than 17 give four additional 2-es when the operation is applied to them in pairs. Since $97-\left( 72+2\cdot 4 \right)=17$, the only way to achieve 97, when $n=17$, is to start by 17 and in a suitable order to add integers from the set $\left\{ 2,\,\,2,\,\,2,\,\,2,\,\,2,\,\,4,\,\,6,\,\,\ldots ,\,\,16 \right\}$, obtaining each time a new prime number different from the previous one. Two of these 12 integers in the set are equal to 0 modulo 3, three of them are equal to 1 modulo 3 and seven of them are equal to 2 modulo 3. The number 17 is equal to 2 modulo 3 and a number equal to 2 or to 0 modulo 3 should be added to it only. When a number equal to 1 modulo 3 is obtained, then a number equal to 1 or to 0 modulo 3 should be added only. Thus 97 could not be achieved since the integers in the set under consideration which are equal to 1 modulo 3 are less than the integers which are equal to 2 modulo 3. The answer of the problem is $n=18$. Firstly, apply the operation to the pairs (3,5); (7,9); (11,13) and (15,17). Further; proceed in the following way: (1,2) $\to $ 3; (3,2) $\to $ 5; (5,2) $\to $ 7; (7,4) $\to $ 11; (11,2) $\to $ 13; (13,6) $\to $ 19; (19,10) $\to $ 29; (29,8) $\to $ 37; (37,16) $\to $ 53; (53,14) $\to $ 67; (67,12) $\to $ 79, (79,18) $\to $ 97.