Дана полоска 1 × 10. В клетки записываются числа 1, 2, . . . , 10 по сле- дующему правилу: сначала в какую-нибудь клетку пишут число 1, затем число 2 записывают в соседнюю клетку, затем число 3 — в одну из соседних с уже занятыми, и так далее. Сколькими способами это можно сделать?


Решим задачу для общего случая, когда полоска состоит из n клеток. Докажем по индукции, что способов имеется 2^{n-1}. База индукции очевидна. Покажем, что число способов каждый раз удваивается. Когда вписано несколько первых чисел, они образуют "сплошной" ряд без пробелов. Отсюда следует, что последнее число n вписывается в одну из двух крайних клеток. Это даёт два разных типа заполнения при n > 1. Ясно, что заполнений, у которых число n занимает первую позицию, столько же, сколько способов заполнить полоску длины n-1 числами от 1 до n-1. Столько же способов заполнения имеется, если число n занимает последнюю позицию. Поэтому при переходе от n-1 к n число способов заполнения становится вдвое больше.

Оцени ответ

Загрузить картинку
Не нашёл ответ?

Если тебя не устраивает ответ или его нет, то попробуй воспользоваться поиском на сайте и найти похожие ответы по предмету Математика.

Найти другие ответы

ПОИСК ПО САЙТУ



ПРЕДМЕТЫ

Показать ещё