Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа

В белой таблице размером $100\times 100$ клеток окрашено в красный цвет $N$ ($N > 0$) клеток таким образом, что количество красных клеток в любой фигуре, образованной объединением столбца и строки таблицы, делится на 3. Чему может быть равно $N$? ( С. Берлов )

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

Ответ. 300, 2*300, 3*300,... 33*300.

Решение. Пример: Зn строк (или столбцов) красные, остальные белые, n = 1,2,...,33. Условие делимости на 3 выполнено: если столбец и строка пересекаются по белой клетке, то в их объединении 3n красных клеток, если по красной клетке то 100 + 3n - 1 = 3(n + 33) красных клеток.

Покажем, что других вариантов нет. Рассмотрим 4 клетки, образующие прямоугольник со сторонами, па- раллельными сторонам таблицы. Сложим количества красных клеток в строках и столбцах, содержащих две противоположные вершины прямоугольника, и вычтем количества красных клеток в строках и столбцах, содер- жащих две оставшихся вершины. Результат будет равен разности количества красных клеток во второй пареe вершин и количества красных клеток в первой паре вершин. Эта разность не больше 2 и не меньше 2. Кроме того, она делится на 3. Значит, она равна 0, есть количества красных клеток в парах противоположных вершин равны.

Пусть нашлась строка С, где есть белая клетка Б и красная клетка К. Тогда из доказанного следует, что столбец с клеткой Б целиком белый, с клеткой К целиком красный. Аналогичные утверждения верны и для всех остальных клеток строки С. Таким образом, в этом случае каждый столбец таблицы состоит из клеток одного цвета. В противном случае каждая строка таблицы состоит из клеток одного цвета.

Пусть каждая из строк таблицы целиком красная или целиком белая, и красных строк к штук. Целиком красной таблица быть не может, так как в этом случае число красных клеток в объединении строки и столбца не делится на 3. Значит, есть белая строка. В ее объединении с любым столбцом к красных клеток. Значит, к делится на 3 и N = 300 * (k/3), что и требовалось доказать. Случай, когда каждый столбец таблицы состоит из клеток одного цвета, рассматривается аналогично.