Задача о картине, веревке и гвоздях

Недавно с помощью знакомого откопал, как я понимаю, старую задачу, условие которой формулируется следующим образом: Имеется картина, к которой обоими концами прикреплена длинная веревка. Необходимо повесить её на стене с помощью N гвоздей таким образом, чтобы при удалении любого (одного) гвоздя картина и веревка падали.

Для случая, когда гвоздь всего один, задача решается элементарно.
Будем разбираться, как её решить для 2-ух и более гвоздей. Рассмотрим ситуацию с 2-мя гвоздями. Обозначим их A и B. Введем операции (+) и (-), когда веревка обматывает гвоздь по часовой и, соответственно, против часовой стрелки. Таким образом, A + B означает, что гвозди A и B обмотаны веревкой по часовой стрелке 1 раз (по отдельности или вместе - в данном случае это не играет особой роли).
Также понятно, что A + (-A) = 0, так как мы оборачиваем гвоздь А по часовой стрелке, и тут же снимаем с него веревку против часовой стрелки. Итоговое значение 0 означает, что картину с веревкой ничего не удерживает, и они гарантированно упадут.
Удаление гвоздя будем отмечать заменой соответствующей буквы на число 0 (гвоздь перестает играть роль в процессе удержания картины). Таким образом, для того, чтобы условие задачи выполнялось, необходимо получить такую формулу, когда замена какой-либо одной (любой) буквы, обозначающей гвоздь, приводит всю формулу к нулевому значению.


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

A + B - A - B.

Заметим, что мы не можем располагать буквы одного гвоздя рядом (например, A - A или B - B).
В формуле выше при замене A на 0 (удаляем гвоздь) получаем выражение B - B. Которое, как мы выяснили ранее, равно 0. Аналогичную картину получаем и при замене буквы B на 0 (A - A тоже равно 0).
То есть, мы видим, что применяя обмотку по этой схеме, мы получаем решение задачи для двух гвоздей. Таких "базовых" формул может быть несколько (например, -A -B +A +B,
и так далее).

Теперь попробуем найти решение для ситуации, когда количество гвоздей больше двух.
Применим метод индукции. Если для N гвоздей доказано, что,  Z_{n} = 0 (под Z будем понимать функцию преобразования, которую мы ввели выше), то тогда совершенно очевидно, что, обозначив за C_{n+1} - n+1-ый гвоздь, можно утверждать, что выражение

Z_{n+1} = -Z_{n} + -C_{n+1} + Z_{n} + C_{n+1}

представляет решение нашей задачи, так как при Z_{n} = 0 (а значит, что и -Z_{n} = 0) формула вырождается в

Z_{n+1} = -C_{n+1} + C_{n+1},

что всегда равно 0.

Таким образом, имея N гвоздей, всегда можно найти такой вариант, при котором удаление любого из гвоздя приведет к тому, что картина упадет вниз. Для этого нужно лишь придерживаться правил обмотки веревкой гвоздей, которые мы получим в соответствии с нашей формулой.

В заключение, я попробовал написать небольшую программку на Haskell, которая бы формировала последовательность шагов по обмотке гвоздей веревкой для решения нашей задачи. Получилось нечто такого вида:


====== file picture.hs ======
turn_one [] = []
turn_one ('-':xs) = xs
turn_one x = '-' : x

turn [] = []
turn lst = reverse (map turn_one lst)

show_elem n sign = sign ++ show n ++ "g"

make_lst n = if n == 1 then [b ""] else turn a ++ [b "-"] ++ a ++ [b ""]
                    where
                          a = make_lst (n-1)
                          b = show_elem n

main = print (make_lst 10)
=======================


В последней строке здесь формируется последовательность, в частности, для 10 гвоздей. С удивлением обнаружил, что для этого придется "обвязывать" гвозди аж 1534(!) раза :)