которого держит заряд 1000 лет, уже через месяц его придётся
поменять на новый, который держит заряд 2000 лет.
Добрый день!
Сегодня мы будем решать топологическую задачку, но сперва небольшое введение в проблему. Людей на Земле много, а дел для них уже мало, поэтому перед человечеством стоит сложнейшая задача — хоть чем-то занять скучающие миллиарды. Современные технологии уже давно могут удовлетворить все базовые потребности человека, поэтому банальным производством нужных вещей заниматься недостаточно (почти всё необходимое запросто может быть произведено не очень большой группой людей). Тогда остаётся только производить что-то ненужное, чем население планеты и занято почти всю жизнь (и даже находит в этом радость).
Сложности начинаются, когда заметно вырастает доля несознательных граждан, которые не желают покупать ненужное, а способны оценить полезность предмета до того, как он пролежит на антресолях два года. Против таких людей включается машина хлипких вещей. Вот вроде бы и нужная штука, но проработает ровно до истечения гарантийного срока. И так мастерски она сделана, что даже если починить, то всё равно скоро что-нибудь новое в ней поломается. Это целое искусство разработать такую конструкцию, которая от малейшего колыхания ветра может развалиться на мелкие кусочки, целые НИИ разрабатывают такие механизмы. И сегодня мы с вами будем решать эту же задачу :)
Итак, есть картина, которую нужно повесить на вертикальную стену, есть верёвка, от которой мы можем отрезать сколь угодно длинный кусок, есть N гвоздей, забитых в стену. Требуется привязать оба конца верёвки к картине, после чего повесить картинку на эти гвозди так, чтобы вытаскивание любого гвоздя из стены приводило к падению картины. Ну а если ничего не трогать, то картина должна спокойно висеть на всех N гвоздях.
Пояснения:
- верёвка может касаться картины только в двух местах (в точках крепления),
- верёвка очень прочная (не рвётся) и тонкая (можно сделать сколько угодно витков вокруг гвоздя),
- силой трения можно пренебречь (верёвка от трения о гвозди или саму себя не воспламенится),
- гвозди перпендикулярны стене и не гнутся под весом картины и верёвки
(т.е. всё без хитростей),
- если хочется, то можно считать, что гвозди расположены на стене каким-то фиксированным образом (как вам будет удобнее решать).
Для одного гвоздя задачка решается элементарно.
Для N=2 многие уже решали в детском саду/начальной школе.
А как решить для N>2?
А можно ли решить так, чтобы длина верёвки не зависела от N экспоненциально?
Хорошего вам решения!
RSS-feed
Прочитав вступление, подумал, что, возможно, Вам будет интересно ознакомиться вот с этим постом: http://domestic-lynx.livejournal.com/50493.html (там есть еще продолжение в трех последующих постах)
ОтветитьУдалитьЧто-ж это такое-то? Я при N=2 никак придумать не могу.
ОтветитьУдалитьЭтот комментарий был удален администратором блога.
ОтветитьУдалитьВидимо, я тоже ходил не в ту школу или садик. Даже для N=2 не могу придумать...
ОтветитьУдалитьAlexiski, да, это читал, спасибо.
ОтветитьУдалитьСаша и уважаемый аноним, верёвку на паре гвоздей разумным образом расположить можно очень малым количеством способов. Я уверен, что вы вот-вот найдёте решение.
Уважаемый аноним, я удалил Ваш комментарий, так как ещё рано такие картинки показывать.
Или крепление развалится, или веревка будет цепляться. Предлагаю вариант: трение о гвозди отсутствует.
ОтветитьУдалитьЕсли , обозначит точками А и Б, точки крепления к картине а цифрами от 1 до N номера гвоздей то в случае "змейки" то есть крепления А,1,А,2....А,N,Б,N,Б,N-1....Б,1,Б получим что в случае вытаскивания любого из гвоздей картина про виснет, грубо на расстояние от А до среднего гвоздя.
ОтветитьУдалитьЭх. Плохой я ученик: посмотрел готовое решение в интернете. Да уж. Ничего кроме разочарования. В своих решениях был близко, но уходил куда-то в сторону.
ОтветитьУдалитьДля N гвоздей попробую сам.
Я не понимаю: веревка, при этом должна касаться всех гвоздей или при этом я могу забить все остальные гвозди выше?)
ОтветитьУдалитьНе нашел этого в условии
> веревка, при этом должна касаться всех гвоздей или при этом я могу забить все остальные гвозди выше?
ОтветитьУдалитьЗабивать-то точно ничего не надо. Как обычно картину на один гвоздь вешают? Вбивают его в стену, оставляя торчать шляпку и ещё несколько миллиметров, чтобы веревочка там держалась.
Я вот для двух гвоздей смог нарисовать, но как хотя бы с тремя разобраться ума не приложу.
мне когда-то задавали эту задачу, правда задающий сам ответа и не знал и потому ответ мой не смогли ни зачесть, ни опровергнуть. Мне сейчас прям интересно стало, правильно ли я ее тогда решил)
ОтветитьУдалитьНадо гвозди вбить в стену по самые шляпки и таким образом, чтобы извлечение из стены одного гвоздя создавало большой кусок свободно висящей веревки, например, так: (для n = 3)
* *
*
веревка протягивается над первым, под вторым, над третьим гвоздями и картина висит в таком положении. При извлечении любого гвоздя получается большой кусок свободно провисающей веревки, картина начнет падать, а силы рывка при натяжении веревки, когда та вновь натянется на шляпки гвоздей, хватит на то, чтобы эту самую веревку с этих шляпок "сшибить" (поскольку, в принципе, такое положение веревки, когда она лежит на шляпке, а не на самом гвозде, неустойчивое)
Еще идея появилась.Исходя из "веревка тонкая (можно сделать сколько угодно витков вокруг гвоздя)" и "силой трения можно пренебречь" то на каждый из гвоздей накручивается веревка длинной до пола*2... :)
ОтветитьУдалитьBasilevs,
ОтветитьУдалитьда, конечно, задача математическая, а не физическая.
Уважаемый аноним, считайте, что гвозди забивать нельзя (они уже как-то расположены на стене), а надо только повесить картину на них.
Павел,
здесь предполагается честное математическое решение. Ваш оригинальный подход с физическими эффектами тоже интересен, но сейчас я предлагаю рассматривать именно топологический аспект.
Chubakarell,
тогда картина не упадёт, если вынуть любой гвоздь... В любом случае, давайте ещё потребуем, чтобы расстояние от картины до пола было равно длине верёвки. Тогда проблемы с этим точно не будет :)
С хабрахабра: http://habrastorage.org/storage1/9a7b1c86/80176217/45a6843d/177356eb.png "Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину. "
ОтветитьУдалитьYury Nikalayuk,
ОтветитьУдалитьспасибо за ссылку на это оригинальное физическое решение. Мне в этой задаче интересны математические идеи, но и физические хитрости тоже забавно увидеть :)
Вопрос ко всем:
почему ещё никто не прислал ссылку на картинку с решением для двух гвоздей? ;)
Илья, спасибо за задачу.
ОтветитьУдалитькак я понимаю веревку нельзя разрезать? иначе обнаруживается очень простое решение :).
Алексей,
ОтветитьУдалитьда, конечно нельзя. В условии требуется привязать оба конца верёвки к картине (а если разрезать, то будет больше, чем два конца).
для N=2 решение нашлось быстро.
ОтветитьУдалитьсложнее было для N>3. но наши победили )))
Пронумеруем гвозди от 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).
Вроде все.
Дима, стоит добавить, что нельзя пропускать верёвку под ранее намотанной частью и выстроить гвозди в ряд. Первое позволит избежать возможного запутывания верёвки вокруг неё самой. Второе не меняет топологию задачи, что несложно доказать, но позволит строже сформулировать, что значит "зацепить веревку вокруг i-го гвоздя" - это будет означать, что верёвка пересекает линию, по которой вбиты гвозди после i-го, но до i+1-го (если такой есть) гвоздя.
ОтветитьУдалитьАнонимный, небольшие уточнения:
ОтветитьУдалить1. Если пропускать веревку под предыдущими витками, то это будет означать зацепление веревки за себя с образованием узлов. Такое не рассматриваем, иначе это совсем другой случай.
2. Для наглядности проще расположить гвозди на дуге окружности, а зацепление за гвоздь выполняеть от центра этой окружности с возвратом туда же.
Воистину загадочен мозг программиста. Эту задачу решил за 10 (ну, может, 15) минут.
ОтветитьУдалитьПри этом уже второй час подряд в пейнте, как дурак, рисую кружочки, чтобы создать фигуру из 10 монеток с 5ю прямыми.
Спасибо за задачу!
если вы про 10 гвоздей , то рисовать задолбаетесь
Удалитьдля 4х гвоздей попробуйте и не в пейнте а на гвоздях или в худшем случае на пальцах с ниткой, а то вам ошибки алгоритма не будут видны
все вроде вумные, и даже думают что понимают общую формулу, а вот почему для 10 гвоздей более 1500 петель нужно - объяснить не могут
Yury Nikalayuk
ОтветитьУдалить"Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину."
В условии:
"чтобы вытаскивание [b]любого[/b] гвоздя из стены приводило к падению картины"
Так что ответ не подходит )