Тема . Множества

Бесконечные конструкции (игры, клетки, множества)

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

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

Задача 1#81861

Из бесконечной клетчатой доски выкинули все клетки, обе координаты которых делятся на 100.  Можно ли оставшуюся часть доски обойти шахматным конем, побывав в каждой клетке по 1  разу?

Показать ответ и решение

Предположим, что можно. Возьмём какой-нибудь квадрат N  на N.  Ясно, что все выкинутые клетки одного цвета (пусть чёрного). Также понятно, что внутри квадрата не меньше  -1-  2
[100 ⋅N ]  выкинутых клеток (вдоль стороны точно поместится  1--
[100 ⋅N ]  клеток).

Рано или поздно конь по нашему предположению должен обойти этот квадрат. Не факт, что он будет ходить только по нему, но должен обойти. Назовём цепочкой следующий набор последовательных ходов: конь входит в квадрат, делает несколько ходов и выходит из него. Ясно, что конь обойдёт весь квадрат по некоторым цепочкам. Заметим, что если цепочка начинается с чёрной клетки, то тогда суммарно в цепочке чёрных клеток не меньше, чем белых. Если цепочка начинается с белой клетки и заканчивается чёрной, то в неё поровну чёрных и белых клеток.

Рассмотрим теперь цепочки, которые начинаются и заканчиваются белой клеткой, в них на одну белую клетку больше. Лишь за счёт этих цепочек конь может обойти в квадрате больше белых клеток, чем чёрных (это необходимо, поскольку часть чёрных клеток выкинули). Однако заметим, что в каждую такую цепочку конь входит из чёрной клетки двухклеточной каёмки квадрата. Аналогично выходит из этой цепочки конь в чёрную клетку двухклеточной каёмки. То есть количество таких цепочек не превосходит количества чёрных клеток в двухклеточной каёмке, которое равно 4N − 8  (для удобства возьмём чётное N  ). То есть посредством этих цепочек получится пройти максимум на 4N − 8  больше белых клеток, чем чёрных, однако разница между ними не меньше [1 100 ⋅N]2.  Понятно, что при выборе достаточно большого N  величина 4N − 8  будет меньше (1100 ⋅N − 1)2,  что, в свою очередь, меньше [1100-⋅N]2.  Пришли к противоречию.

Ответ:

Нет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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