#алгоритм #математика
В тетрадке нарисован прямоугольник 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 конструкций приведённого выше вида.
Комментариев нет:
Отправить комментарий