Задача о числах на клетчатой доске.

Question

Задача о числах на клетчатой доске.

hippie Просветленный (31241), закрыт 16 лет назад

В клетках доски 6х6 написаны целые числа.
За один шаг разрешается выбрать произвольный квадрат (размером больше чем 1х1), стороны которого идут по сторонам клеток доски, и увеличить на 1 все числа, которые находятся в этом квадрате.
Всегда ли за несколько таких шагов можно добиться того, чтобы все числа на доске делились на 3?

Дополнен 16 лет назад

Прежде чем закрыть вопрос выкладываю своё решение задачи.

=====================

Расставим на доске знаки «0», «+» и «–» как показано на схеме

0++––0
–0+–0+
––00++
++00––
+0–+0–
0––++0

Как бы ни располагался квадрат на доске, в нём будет
либо равное количество знаков «+» и «–»,
либо одних из этих знаков будет ровно на 3 больше чем других.
Поэтому остаток от деления на 3 разности между суммой чисел в клетках со знаком «+» и суммой чисел в клетках со знаком «–» остаётся постоянным. И если вначале эта разность не делилась на 3, то она не будет делится на 3 и после любого числа шагов. И, следовательно, для такой расстановки чисел за конечное число шагов нельзя добиться того, чтобы все числа на доске делились на 3.

-----------------------------

ПРИМЕЧАНИЕ: если указанная разность изначально делилась на 3, то для такой расстановки всегда можно добиться того, чтобы все числа на доске делились на 3, за конечное число шагов. Но это доказать достаточно сложно.

ПРИМЕЧАНИЕ #2: решение Смайлик, в действительности легко исправляется, и доводится до правильного.

Answer 1

Вроде получилось.

Не всегда.

1.Всего различных расстановок чисел (по модулю 3) в таблице 6х6 равно 3^36.

2.Оценим, сколько различных таблиц можно получить из нулевой. Рассмотрим все возможные квадраты, которые увеличивают число на 1.

Число возможных таблиц равно числу способов, которыми можно выбрать эти квадраты для у4частия в процессе.

Квадраты 4х4 и 6х6 сразу исключаем из рассмотрения, они заменяются несколькими квадратами 2х2.

Квадраты 2х2, не примыкающие к границе тоже можно исключить – они заменяются двумя квадратами 3х3, идущими внахлест. Такая конструкция увеличивает числа в образовавшемся квадрате 2х2 на 2, две таких конструкции – на 1 (по модулю 2).

Итак, получаем
16 квадратов 2х2 ( по краям) , каждый может участвовать 3-мя способами (от 0 до 2 по модулю 3), 3^16 способов

16 квадратов 3х3, 3^16 способов

4 квадрата 5х5, 3^4 способов.

Итого, не более 3^36 способов.

Однако, 4 непересекающихся квадрата 3х3 можно заменить квадратами 2х2.

Итого, количество таблиц, которые можно получить из нулевой меньше 3^36 а количество всех таблиц равно 3^36. Все таблицы таким способом получить нельзя, значит, и наоборот, найдется таблица из которой нельзя получить нулевую.

Спасибо за задачу!

Answer 2

Наглая задачка.. . попробуем так: заменим все числа на 0, 1 и -1 в зависимости от остатка от деления на 3, и в дальнейшем будем пользоваться только этими числами (так удобнее) ; задача тогда - свести все числа в квадрате 6х6 к 0. Во-первых, заметим, что из двух квадартов 2х2, двух 3х3 и двух 5х5 можно составить квадрат 5х5 с 1, изменяющий на 1 только центральную клетку (подумай, как, это не сложно) , назовем это "операция *". Такими квадратами можно свести 4 центральные клетки к 0. Идея решения - "столкнуть" все не-нули в центр, после чего ликвидировать их *-ами.
Во-вторых, заметим, что комбинацией 4 2х2 и 2 3х3 можно изменить квадрат 3х3 на
0 1 0
1 0 1
0 1 0
(Расположение аналогично операции *, но все 2х2 накладываются в центре) . Назовем это "операция **".
Кроме того, очевидно, что 2-кратное повторение какой-либо операции эквивалентно ее обращению (т. е. вычитанию) .
Начинаем обнулять эл-ты, начиная с угловых. Квадартами 2х2 в углах доводим до 0. Операциями ** обнуляем соседние с углами э-ты (при этом, естественно, "портятся" эл-ты в центре, но это нас не волнует - пока) . Теперь, если на краю два одинаковых числа, обнуляем их квадратом 2х2, если разных - приводим край к виду 0 0 1 0 0 0 (теми же 2х2), после чего квадратом 2х2 превращаем 3-е и 4-е числа в единицы, которые вместе с 2-м числом обнуляются двумя 3х3.
Стороны очищены. Теперь операциями ** обнуляем углы центрального квадрата 4х4. Дальше обнуляем все, что возможно, используя квадраты 2х2, * и **. Если внешние эл-ты центрального 4х4 удалось обнулить, центр обнуляем операцией *, если не удалось - возможны нескольно вариантов (вроде 3, если изображать только центральный 2х4, то:
1 0 0 1
0 0 0 0

1 0 0 0
0 0 0 1

1 0 0 0
0 0 0 0

В каждом варианте есть несколько запутанное решение, которое несложно восстановить, но долго описывать.
В целом, мне кажется, что есть и более простое решение, чем этот брутфорс, но я его пока не увидел.