Подсчеты в клетчатых задачах
Ошибка.
Попробуйте повторить позже
Клетки доски красятся в два цвета — белый и черный. Единичная клетка строки (столбца) называется
доминирующей по строке (по столбцу), если более половины клеток этой строки (этого столбца) имеет одинаковый цвет
с этой клеткой. Докажите, что по крайней мере
клеток доски одновременно доминируют и по строке, и по
столбцу.
Подсказка 1
Пусть A — количество клеток, который доминируют и по строке. Как можно охарактеризовать множество таких клеток?
Подсказка 2
Это пересечение двух множеств, в первом из которых содержится клетки, доминирующие хотя бы по строке, во втором — хотя бы по столбцу. Для удобства в дальнейшей оценке, пусть B — количество клеток доски которые доминируют только по строке, С — количество клеток доски которые доминируют только по столбцу. Что можно сказать про числа A+B и A+C?
Подсказка 3
Подсказка A+B — количество клеток, которые доминируют хотя бы по строке. Сколько таких клеток в каждой из строк?
Подсказка 4
Не меньше n+1. Таким образом A+B не меньше, чем (n+1)(2m+1). Аналогично, A+C не меньше, чем (2n+1)(m+1). Как можно сделать оценку на A, используя данные неравенства?
Подсказка 5
Число A не меньше (n+1)(2m+1)+(2n+1)(m+1)-(A+B+C). Как необходимо оценить сумму A+B+C, чтобы доказать неравенство n+1)(2m+1)+(2n+1)(m+1)-(A+B+C) ≥ n+m+1? Почему это оценка верна?
Пусть — количество клеток доски которые одновременно доминируют по строке и по столбцу,
— количество клеток доски
которые доминируют только по строке,
— количество клеток доски которые доминируют только по столбцу. Заметим,
что
Из того, что — это количество клеток которые доминируют хотя бы по строке, то
поскольку в
каждой из
строк хотя бы
клетка доминирует по ней. Аналогично
Тогда получаем,
что
следовательно,
Специальные программы

Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!