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