Дана доска 3х100. Фигура может ходить только на соседнюю по горизонтали или вертикали клетку. Сколькими способами из левого нижнего угла доски фигура может вернуться обратно, по пути побывав во всех клетках, причем в каждой клетке ровно по 1 разу?

задан 20 Фев '18 7:47

10|600 символов нужно символов осталось
3

Занумеруем вертикали числами от 1 до 100, а горизонтали -- буквами a, b, c. В левый нижний угол a1 мы попадаем двумя способами: один раз "туда", второй раз "обратно". Будем считать, что мы переместились в a2 на первом шаге, а вернулись на последнем из b1. Могло быть и наоборот, поэтому найденное в конце число вариантов придётся умножить на 2.

Перед посещением b1 мы должны были посетить угол c1: в противном случае он окажется в тупике. В угол мы попадаем из c2. Теперь клетку b2 мы должны были рядом с a2 или c2 -- в противном случае это тупик. Возникает два симметричных варианта. Рассмотрим один из них. Пусть b2 соединено с c2. Тогда в b2 мы попадаем из b3, а из a2 идём в a3. Поле c3 мы посетили перед b3, а до него были в c4. Также ясно, что из a3 мы идём в a4.

На 4-й вертикали возникла та же ситуация, что и на второй. Поле b4 должно быть соединено либо с a4, либо с c4, и выбор одного из двух вариантов здесь осуществляется независимо. После этого продолжение строится однозначно до 6-й вертикали, где снова 2 варианта выбора, и так до 98-й вертикали. Затем на 100-й вертикали мы соединяем между собой два фрагмента пути.

Итого мы делали 49 раз выбор из двух вариантов, а с учётом дополнительного умножения на 2 (выбор одного из двух направлений), у нас получается 2^{50} способов.

ссылка

отвечен 20 Фев '18 14:05

@falcao, круто, спасибо!

(20 Фев '18 14:47) make78
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,297

задан
20 Фев '18 7:47

показан
204 раза

обновлен
20 Фев '18 14:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru