Заполнить клетки прямоугольника 2*100 непрерывной последовательностью чисел
В тетрадке нарисован прямоугольник 2×100. Требуется записать в его клетки числа от 1 до 200 так, что любые два числа, отличающиеся на единицу были записаны в клетки, соседние по стороне. Сколько существует способов это сделать?
Лемма Если зафиксировать столбцы, на которых находятся числа 1 и 200, то
- существует ровно 2 варианта решения если столбцы различные,
- существует ровно 2 варианта решения если это один и тот же столбец и он - крайний,
- в остальных случаях решения не существует.
Доказательство очевидно (т.е. мне лень его писать).
Решение Всего 100*100 вариантов выбора столбцов для чисел 1 и 200, из них 98 - невозможные.
Итого - 2*(100*100 - 98) = 19804 варианта.
Попробуем решить задачу рекурсивно.
Пусть F(n) — количество решений для доски 2 × n, G(n) — количество решений для доски 2 × n, которые начинаются в левом нижнем углу. (Мы предполагаем, что прямоугольник расположен горизонтально).
Не ограничивая общности, предположим, что первая точка расположена внизу (это уменьшает количество вариантов для F(n) вдвое).
Очевидно, в каждом из путей должен быть вертикальный отрезок. Рассмотрим первый из них. Пусть он будет на k-ом шагу. Наш путь имеет вид
У нас есть такие варианты:
1) k ≠ 1, и верхняя часть идёт в том же направлении, что и первый отрезок:
В левую часть от k + 1 попасть невозможно, и эта часть непуста. Итак, этот вариант невозможен.
2) k ≠ 1, и верхняя часть идёт в противоположном от первого отрезка направлении.
при этом наш путь не может попасть в правую часть, то есть, она должна быть пустая. То есть путь выглядит так:
Остаток доски имеет размеры 2 × (n − k), и её можно обойти G(n − k) способами.
при этом наш путь не может попасть в левую часть, значит, она должна быть пуста, то есть имеем такую картинку:
Количество вариантов обхода равно G(n − 1).
Составим рекуррентные соотношения.
Для произвольной начальной точки: Количество вариантов в 1) равно 0. Количество вариантов в 2) равно сумме по всем возможным k (от 2 до n) величин G(n − k), т. е., G(n − 2) + G(n − 3) + . + G(n − n) = G(0) + G(1) + . + G(n − 2). Эту сумму надо ещё умножить на 2, для двух возможных направлений (влево и вправо), и ещё на 2 для двух возможных строк для начальной точки. Количество вариантов для 3) равно G(n − 1), и это надо умножить на 2 для двух возможных строк для начальной точки, и ещё на 2 для положения единицы слева и справа. Итого:
Теперь составим рекуррентное соотношение для G(n). Рассмотрим те же три варианта (помним, что 1 находится в левом нижем углу).
Вариант 1) невозможен по тем же причинам.
Вариант 2) по сути означает такую картинку
то есть k = n, это даёт ровно один вариант при n > 1 и ни одного варианта при n = 1.
Вариант 3) остаётся неизменным и даёт G(n − 1) вариант.
Отсюда легко выходит, что G(n) = n при n > 0.
Окончательно получаем: F(100) = 4 × ([1 + 1 + 2 + 3 + . + 99]) = 4 + 4 × 99 × 100 / 2 = 19804.
Надеюсь, что нигде не ошибся.
Лемма 1. Фрагмент пути может быть только двух видов: змейка или петля. Змейка – непрерывная цепочка вертикальных П-образных фрагментов, где чередуется их вертикальная направленность. Петля – горизонтальный П-образный фрагмент, где ножки могут быть любой (и разной) длины.
Лемма 2. Петля хотя бы с одной стороны подходит к краю.
Лемма 3. Петель может быть 0, 1 или 2.
Лемма 4. Змеек может быть 0 или 1. Наличие Змейки разрывает концы Пути (0 и 200). При отсутствии змейки концы соседствуют.
Минимальной длиной Петли по горизонтали считаем 1 переход (2 значения):
Минимальной длиной Змейки по горизонтали считаем 2 перехода (3 значение по гор.:
Петля и змейка. Минимальная длина такой штуки - 4. 96 остаётся для распределения. Сколькими способами можно составить 96 из двух натуральных слагаемых, считая нули? 0+96, 1+95 .. 95+1, 96+0 = 97 вариантов. Не забыть домножить на 2 (порядок змейки и петли), и на 4, т.к. симметрия. +776
В случае, когда есть 2 петли и змейка, минимальная длина такой конструкции 5: ПZП . Остаётся 95 позиций для распределения среди трёх элементов. Задача сводится к кол-ву композиций 95 из трёх слагаемых, считая нули, и учитывая порядок. Формула для кол-ва композиций числа n из k слагаемых, считая нули:
Пусть верхняя часть N = n + k - 1 , а нижняя M = k - 1 . Вычисляется как
Для 95 и 3 у меня получилось 4656 и домножить на 4. +18624
Результат: 19804. А теперь выкладывайте простой, как двоичные числа, тривиальный вариант решения, который наверняка есть. )
Upd. глядя на два независимых других результата @pavel-mayorov и @vladd, исправил ошибку у себя – не учитывал сначала порядок змейки-петли в варианте 1:1.