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

Увидеть граф (переформулировки)

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

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

Задача 1#100072

В квадрате 100× 100  клетки покрашены в синий и зеленый цвета. Причем на диагонали из левого верхнего угла в правый нижний есть 50  синих и 50  зеленых клеток. Докажите, что из доски всегда можно вырезать 50  доминошек с разноцветными клетками.

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

Соединим самую верхнюю зеленую клетку на диагонали с самой нижней синей, двигаясь вниз по вертикали до горизонтали, где стоит эта синяя клетка, а потом вправо по горизонтали. То же проделаем со второй сверху зеленой и второй снизу синей диагональными клетками и т.д., доколе возможно. Когда станет невозможно, все оставшиеся на диагонали зеленые клетки будут ниже всех оставшихся синих. Соединим самую нижнюю из оставшихся зеленых клеток с самой верхней из оставшихся синих, двигаясь вверх по вертикали до горизонтали, где стоит эта синяя клетка, а потом — влево по горизонтали. То же проделаем со второй снизу из оставшихся зеленых и второй снизу из оставшихся синих диагональных клеток и т.д. В итоге у нас получится 50  непересекающихся путей, у каждого из которых разноцветные концы. Очевидно, на каждом из таких путей окажется хотя бы по одной разноцветной паре соседних по стороне клеток, так что мы сможем вырезать 50  искомых доминошек.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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