6-шы халықаралық Жәутіков олимпиадасы, 2010 жыл

Тақтаға $1,2, \ldots,n$ натурал сандары жазылған, $n > 2$. Әр минутта тақтадан екі сан өшіріліп, орынына олардың қосындысының ең кіші жай бөлгіші жазылады. Ең соңында тақтада 97 саны қалды. Қандай ең кіші $n$ үшін осылай болуы мүмкін?

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

Комментарии от администратора Комментарии от администратора №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.