Азиатско-Тихоокеанская математическая олимпиада, 2019 год

Рассмотрим доску $2018 \times 2019$, у которой в каждой клетке записано целое число. Две клетки называются соседними если у них есть общая сторона. На каждом шаге вы выбираете некоторые клетки. Затем для каждой выбранной клетки высчитывается среднее арифметическое ее соседей. После того как все вычисления произведены, число в каждой выбранной клетке меняется на соответствующее среднее значение. Всегда ли возможно сделать числа во всех клетках одинаковыми после конечного количества шагов.

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

Ответ: нет

Выберем модуль $5$. Теперь по время замены числа на среднее арифметическое, мы будем заменять деление на $2,3,4$ на умножение по модулю 5. Например $3^{-1} \equiv 2 \pmod{5}$. Тогда если в конце должна получиться доска из равных цифр, то во всех клетках должны стоять равные остатки по модулю 5.

Лемма 1. Есть доска $2 \cdot 3$ в клетках которой записаны неодинаковые остатки по модулю 5, такая что при любой замене она остается тождественной себе.

$$ | 3 | 1 | 3 |$$

$$ | 0 | 2 | 0 |$$

То, что эта доска подходит проверяется простой заменой числа в каждой клетке.

Лемма 2. Если существует доска $n \cdot m$ которая при любой замене переходит сама в себя, то существует доска $nk \cdot ms$ которая при любой замене переходит сама в себя.

Чтобы добиться этого, будем преобразовывать доску $n \cdot m$. Мы будем ее увеличивать путем симметричного отображения через стороны доски. Например

$$|3|1|3| \rightarrow |3|1|3||3|1|3|$$

$$|0|2|0| \rightarrow |0|2|0||0|2|0|$$

Покажем, что у новой доски после замены число не изменяется по модулю 5.

Случай 1. Если клетка имела $4$ соседа, она продолжит иметь тех же 4 соседей.

Случай 2. Если клетка с числом $a$ имела трех соседей $b, c, d$, то по предположению $a^{-1} \equiv 3^{-1}(b+c+d) \equiv 2(b+c+d) \pmod{5}$. После преобразования, клетка будет иметь соседей $a, b, c, d$. То перейдет сама в себя: $$4^{-1}(a+b+c+d) \equiv 4(a+b+c+d) \equiv 4a+2a \equiv a \pmod{5}$$

Случай 3. Если клетка с числом $a$ имела двух соседей $b, c$, то по предположению $a^{-1} \equiv 2^{-1}(b+c) \equiv 3(b+c) \pmod{5}$. Если после преобразования, клетка будет иметь соседей $a, b, c$. То перейдет сама в себя: $$3^{-1}(a+b+c) \equiv 2(a+b+c) \equiv 8(b+c) \equiv a \pmod{5}$$

Если после преобразования, клетка будет иметь соседей $a, b, c, a$. То перейдет сама в себя: $$4^{-1}(2a+b+c) \equiv 4(2a+b+c) \equiv 28(b+c) \equiv a \pmod{5}$$

Значит доска $nk \cdot ms$ после замены переходит сама в себя по модулю 5.

Возвращаясь к задаче. Так как $2 \, | \, 2018$, $3 \, | \, 2019$, то по лемме 2 если преобразовать доску из леммы 1 в доску $2018 \cdot 2019$ то в ней никогда все числа не будут давать равные остатки, что означает что в ней никогда все числа не будут равны после конечного числа шагов.