четверг, 29 июля 2010 г.

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

Недавно с помощью знакомого откопал, как я понимаю, старую задачу, условие которой формулируется следующим образом: Имеется картина, к которой обоими концами прикреплена длинная веревка. Необходимо повесить её на стене с помощью 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(!) раза :)

8 комментариев:

  1. tvolf здравствуйте, вы ответ выложили ради кликов, похвастаться или чтобы людям удовольствие от решения обломать ?)

    ОтветитьУдалить
  2. я не всмысле протеста )), вы же как программер для программеров пишите, оставили бы общую теорию и формулу с кодом, а такое разжевывание для 2х гвоздей - лучше бы написали как все не тривиально и в каком направлении двигаться чем вот так все на блюдечке )

    ОтветитьУдалить
  3. Доброе утро.
    Во-первых, спасибо большое за отклик.
    Если честно, решение выкладывал без каких-либо задних мыслей попортить и без того нелегкую жизнь программистам :)
    Возможно, конечно, не очень хорошо выкладывать разжеванное решение, но по себе знаю, что иногда так хочется понять, как решается та или иная задача, что, как говорится, "зубы ломит" :)

    ОтветитьУдалить
  4. Ну и потом, не исключено, что мои решения не всегда лучшие, оптимальные (да и вообще правильные :), поэтому расписав всё так подробно, возможно, найдется тот, кто заметит какие-то очевидные огрехи и отпишет мне об этом.
    Это было бы замечательно. Ну а в качестве компенсации посмотрите мой последний пост о задаче с большим потоком целых чисел. В конце его есть дополнительное условие, при котором решить задачу красиво у меня пока никак не получается. Возможно, вы бы что-то посоветовали ? )

    ОтветитьУдалить
  5. спасибо большое, мне очень помогло.

    ОтветитьУдалить
  6. В задаче надо предложить вариант, а не доказать его существование. Какой у Вас вариант для 3-х гвоздей?

    ОтветитьУдалить
    Ответы
    1. Добрый вечер. Перечитал еще раз свой пост и вижу, что в нем присутствует не только доказательство того, что такое обвязывание вообще возможно, но и предлагается решение для общего случая, когда имеется N гвоздей. В частности, для 3-ех гвоздей Haskell мне выдал следующую последовательность действий:
      ["-2g","-1g","2g","1g","-3g","-1g","-2g","1g","2g","3g"]
      где 1,2,3 - номера гвоздей, "-" обвязывание против часовой стрелки, "+" (отсутствие знака) - обвязывание по часовой стрелке.
      А вообще очень приятно, что даже и через 5 лет этот пост кто-то читает и комментирует ) Большое вам человеческое спасибо.

      Удалить