Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео
Ошибка.
Попробуйте повторить позже
На бесконечной клетчатой плоскости некоторые клетки покрашены в красный цвет, некоторые — в синий, а некоторые остались непокрашенными. Известно, что в каждой строчке, где есть хотя бы одна синяя клетка, есть также хотя бы 5 красных, а в каждом столбце, где есть хотя бы одна красная клетка, есть хотя бы 6 синих. Какое наименьшее положительное число покрашенных клеток может быть на плоскости?
Источники:
Подсказка 1
Для начала заметим, что мы можем избавиться от всех столбцов, в которых все клетки синие и от всех строк, в которых все клетки красные. Теперь в каждом столбце и строке у нас и синие, и красные клетки. Пусть у нас есть m строк и n столбцов ,x-кол-во красных клеток, y-кол-во синих клеток. По условию в каждом столбце хотя бы 6 синих клеток => y>=6n, аналогично x>=5m. В каждой строке есть хотя бы одна синяя клетка и 5 красных, n>=6.Аналогично m>=7.Чтобы догадаться до ответа, бывает полезно рассмотреть частный случай. Попробуйте рассмотреть случай, когда все закрашенные клетки будут находиться только на пересечении строк и столбцов.
Подсказка 4
Так как n<=9 и x>=60, то в каком-то столбце >=7 красных клеток, тогда в каком-то столбце >=13 клеток, тогда m>=13 и x>=65 и y<55. Вам не кажется это похожим на предыдущий шаг? Попробуйте теперь сами сделать то же самое.
Подсказка 5
После нескольких таких шагов мы получим, что n<=5, но у нас n>=6. Противоречие! Со вторым случаем делаем то же самое. Оценка доказана. Значит, наш ответ 120.
Примеров для 120 закрашенных клеток несколько, они все отличаются перестановкой строк и столбцов. Можно взять прямоугольник и раскрасить его в шахматном порядке в красный и синий цвет.
Докажем теперь, что меньше 120 закрашенных клеток не может быть.
Если в каком-то столбце есть закрашенные клетки, то по условию они либо только синие, либо обоих цветов. При этом, если в каком-то столбце все закрашенные клетки синие, можно превратить их все в незакрашенные. При этом условие задачи сохранится, а количество закрашенных клеток уменьшится (но не до нуля, так как в строчках с этими синими клетками останутся какие-то красные). Аналогичным образом можно избавиться от строчек, в которых есть красные клетки, но нет синих. Теперь можно считать, что во всех строчках и столбцах, где есть закрашенные клетки, присутствуют клетки обоих цветов.
Пусть у нас красных клеток и синих, при этом закрашенные клетки находятся в строках и столбцах. Так как в каждом из этих столбцов присутствуют хотя бы 6 синих клеток, выполняется неравенство или, что то же самое, Аналогично, или, что то же самое, Также заметим, что в каждой строке есть хотя бы одна синяя клетка и 5 красных, Аналогично
Сравним числа и
Пусть то есть В каждом столбце присутствуют хотя бы 6 синих клеток. Из взятого в качестве предположения неравенства следует, что в каком-то столбце количество красных клеток хотя бы от количества синих, то есть хотя бы 5, поэтому общее количество закрашенных клеток в данном столбце хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.
Но раз а в каком-то из наших не более чем 10 столбцов присутствуют хотя бы 6 красных клеток. Так как в нём должно быть ещё и 6 синих, мы получаем, что общее количество закрашенных клеток в этом столбце хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.
Поскольку значит Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 7 красных клеток, откуда
Поскольку в каком-то столбце присутствуют хотя бы то есть хотя бы 8 красных клеток, откуда
Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 9 красных клеток, откуда
Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 11 красных клеток, откуда
Поскольку значит, Значит, в каком-то столбце присутствуют хотя бы то есть хотя бы 15 красных клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.
Аналогично разбираем случай, когда то есть В каждой строке присутствуют хотя бы 5 красных клеток. Из взятого в качестве предположения неравенства следует, что в какой-то строке есть хотя бы 6 синих клеток, то есть общее количество закрашенных клеток в данной строке хотя бы 11, откуда и, следовательно, Если и оценка доказана. Предположим, тогда то есть не превосходит 10.
Но раз а в какой-то из наших не более чем 10 строк присутствуют хотя бы 7 синих клеток. Так как в ней должно быть ещё и 5 красных, мы получаем, что общее количество закрашенных клеток в этой строке хотя бы 12, то есть, и Тогда, чтобы было меньше 120, необходимо Продолжим эти рассуждения.
Поскольку в какой-то строке присутствуют хотя бы то есть хотя бы 8 синих клеток, откуда
Поскольку значит Значит, в какой-то строке присутствуют хотя бы то есть хотя бы 10 синих клеток, откуда Отсюда получаем, что что противоречит доказанному ранее.
Таким образом, мы разобрали оба случая и доказали, что ситуация, в которой невозможна.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!