Упр.929 ГДЗ Мерзляк Полонский 9 класс (Геометрия)

Рассмотрим вариант решения задания из учебника Мерзляк, Полонская, Якир 9 класс, Вентана-Граф: 929. Дан квадрат размером 99X99 клеток. Каждая клетка квадрата окрашена в чёрный или в белый цвет. Разрешается одновременно перекрасить все клетки некоторого столбца или некоторой строки в тот цвет, клеток которого в этом столбце или в этой строке до перекрашивания было больше. Всегда ли можно добиться того, чтобы все клетки квадрата стали окрашенными в один цвет?

Рассмотрим любой столбец. В нём 99 клеток, значит одного из цветов в этом столбце не меньше $$50$$. Следовательно, в каждом столбце можно выбрать цвет, который там встречается чаще.

Так как столбцов всего $$99$$, то по принципу Дирихле найдётся не меньше $$50$$ столбцов, в которых один и тот же цвет встречается чаще другого. Перекрасим все клетки этих столбцов в этот цвет.

После этого в каждой строке клеток выбранного цвета станет не меньше $$50$$, потому что в каждой строке пересекается с этими столбцами не менее $$50$$ клеток. Значит, в каждой строке этот цвет уже является преобладающим или, по крайней мере, не уступает другому цвету.

Теперь можно перекрасить каждую строку в этот цвет. После этого все клетки квадрата станут одного цвета.

Следовательно, добиться того, чтобы весь квадрат стал одноцветным, можно.

Ответ

Да.