ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66893
Темы:    [ Теория алгоритмов (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4-
Классы: 8,9
В корзину
Прислать комментарий

Условие

На клетчатой доске лежат доминошки, не касаясь даже углами. Каждая доминошка занимает две соседние (по стороне) клетки доски. Нижняя левая и правая верхняя клетки доски свободны. Всегда ли можно пройти из левой нижней клетки в правую верхнюю, делая ходы только вверх и вправо на соседние по стороне клетки и не наступая на доминошки, если доска имеет размеры

а) $100\times101$ клеток;

б) $100\times100$ клеток?

Решение

На рисунке слева показано расположение доминошек на доске $6\times 7$, которое не позволяет пройти из левой нижней клетки в правую верхнюю. Действительно, попасть в (серую) область правее самой нижней доминошки нельзя, поскольку сначала мы должны подняться выше первой доминошки, и тогда мы уже выше серой полосы (а вниз ходить нельзя). Далее, нельзя попасть в аналогичную серую область правее следующей доминошки и т.д. Эта конструкция обобщается на любую доску размера $2n\times (2n+1)$.

Замечание. Для упрощения доказательства можно было бы добавить ещё горизонтальные доминошки над вертикальными, чтобы оставался единственный путь по доске, упирающийся в итоге в последнюю вертикальную доминошку (рисунок справа).

б) Начальная и конечная клетки лежат на главной диагонали доски и имеют «координаты» $(1, 1)$ и $(100, 100)$. Докажем, что в любую свободную клетку этой диагонали можно попасть.

Действительно, пусть мы дошли до клетки $(n, n)$. Если клетка $(n + 1, n + 1)$ свободна, то хоть одна из клеток $(n, n + 1)$ и $(n + 1, n)$ не занята и через неё можно пройти на клетку $(n + 1, n + 1)$.

Если же клетка $(n + 1, n + 1)$ занята, то из её соседей занята ровно одна клетка, причём по стороне, поэтому один из двух путей из $(n, n)$ в $(n + 2, n + 2)$ не закрыт.


Ответ

а) не всегда;

б) всегда.

Источники и прецеденты использования

олимпиада
Название Турнир городов
год/номер
Номер 42
Дата 2020/21
вариант
Вариант весенний тур, базовый вариант, 8-9 класс
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .