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