Ошибка.
Попробуйте повторить позже
На бесконечной клетчатой плоскости некоторые клетки покрашены в красный цвет, некоторые — в синий, а некоторые остались непокрашенными. Известно, что в каждой строчке, где есть хотя бы одна синяя клетка, есть также хотя бы 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%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
