Азиатско-Тихоокеанская математическая олимпиада, 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$ то в ней никогда все числа не будут давать равные остатки, что означает что в ней никогда все числа не будут равны после конечного числа шагов.