Областная олимпиада по математике, 2017 год, 9 класс

На доске выписаны числа 1,2, $\ldots$, 2016, 2017. За один шаг разрешается выбрать три идущие подряд числа $a$, $b$ и $c$, из которых ни одно не равно 0, и заменить их на тройку чисел $b-1$, $c-1$, $a-1$ в указанном порядке. Какую наименьшую сумму записанных на доске чисел можно получить, делая такие шаги?

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

$$(а,b,c) \rightarrow (b-1,c-1,a-1)$$

$$ 1,\underbrace{2}_a,\underbrace{3}_b,\underbrace{4}_c$$

$$ 1,.,2,.3,.1$$

$$ 1,.\underbrace{2,.0,.1} \Rightarrow \mathbb{S}_1=4$$

$$1,.2,\underbrace{3}_a,.\underbrace{4}_b,.\underbrace{5}_c$$

$$...........................$$

$$ 1,.2,.\underbrace{0,.1,.2} \Rightarrow \mathbb{S}_2= 6$$

$$1,.2,.3,.\underbrace{4}_a,.\underbrace{5}_b,.\underbrace{6}_c$$

$$...........................$$

$$ 1,.2,.3,.\underbrace{2,.0,.1} \Rightarrow \mathbb{S}_3= 9$$

$$...........................$$

$$1,.2,....,n-3,\underbrace{n-2}_a,.\underbrace{n-1}_b,.\underbrace{n}_c$$

$$...........................$$

$$1,.2,.3,......,n-3, \underbrace{(0,1,2)} \Rightarrow \mathbb{S}_{min}=\frac{(n-2)(n-3)}{2}+3$$

$$1,.2,.3,.......2016,.2017 \Rightarrow \mathbb{S}_{min}=2015\cdot 1007 +3$$

Дастан а если мы применим для каждой такой тройки как:

2;3;4

5;6;7

...

2015;2016;2017

то у нас выйдет 672×3+1<2015×1007+3

То есть ответ 2017?

Da

Ответ: $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$-ом месте не меняет остаток.