Математикадан облыстық олимпиада, 2016-2017 оқу жылы, 10 сынып

Тақтада 1,2, $\ldots$, 2016, 2017 сандары жазылған. Бір қадамда ешқайсысы 0-ге тең емес үш қатар тұрған $a$, $b$ және $c$ сандарын алып, оларды осы ретпен жазылған $b-1$, $c-1$, $a-1$ үштігіне ауыстыруға болады. Осындай қадамдармен тақтада жазылған сандардың қосындысының ең кіші қандай мәнін алуға болады?

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

1,2,3 - 1,2,0

4,5,6 - 1,2,0

7,8,9 - 1,2,0

т.с.с

2014,2015,2016 - 1,2,0

2017/3 = 672*1/3

Яғни, шыққан сандардың минималды қосындысы 2016+2017=4033

Ответ: $2017$.

Решение: Легко понять, что остаток любого числа при делении на $3$ не меняется. Заметим, что из условия следует, что любое число не отрицательное. Поэтому наименьший набор который мы можем получить это

$$1,2,0,1,2,0,\ldots,1,2,0,1\implies \text{минимальная сумма} = 2017.$$

Пример: Разделим искомый ряд таким образом:

$$(1) \quad (2,3,4) \quad (5,6,7) \quad \ldots \quad (2015,2016,2017)$$

Для тройки вида $(3i+2,3i+3,3i+4)$ используем операцию $3i+2$ раз. Очевидно, что после $3i$ ходов останется $(2,3,4)$, а после $3i+1$-го и $3i+2$-го ходов получится

$$(2,3,4)\to(2,3,1)\to(2,1,0)$$

Тогда ряд $1,2,3,\ldots,2017\to 1,2,0,\ldots,1,2,0,1$ откуда сумма равна $2017.\quad \square$

Остаток любого числа имеется ввиду, что на число $i$-ом месте не меняет остаток.