Задача 1. Шахматному коню разрешено перемещаться только одним из четырех способов: на две клетки вправо и на клетку вверх, на две клетки влево и на клетку вверх, на две клетки вверх и на клетку вправо, на две клетки вверх и на клетку влево. Конь находится в левом нижнем углу доски 8*8. Сколькими различными способами он может переместиться на верхнюю горизонталь? Ответ обоснуйте.

задан 30 Окт '13 22:32

изменен 1 Ноя '13 0:46

Deleted's gravatar image


126

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

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

Далее заполняем вторую горизонталь, следя за тем, из каких клеток мы можем добраться в заполняемую клетку, и сколькими способами. Числа на второй горизонтали получаются такие: 0, 0, 1, 0, ..., 0. Только третье из чисел равно 1, так как на вторую горизонталь мы можем добраться только одним способом, и только в эту клетку.

Заполняем следующую, третью (снизу) горизонталь. На ней возникают три единицы: на первом, втором и пятом месте слева. Остальные числа равны нулю.

Дальнейший принцип заполнения должен быть понятен: для каждой очередной клетки просматриваем все клетки двух предыдущих горизонталей, с которых на неё мог попасть конь одним ходом. Таких клеток может быть максимум четыре. Все они уже заполнены числами, которые надо просуммировать, вписав итог в просматриваемую клетку. Это будет в точности число способов, сколькими можно в данную клетку добраться из начальной позиции коня.

После того, как вся таблица окажется заполнена, надо найти сумму всех чисел в клетках верхней горизонтали. У меня получилось 205, что желательно перепроверить.

ссылка

отвечен 31 Окт '13 0:11

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×480

задан
30 Окт '13 22:32

показан
893 раза

обновлен
31 Окт '13 0:11

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

по почте:

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

по RSS:

Ответы

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

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