Тема . Клетчатые задачи

Подсчеты в клетчатых задачах

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела клетчатые задачи
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#92128

Клетки доски (2n+1)× (2m + 1)  красятся в два цвета — белый и черный. Единичная клетка строки (столбца) называется доминирующей по строке (по столбцу), если более половины клеток этой строки (этого столбца) имеет одинаковый цвет с этой клеткой. Докажите, что по крайней мере n+ m +1  клеток доски одновременно доминируют и по строке, и по столбцу.

Подсказки к задаче

Подсказка 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? Почему это оценка верна?

Показать доказательство

Пусть A  — количество клеток доски которые одновременно доминируют по строке и по столбцу, B  — количество клеток доски которые доминируют только по строке, C  — количество клеток доски которые доминируют только по столбцу. Заметим, что

A+ B+ C ≤(2m +1)(2n+ 1)

Из того, что (A+ B)  — это количество клеток которые доминируют хотя бы по строке, то A+ B ≥(n+ 1)(2m +1),  поскольку в каждой из (2m +1)  строк хотя бы (n +1)  клетка доминирует по ней. Аналогично A + C ≥ (m+ 1)(2n+ 1).  Тогда получаем, что

(n+ 1)(2m +1)+ (m + 1)(2n+ 1)≤ (A+ B)+ (A + C)= A+ (A+ B+ C)≤

                    ≤ A+ (2m + 1)(2n+ 1)

следовательно,

A≥ (n+ 1)(2m+ 1)+(m +1)(2n +1)− (2m + 1)(2n +1)= m +n +1

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

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

Бесплатное онлайн-обучение

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

Налоговые вычеты

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

Специальное предложение
для учителей

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

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!