Клетчатые задачи на Курчатове
Ошибка.
Попробуйте повторить позже
Дана клетчатая доска 
Фигура принц умеет ходить по горизонтали и вертикали, делая ходы сначала на 1 клетку, потом — на две (в
одном направлении), потом опять на одну и т.д. Может ли принц, встав на некоторую клетку, обойти все остальные клетки доски, побывав
на каждой ровно по одному разу?
Источники:
Подсказка 1
Попробуем представить некоторые варианты передвижения принца за несколько ходов. Например, как можно обобщить его передвижения за ход вида "2 клетки" от клетки, на которой он был до этого хода?
Подсказка 2
Заметим, что, если мы условно разделим поле на области размера 2х2, то каждый ход вида "2 клетки" принц выходит из одной области и входит в другую. Тогда пусть эти области покрашены в два чередующихся цвета, так, что соседние области имеют разные цвета. Что нам это может дать?
Подсказка 3
Получаем, что на чётных ходах принц будет менять цвет клетки, на которой стоит. Тогда можно условно сопоставить клетки разных цветов по ходам: после второго хода и после первого — разные цвета, после четвертого хода и третьего — разные цвета... и так далее. Тогда как можно оценить количество клеток каждого цвета?
Подсказка 4
То есть свободные варианты для цветов (когда нельзя ходы принца разбить на пары, дающие равное количество обоих цветов) — это только первый и последний ход, что дает максимальное различие в количестве клеток каждого цвета, равное двум. А теперь посмотрим, сколько у нас действительно клеток каждого цвета по нашей раскраске, и сравним результаты.
Предположим, что такое возможно. Покрасим клетки доски как на рис.
Заметим, что при втором, четвертом, …, 
-м ходе принц меняет цвет клетки. Значит, количество клеток цветов 
и 
может
отличаться не более чем на 
поскольку все клетки, начиная со второй и заканчивая 
-й, бьются на пары вторая-третья,
четвертая-пятая, …, тридцать четвертая-тридцать пятая, и внутри каждой пары клетки имеют разный цвет. Ну а первая и последняя клетки
могут иметь любой цвет.
Таким образом, количество клеток цветов 
и 
отличается не более чем на 
Но с другой стороны, клеток цвета 
больше на 
—
противоречие.
Нет, не может
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
