5 дек. 2011 г.

Надёжная поломка

И даже если завтра появится телефон, аккумулятор
которого держит заряд 1000 лет, уже через месяц его придётся
поменять на новый, который держит заряд 2000 лет.

Добрый день!

Сегодня мы будем решать топологическую задачку, но сперва небольшое введение в проблему. Людей на Земле много, а дел для них уже мало, поэтому перед человечеством стоит сложнейшая задача — хоть чем-то занять скучающие миллиарды. Современные технологии уже давно могут удовлетворить все базовые потребности человека, поэтому банальным производством нужных вещей заниматься недостаточно (почти всё необходимое запросто может быть произведено не очень большой группой людей). Тогда остаётся только производить что-то ненужное, чем население планеты и занято почти всю жизнь (и даже находит в этом радость).

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

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

Пояснения:
- верёвка может касаться картины только в двух местах (в точках крепления),
- верёвка очень прочная (не рвётся) и тонкая (можно сделать сколько угодно витков вокруг гвоздя),
- силой трения можно пренебречь (верёвка от трения о гвозди или саму себя не воспламенится),
- гвозди перпендикулярны стене и не гнутся под весом картины и верёвки
(т.е. всё без хитростей),
- если хочется, то можно считать, что гвозди расположены на стене каким-то фиксированным образом (как вам будет удобнее решать).

Для одного гвоздя задачка решается элементарно.
Для N=2 многие уже решали в детском саду/начальной школе.
А как решить для N>2?
А можно ли решить так, чтобы длина верёвки не зависела от N экспоненциально?

Хорошего вам решения!

24 комментария:

  1. Прочитав вступление, подумал, что, возможно, Вам будет интересно ознакомиться вот с этим постом: http://domestic-lynx.livejournal.com/50493.html (там есть еще продолжение в трех последующих постах)

    ОтветитьУдалить
  2. Что-ж это такое-то? Я при N=2 никак придумать не могу.

    ОтветитьУдалить
  3. Анонимный05.12.2011, 15:30

    Этот комментарий был удален администратором блога.

    ОтветитьУдалить
  4. Анонимный05.12.2011, 15:36

    Видимо, я тоже ходил не в ту школу или садик. Даже для N=2 не могу придумать...

    ОтветитьУдалить
  5. Alexiski, да, это читал, спасибо.

    Саша и уважаемый аноним, верёвку на паре гвоздей разумным образом расположить можно очень малым количеством способов. Я уверен, что вы вот-вот найдёте решение.

    Уважаемый аноним, я удалил Ваш комментарий, так как ещё рано такие картинки показывать.

    ОтветитьУдалить
  6. Или крепление развалится, или веревка будет цепляться. Предлагаю вариант: трение о гвозди отсутствует.

    ОтветитьУдалить
  7. Если , обозначит точками А и Б, точки крепления к картине а цифрами от 1 до N номера гвоздей то в случае "змейки" то есть крепления А,1,А,2....А,N,Б,N,Б,N-1....Б,1,Б получим что в случае вытаскивания любого из гвоздей картина про виснет, грубо на расстояние от А до среднего гвоздя.

    ОтветитьУдалить
  8. Эх. Плохой я ученик: посмотрел готовое решение в интернете. Да уж. Ничего кроме разочарования. В своих решениях был близко, но уходил куда-то в сторону.
    Для N гвоздей попробую сам.

    ОтветитьУдалить
  9. Анонимный05.12.2011, 18:32

    Я не понимаю: веревка, при этом должна касаться всех гвоздей или при этом я могу забить все остальные гвозди выше?)
    Не нашел этого в условии

    ОтветитьУдалить
  10. Анонимный05.12.2011, 19:12

    > веревка, при этом должна касаться всех гвоздей или при этом я могу забить все остальные гвозди выше?
    Забивать-то точно ничего не надо. Как обычно картину на один гвоздь вешают? Вбивают его в стену, оставляя торчать шляпку и ещё несколько миллиметров, чтобы веревочка там держалась.
    Я вот для двух гвоздей смог нарисовать, но как хотя бы с тремя разобраться ума не приложу.

    ОтветитьУдалить
  11. мне когда-то задавали эту задачу, правда задающий сам ответа и не знал и потому ответ мой не смогли ни зачесть, ни опровергнуть. Мне сейчас прям интересно стало, правильно ли я ее тогда решил)
    Надо гвозди вбить в стену по самые шляпки и таким образом, чтобы извлечение из стены одного гвоздя создавало большой кусок свободно висящей веревки, например, так: (для n = 3)
    * *

    *
    веревка протягивается над первым, под вторым, над третьим гвоздями и картина висит в таком положении. При извлечении любого гвоздя получается большой кусок свободно провисающей веревки, картина начнет падать, а силы рывка при натяжении веревки, когда та вновь натянется на шляпки гвоздей, хватит на то, чтобы эту самую веревку с этих шляпок "сшибить" (поскольку, в принципе, такое положение веревки, когда она лежит на шляпке, а не на самом гвозде, неустойчивое)

    ОтветитьУдалить
  12. Еще идея появилась.Исходя из "веревка тонкая (можно сделать сколько угодно витков вокруг гвоздя)" и "силой трения можно пренебречь" то на каждый из гвоздей накручивается веревка длинной до пола*2... :)

    ОтветитьУдалить
  13. Basilevs,
    да, конечно, задача математическая, а не физическая.

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

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

    Chubakarell,
    тогда картина не упадёт, если вынуть любой гвоздь... В любом случае, давайте ещё потребуем, чтобы расстояние от картины до пола было равно длине верёвки. Тогда проблемы с этим точно не будет :)

    ОтветитьУдалить
  14. С хабрахабра: http://habrastorage.org/storage1/9a7b1c86/80176217/45a6843d/177356eb.png "Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину. "

    ОтветитьУдалить
  15. Yury Nikalayuk,
    спасибо за ссылку на это оригинальное физическое решение. Мне в этой задаче интересны математические идеи, но и физические хитрости тоже забавно увидеть :)

    Вопрос ко всем:
    почему ещё никто не прислал ссылку на картинку с решением для двух гвоздей?
    ;)

    ОтветитьУдалить
  16. Илья, спасибо за задачу.
    как я понимаю веревку нельзя разрезать? иначе обнаруживается очень простое решение :).

    ОтветитьУдалить
  17. Алексей,
    да, конечно нельзя. В условии требуется привязать оба конца верёвки к картине (а если разрезать, то будет больше, чем два конца).

    ОтветитьУдалить
  18. для N=2 решение нашлось быстро.
    сложнее было для N>3. но наши победили )))

    ОтветитьУдалить
  19. Пронумеруем гвозди от 1 до N: g(1), g(2) ... g(N).
    Если надо зацепить веревку вокруг i-го гвоздя по часовой стрелке, то обозначаем как +g(i), против часовой соответственной будет -g(i).
    Для одного гвоздя зацепление тогда описывается как +g(1) или +g(1).

    Для N=2 решается несложно, искомая комбинация: G(2) = +g(1)-g(2)-g(1)+g(2), картинку ищите сами в инете :)
    Если вынимаем гвоздь 1, то в формуле g(1) выкидывается, остается -g(2)+g(2) = 0, т.е. веревка за гвоздь 2 не зацеплена.

    Далее по индукции. Пусть у нас есть решение для N-1 гвоздей в виде комбинации G(N-1), которая обращается в ноль при вытаскивании любого гвоздя.
    Тогда для N составляем формулу: G(N) = +G(N-1)-g(N)-G(N-1)+g(N).
    Вроде все.

    ОтветитьУдалить
  20. Анонимный08.12.2011, 2:39

    Дима, стоит добавить, что нельзя пропускать верёвку под ранее намотанной частью и выстроить гвозди в ряд. Первое позволит избежать возможного запутывания верёвки вокруг неё самой. Второе не меняет топологию задачи, что несложно доказать, но позволит строже сформулировать, что значит "зацепить веревку вокруг i-го гвоздя" - это будет означать, что верёвка пересекает линию, по которой вбиты гвозди после i-го, но до i+1-го (если такой есть) гвоздя.

    ОтветитьУдалить
  21. Анонимный, небольшие уточнения:
    1. Если пропускать веревку под предыдущими витками, то это будет означать зацепление веревки за себя с образованием узлов. Такое не рассматриваем, иначе это совсем другой случай.
    2. Для наглядности проще расположить гвозди на дуге окружности, а зацепление за гвоздь выполняеть от центра этой окружности с возвратом туда же.

    ОтветитьУдалить
  22. Анонимный08.12.2011, 22:37

    Воистину загадочен мозг программиста. Эту задачу решил за 10 (ну, может, 15) минут.

    При этом уже второй час подряд в пейнте, как дурак, рисую кружочки, чтобы создать фигуру из 10 монеток с 5ю прямыми.

    Спасибо за задачу!

    ОтветитьУдалить
    Ответы
    1. Анонимный15.03.2012, 15:27

      если вы про 10 гвоздей , то рисовать задолбаетесь
      для 4х гвоздей попробуйте и не в пейнте а на гвоздях или в худшем случае на пальцах с ниткой, а то вам ошибки алгоритма не будут видны

      все вроде вумные, и даже думают что понимают общую формулу, а вот почему для 10 гвоздей более 1500 петель нужно - объяснить не могут

      Удалить
  23. Yury Nikalayuk
    "Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину."
    В условии:
    "чтобы вытаскивание [b]любого[/b] гвоздя из стены приводило к падению картины"
    Так что ответ не подходит )

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний