Номер 929, страница 227 - гдз по геометрии 9 класс учебник Мерзляк, Полонский

929. Дан квадрат размером $99 \times 99$ клеток. Каждая клетка квадрата окрашена в чёрный или в белый цвет. Разрешается одновременно перекрасить все клетки некоторого столбца или некоторой строки в тот цвет, клеток которого в этом столбце или в этой строке до перекрашивания было больше. Всегда ли можно добиться того, чтобы все клетки квадрата стали окрашенными в один цвет?

Нет, не всегда можно добиться того, чтобы все клетки квадрата стали окрашенными в один цвет. Процесс перекрашивания может попасть в цикл, из которого невозможно выйти в монохроматическое состояние (когда все клетки одного цвета).

Рассмотрим логику процесса. Каждая операция (перекрашивание строки или столбца) делает эту линию монохроматической. Это локальное "улучшение". Однако, последовательность таких локальных улучшений не обязательно ведет к глобальному оптимуму — полностью монохроматической доске. Система может оказаться в "ловушке" — цикле состояний, ни одно из которых не является монохроматическим.

Чтобы доказать, что это не всегда возможно, достаточно привести один пример начальной раскраски, для которой достичь цели нельзя. Хотя построение такого контрпримера достаточно сложно, можно описать его общую структуру.

Представим себе конфигурацию, в которой действия над строками и столбцами противодействуют друг другу. Например, можно создать такое состояние $A$, что:

1. Применение операций к строкам приводит к состоянию $B$.
2. В состоянии $B$ все строки уже стабильны (монохроматичны), но столбцы — нет.
3. Применение операций к столбцам в состоянии $B$ приводит обратно к состоянию $A$.

Таким образом, система может циклически переходить между состояниями $A \rightarrow B \rightarrow A \rightarrow \dots$, никогда не достигая полностью одноцветной доски.

Покажем существование такого цикла на конкретном примере.

Рассмотрим две конфигурации, $A$ и $B$.

Конфигурация A: Первые 50 строк полностью белые, а оставшиеся 49 строк — полностью чёрные.

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

Рассмотрим столбцы. В каждом столбце находится 50 белых клеток (в верхних 50 строках) и 49 чёрных клеток (в нижних 49 строках). Поскольку $50 > 49$, преобладающий цвет в каждом столбце — белый. Таким образом, ни один столбец не является стабильным, и для каждого из них операция перекрашивания изменит его на полностью белый.

Если мы применим операцию перекрашивания ко всем столбцам, каждый из них станет полностью белым. В результате вся доска станет белой. Это путь к решению.

Однако, мы можем выбрать другую последовательность действий. Перекрасим только один, например, первый столбец. Он станет полностью белым. Назовем новую конфигурацию $A'$. В ней первый столбец полностью белый, а остальные столбцы остались прежними (50 белых, 49 чёрных). Но теперь строки с 51 по 99 перестали быть монохроматичными: каждая из них состоит из одной белой клетки (в первом столбце) и 98 чёрных. В этих строках преобладает чёрный цвет ($98 > 1$). Если мы теперь перекрасим любую из этих строк (например, 51-ю), она снова станет полностью чёрной. Это действие "отменяет" изменение, внесённое операцией над столбцом. Если мы перекрасим все строки с 51 по 99, мы вернемся в исходное состояние $A$.

Это показывает, что существуют циклы операций, возвращающие доску в предыдущее состояние. Хотя для данной конфигурации $A$ существует и путь к полному окрашиванию (перекрасить все столбцы), можно построить более сложные конфигурации, где любой возможный ход ведет в состояние, из которого можно вернуться обратно, и ни один путь не ведет к монохроматическому состоянию.

Такие "зацикленные" конфигурации являются контрпримером, доказывающим, что не для всякой начальной раскраски можно достичь цели.

Ответ: Нет, не всегда.