Pull to refresh

Comments 151

Под падали подразумевается, что она должна начать движение вниз, или что это движение потом не должно прекращаться?
Это я к чему. Если гвоздики забить в шахматном порядке выше-ниже (хотя можно и лево-право) и пропустить веревку змейкой через все их — то вытаскивание любого приведет к проскальзывании картины вниз на расстояние между этими шахматными рядами. Вроде как при большом расстоянии можно считать, что картина падает.

Хотя это, наверняка, не тот вариант :)
Движение не должно прекращаться. Считайте, что внизу, на расстоянии, многократно превосходящем длину веревки, находится пол. Тогда картина должна достигнуть пола.
Эммм, тупо на одном гвозде? при его вытаскивании картина упадет.
Так в задаче же не один гвоздь, а практически любое их количество.
Сказанно, N. Ограничения на него не даны, потому и можно предположить что N=1. А вообще, в задаче по факту не стоит то, что требуется найти. Взаимное расположение гвоздей и веревки для любого N? Из формулировки «Требуется повесить её на N вбитых в стену гвоздей так, чтобы при вытаскивании из стены одного любого гвоздя картина и веревка падали. » как раз и вытекает, что требование задачи — сделать падающую картину. И можно взять для этого любое количество гвоздей. Вот я и взял то количество, что посчитал нужным — 1.
Требуется найти решение (решение = расположение гвоздей и конфигурация веревки) для произвольного натурального N.
Нехорошо такие задачки в разгар понедельника постить.
image

Я за 13 минут решил, не слабо меня замкнуло =)
Я понимаю, условие «повесить на N гвоздей» означает «каждый из N гвоздей должен касаться веревки»?
Если сможете так, чтобы некоторых гвоздей веревка не касалась (но чтобы картина падала при выдергивании любого гвоздя) — пожалуйста :)
Если найдете решение, где гвозди будут не касаться, пишите :)
Казалось бы, к чему сейчас эта картинка стоит перед мысленным взором
image
В этом случае автор рискует :)
Черного властелина тут не будет, не переживайте. Решение я знаю, вывешу завтра утром.
Спасибо за ещё одну вкладку в моем браузере!
Мне кажется тут что-то с натяжением верёвки — один гвоздь убираешь, верёвка даёт слабину и сползает.
Как один из неправдоподобных вариантов: сложить верёвку вместе и продеть её через N рядом стоящих гвоздей так, чтобы верёвка касалась каждого из них. Картина держится на трении, гвозди вбиты так, что убирая любой из них трение уменьшается, становится не достаточным, верёвка проскальзывает и картина падает.
Нет, это задача чисто на топологию.
А, забыл что в условии сказано про трение…
трении между веревкой и гвоздями?
Может лучше сложить веревку, протянуть её между гвоздями в шахматном порядке (чтобы приходила в движение при убирании любого гвоздя) и замкнуть её — сделать как бы нахлест… Тогда она вероятно выскользнет.
Эмм… Нарисуйте, пожалуйста. Только учтите, трения нет.
точно трения нет :)
Давайте представим, что это не картина, а микроскоп, тогда можнно сменить топпик на «Микроскоп и гвозди» 8))
Хотите, чтобы за вас решили пятибальную задачу с braingames? ;)
1) Эту задачу на braingames (пятибалльную, да) я уже решил.
2) После очередного падения braingames эта задача оттуда пропала. Когда добавят обратно — неясно.
Спасибо! Я искал по неправильному названию, оказывается.
А зачем на хабр выложили? Просто чтобы другие мозги понапрягали? :)

Да, кстати, из-за падения пропали большие решения некоторых задач (надо же было их именно в это время посылать =_=). Теперь снова все это печатать уже не хочется…
Задача показалась мне интересной (и не только мне, на braingames у нее 100% симпатии решивших), захотелось поделиться с сообществом.
С падением bg у меня грохнулись вообще все решения. Впору было делать FFUUU-рожу.
Кошмар… x_x
У меня, славабогу, 2-5 летней давности решения остались. )
Да, задача и мне тоже очень нравится, правда, я до ее решения так и не добралась. Вообще редко получается решать задачки, более важные дела не позволяют часто заходить на брейнгеймс… (
Один гвоздь.

Надо вбить гвоздь в стену через веревку. Таким образом, гвоздь будет чем-то вроде «затычки», удерживая веревку.

Вынимаете этот гвоздь — картина падает.
Хотя не, если так вколотить пару гвоздей, другой удержит. Хм…
Тут всё не так сложно. На самом деле, особо рисовать не надо, тут просто индукцией доказывается что если мы смогли повесить её на N гвоздей, то нехитрым способом сможем забить еще 1 гвоздь и повесить её в соответствии с условиями, зная как вешать на N гвоздей.
Ну хоть шнурки из ботинок доставай!
Я с патчкордом решал :)
Думаю, тут идея в том, что гвозди могут быть вбиты в стену на произвольную глубину. И/или могут быть разной длины.
Нет. Не ищите подвоха там, где его нет.
«Имеется картина, к которой двумя концами привязана длинная веревка. Требуется повесить её на N вбитых в стену гвоздей...»

Кого её? Картину или веревку?
Картину ставим на два гвоздя, выдергиваем любой — картина падает вместе с веревкой.

На любое N решение не масштабируется :-)
Повесить — картину за верёвку, естественно. Решение должно масштабироваться для любого натурального N.
Первое что пришло в голову: вбить все гвозди в один вертикальный ряд, достаточно близко и глубоко. Веревку продеть перекрученной следующим образом: на самый высокий гвоздь (первый) вешать как обычно (без перекручивания), перевернуть картину мордой к стенке, положить перекрестие на второй гвоздь, перевернуть картину обратно, положить перекрестие веревки на третий гвоздь и т.д. При выдергивании любого гвоздя веревка начинает раскручиваться, и слетает с гвоздей.
Интересно, насколько далеко я от решения. :)
Допустим, вынимаем второй снизу гвоздь. На самом верхнем верёвка продолжает висеть?
С помощью петель получилось решить для N=2. Для большего N — главное не запутаться. )
Да, для N=2 именно так. Теперь ищите общий случай.
Вариант: Выдернуть гвоздь из картины, где веревка крепится.
И подписать его «один любой».
Вспомнился анекдот про рыбака и бумажку «червь жирный»…
Для двух: расположить гвозди один под другим, веревку, сложенную вдвое, обвести сначала мимо нижнего гвоздя, потом обвернуть над верхним и, наконец, зацепить петлей за нижний гвоздь.
Тогда это и есть решение. Нужно продолжать эту мысль на все остальные гвозди.
Если верхний вытянуть — на нижнем повиснет.
Значит ты не правильно перевернул петлю. Мы тут уже повторили эксперимент — работает. nightday — в победители!
надо индукцию еще правильно дальше провести
Э, куда минус, все верно, повиснет.
Рисунок неоднозначный. Если пересечение справа внизу — пересечение, то не повиснет. Но может показаться, что там просто касается.
При выдергивании верхнего картина остаётся висеть на нижнем.
Прежде, чем минусовать, посмотрите внимательно на картинку. Вокруг нижнего гвоздя петля и при вытаскивании верхнего петля вокруг гвоздя никуда не рассосётся. Вариант, который предложил FrollowMi ниже — правильнее.
Там тоже-самое только горизонтально.
Коллега, не спешите, полевые опыты с веревкой, доской, гвоздями и молотком, но без стены и картины доказывают, что не виснет.

Был неправ, каюсь.
Господа, Вы разрушили мой маленький мир. Сидя на работе я мог проверить это только визуально, но, придя домой, повторил эксперимент с реальными гвоздями и веревкой. Также приношу свои извинения за поспешные выводы.
По условиям ясно, что веревка ОБЯЗАТЕЛЬНО касается всех гвоздей. Потому что при выдергивании любого она должна упасть. Взял резинку, набил гвоздей, сижу протягиваю резинку меж них…
Мне кажется тут надо быть последовательным:
— как решить для N=1 всем понятно
— для N=2 уже сложнее, вот картинка одного из возможных вариантов:
image

кто для N=3 нарисует? там, глядишь, и до логического разрешения не далеко, хоть и не уверен
Собрали консилиум, тренируемся на 3х чашках!
Тема сисек раскрыта. =)


Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину. На рисунке — «вид сверху».
Я чего то не понял или картина весит только на последнем гвозде? А если я любой другой выдерну?
Видимо подразумевается, что вытягивая любой из гвоздей мы потянем шляпкой за шляпку (бабка за дедку) и вытащим гвоздь на котором картина.
Остроумное решение!
Это читерство! И потом, что будете делать, если вам выдадут гвозди без шляпок?
не сможет повесить )
вот уж действительно thinking out of the box
я бы Вас на работу сразу взял

хотя вроде как по условию задачи гвозди уже вбиты в стену
интересно кстати, могут ли они быть вбиты так что решения в принципе не существует…
Любое расположение точек-гвоздей на плоскости будет топологически эквивалентно любому другому их расположению. Так что можно добавить уловие, что гвозди уже вбиты произвольным образом. Только тогда нужно сделать оговорку, что мы можем потребовать веревку любой конечной длины.
ну а если вбить два гвоздя «абсолютно вплотную друг к другу»?
веревка по условию «имеет пренебрежимо малую толщину»
но непонятно чья мантра в кавычках сильнее в даннном случае, т.е. можно ли между такими двумя гвоздями веревку провести

опять же, в условии не плоскость а стена
есть ли у стены края? примыкает ли стена к другой стене так что гвоздь вбивается «абсолютно вплотную к соседней стене»?
а если гвозди полые и разной толщины и один вбит в другой?
какая тут нафик топологическая эквивалентность?
Если вы хотите строгую математическую формулировку условия, будет что-то вроде:
«На плоскости с N выколотыми точками необходимо задать нестягиваемую петлю, такую, что если вернуть на место любую из этих точек, то она станет стягиваемой».
Боюсь, коллеги, что для N>2 решений нет. Для двух предложили три человека решения, но эти решения не позволяют увеличить число гвоздей.
Решение для N>2 не является продолжением решения для N=2, оно основано на другом принципе.
Мне напомнило другую задачу с верёвкой, которая вроде бы решение имеет, но сложное. Задача по-моему из Мартина Гарднера.
На полу лежит закольцованная верёвка (у неё скреплены 2 конца). Она лежит неровно, несколько раз пересекается сама с собой. Нам не очень хорошо видны места пересечения, поэтому непонятно, какая часть сверху в каждом из пересечений, а какая снизу.
Зная количество пересечений, необходимо подсчитать вероятность того, что при растягивании верёвки она завяжется узлом (а не просто растянется в 2 параллельных отрезка).
Мой вариант. Там где толстая линия означает, что две нити идут.
Вытаскиваем любой, кроме того, что в петле и ничего не падает.
Кажись доперло наушниками на пальцах. Но мозги уже сварены, и буквописью не осилю.
Решение как-то связано с наматыванием в один оборот?
Что вы понимаете под «наматыванием в один оборот»?


Решение для трёх гвоздей. Основано на решении для двух гвоздей, но вместо гвоздей в первом случае пропускаются петли, которые идут дальше.
Аналогично расширяется «пирамидкой» до N гвоздей.
Ох ты ж..! Неужели правда работает?
Наврал, таки останется висеть. Надо ещё подумать в этом направлении.
Немного не те петли зарекурсировал, но решение явно видно.
Пока не видно :) Тут всегда кажется, что «еще чуть-чуть и получится». Попробуйте нарисовать правильное решение.
Прошу простить меня. Поторопился. Я просто на пальцах со шнурком проверил, а нарисовал не так как сделал.

habrastorage.org/storage1/4ba70191/9eeb3522/acb9205c/27f41475.jpg

Размотка по среднему:
habrastorage.org/storage1/b131559e/a2fddd9f/243da377/6d1d20ff.jpg
habrastorage.org/storage1/e6e13938/864012a4/a1d60e2c/23ace849.jpg
habrastorage.org/storage1/610ce3f9/ce856c2f/9a062e8f/09f0b304.jpg
Да, вы правы, левая конструкция ведет себя как 1 гвоздь, только если из нее гвоздь достают. В вот если ее не трогают, то ведет себя как петля… Надо подумать еще :)
Что-то туплю. Скорее так:
Если это решение правильное (а оно вроде бы да), то оно масштабируется до N.
Проверьте, пожалуйста, аккуратно ещё раз. У меня всё нормально получается.
Извините, всё верно. Я увидел два перехлёста там, где у вас один.
Решение для N=3 найдено! А каким образом оно масштабируется?
Точно так же: удваиваете верёвку, захлёстываете петлю за четвёртый гвоздь, и не забываете свободный конец завести за него. (Картинка кликабельна.)

Ух! Пожалуй, придется поверить вам на слово, т.к. проверять это я буду очень долго :)
Прочитал UPD2. ИМХО, решение всё-таки является рекурсивным, т.к. в каждом следующем варианте используется предыдущий, просто намотанный двойной верёвкой.
Нерекурсивное решение тоже есть, там на каждом гвозде висит не больше трех петель, независимо от N.
Чорт. А я-то думал, что смогу лечь спать сегодня. %)
Проверьте мои рассуждения, пожалуйста :)

Если обозначить гвозди цифрами 1, 2, 3.
Проход над гвоздем будет означать X, а под гвоздем -X.

Я нашел следующие варианты для 3-х гвоздей (есть и другие, но они уже менее оптимальны):
[1, -2, 2, 1, -1, 2, -3, 3, 2, -1, 1, 2, -2, 1, -1, -2, 3] [7, 7, 3] — наикратчайший вариант, предложенный Biga (вообще их 4 с точностью до переобозначения гвоздей)
[1, -1, -2, 2, -1, 1, 2, -3, 3, 2, 1, -1, 2, -2, -1, 1, -2, 3] [8, 7, 3]
[1, -1, -2, -3, 3, -2, 2, 3, -3, 2, -1, 1, 2, -3, 3, 2, -2, 3] [4, 7, 7]
[2, -1, 1, 2, 3, -3, 2, 1, -1, 2, -2, -1, 1, -2, -3, 3, -2, 1] [7, 7, 4]

Последний вариант проиллюстрирован:


Как я проверял правильность:
Для каждого X из {1, 2, 3}:
1) Выбрасываем все числа X и -X из последовательности.
2) Пока существует такое i, что list[i] == list[i + 1], удаляем из списка i-й и (i + 1)-й элементы.
3) Если в списке остались только отрицательные числа или список пуст, то — «картина упала», иначе нет.

Что-то я закономерностей не вижу… ну кроме как рекуррентно динамикой строить :)
Вы монстр! :) Рассуждения в целом верные, но не учитывается, в каком порядке идут друг над другом веревки в местах пересечений. Точнее, вы предполагаете, что они расположены наилучшим образом и не будут мешать распутыванию. На практике может возникнуть ситуация, подобная этой:

или этой:


P.S.: С утра еще повнимательнее гляну.
Да, не исключено, что нельзя так уложить, как получается в теории.
Надо будет подумать над этим…
Мне кажется, что решение для трёх гвоздей можно «зациклить» способом, аналогичным моей первой попытке: www.habrastorage.com/?v=wire.png
Будет время на работе — попробую придумать что-нибудь. =)
Не могу это описать словами, а тем более нарисовать. Сфоткал. Для 2х гвоздей получается красиво и наглядно, а вот для 3 уже мешанина( но принцип тот же, что и при переходе от одного гвоздя к двум)
1) Один гвоздь.


2) Два


3) Два с половиной


4) Три гвоздя


Для 4х пальцевгвоздей не пробовал — длины шнурка не хватает.
А разве при снятии шнура со среднего пальца конструкция не превращается обратно в то, что на первой фотографии?
Проверил — отлично снимается при убирании любого ил пальцев. Процесс перехода от 3 пункта к 4 такой же, как от перовго ко второму. Заводим петлю из п.3 за безымянный палец и накидываем на средний. При этом левая часть петли из 3-ей картинки будет ближе к нам.

Были бы гвозди сантиметров по 10 и длинная лента — можно было бы наглядно разложить. Тоже получилось бы красиво. Лента нигде не перегибается
Да, действительно, работает. Дальше, я так понимаю, N можно увеличивать рекурсивно? То есть за 4 палец заводится петля из 8 шнурков, за 5 — из 16 и т.д.
Можно и так, но думается что это не лучший способ. Из N=3 можно ещё использовать 2 шнурка с указательного пальца и обмотать их аналогичным образом вокруг большого( обмотать то получается, но вытащить из этой связки какой-то один палец я не могу, так что проверить не могу, но должно работать).

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

ЗЫ Чё-то я уже запутался в пальцах-гвоздях
Что-то я тоже запутался. Есть вариант без рекурсии, попробуйте найти его.
Вы в безымянный палец, случаем, не гвоздь вбивали?
Не, прищемил пассатижами
А если сложить веревку вдвое, поставить картину на гвоздь, пропустить сложенную вдвое верёвку (теперь как единую) по забитым в шахматном порядке гвоздям, а конец веревки подложить под картину на гвоздь, на котором она стоит. По условию задачи имеем право найти хрупкое равновесие?

Как-то так:
Ну, первый, второй гвозди надо бы расположить поправильнее, но саму суть попытался передать
Ваше «физическое» решение безупречно во всем, за исключением одного: оно использует силу трения, которое по условию отсутствует.
Возможно тут не трение, а гравитация и картина уравновешена на гвозде.
Ну а веревку между картиной и гвоздем что держит?
Картина не уравновешена на гвозде. Как показывает картинка, гвоздь смещен от центра вправо.

А веревку держит трение. Трение между гвоздем, веревкой, и картиной; которое зависит от гравитации/веса картины.
… а трения по условию задачи у нас нет…


0. Вариант с двумя гвоздями и вообще без верёвки.

1. Решение для одного гвоздя.
2. Решение для двух гвоздей.

Из решения с 1 гвоздём можно перейти к решению с двумя гвоздями. Видно, как область выделенная пунктиром сводится к решению с 1 гвоздём.

Это скорее всего повторение предыдущих рекурсивных решений… но как-то нагляднее и аккуратнее.
Выложил своё решение. Читаем UPD4.
Супер несущая петля на каждом гвозде держится не за гвоздь, а за петлю. Опять убеждаюсь, что верное решение очень изящно выглядит )
Мне при решении таких задач всегда кажется, что решение должен находить 5-10 летний человечек, по-моему в данном случае, это возможно
Это почти такой же узел, которым укладывали раньше стропы в парашюте! Очевидное рядом (:
Да, да. Долго думал что же оно мне напоминает, действительно стропы.
Очень круто. Приходило на ум что-то такое, но до конца додумать не смог
Вариант задачи без трения можно решить строго, для этого достаточно привлечь лишь элементарную теорию гомотопий. Я опишу суть решения, детали — по требованию.

Для начала нужно эту задачу формализовать. Мы будем считать, что стена — это плоскость, а веревка — это петля (замкнутый непрерывный путь) на ней. Картина выполняет просто роль груза и для решения задачи не нужна. Поскольку веревка никогда не сможет пройти сквозь гвоздь, то точки плоскости, в которые вбиты гвозди, можно считать выколотыми. Если в данной конфигурации картина упадет, то рано или поздно вся веревка окажется ниже всех гвоздей. Но поскольку движение непрерывно, это означает, что веревка упадет тогда и только тогда, когда соответствующая петля гомотопически эквивалентна тривиальной (т.е. ее можно непрерывным движением стянуть в точку).

Таким образом задача сводится к следующей: найти нетривиальную петлю на плоскости с выколотыми N точками, который станет тривиальной, если вернуть любую одну точку на место. Фундаментальная группа этого пространства — свободная группа с N порождающими (доказательство — по требованию, там будет довольно много писанины и поясняющих картинок, без латеха набрать нереально), можно зафиксировать их представителей, например, так:

image

Для определенности также зафиксируем направление их обхода — против часовой стрелки. Таким образом любому гомотопическому классу петель (т.е. любому элементу фундаментальной группы) мы сможем сопоставить реальную петлю, «намотанную» на эти представители в соответствии с ее выражением через порождающие.

Выниманию i-го гвоздя из стены в нашей формализации соответствует вкладывание нашей плоскости с N выколотыми точками в плоскость с N-1 выколотой точкой, обозначим его p_i. Ему сопоставляется гомоморфизм фундаментальных групп этих пространств P_i: Z a_1 *… Z a_N -> Z a_1 * ...* Z a_{i-1} * Z a_{i+1} *… * Z a_N, полностью задаваемый своим действием на порождающих: P_i(a_j) = a_j при i \neq j, P_i(a_i) = 1. Интуитивно это означает всего лишь, что i-й представитель стал стягиваемым, поэтому соответствующие гомотопические классы (a_i и 1) объединились в один.

Таким образом у нас есть N гомоморфизмов групп: P_1, ..., P_n. Задача сводится к отысканию нетривиального элемента фундаментальной группы исходного пространства, обращающегося в единицу под действием любого из них. Легко (с помощью матиндукции) убедиться в том, что таким элементом будет, например, [...[a_1, a_2], a_3], ...], a_N], где [x, y] = xyx^{-1} y^{-1} — коммутатор. Это следует из того, что в любой группе для любого элемента x выполняется равенство [1, x] = [x, 1] = 1 — единица коммутирует с любым элементом. Действительно, гомоморфизмы групп сохраняют коммутаторы (f([x, y]) = f(xyx^{-1}y^{-1}) = f(x)f(y)f(x)^{-1}f(y)^{-1} = [f(x), f(y)]), поэтому приведенный выше вложенный коммутатор обратится в единицу под действием любого P_i.

Важно отметить, что длина веревки, которая потребуется для практической реализации этого решения, будет расти экспоненциально с ростом N. Перспективы поиска более оптимального решения не очень оптимистичные, о чем мне сообщили здесь:
math.stackexchange.com/questions/80219/finding-verbally-smallest-element-of-a-finitely-generated-group

Если что-то непонятно или вы хотите, чтобы я лучше обосновал тот или иной переход, я буду рад пояснить столь подробно, сколь потребуется.
Заметим, что в этом решении считается, что вервка может свободно проходить сквозь саму себя (или, более реалистично, что как узел она тривиальна). Если искать решение среди нетривиальных узлов, возможно удастся найти намного более короткое. Я вижу, выше такие предложения уже есть, и это хорошо :)
Что значит «проходить сквозь саму себя»?
По сути это значит, что веревка намотана на гвозди так, чтобы она не могла запутаться о саму себя, т.е. «вид сбоку» — примерно такой, как в ссылке выше.
То есть мы предполагаем, что первая конфигурация может быть переведена во вторую:

Веревка здесь имеет свойства математической линии, и в точках самопересечения не имеют смысла рассуждения о том, какой участок веревки проходит «сверху», а какой «снизу».
А это не является ложной посылокой? Тем более, что ваше решение при таком допущении уже не работает.
Поскольку гвозди предполагаются достаточно длинными, вы можете просто наматывать веревку «спиралью», постепенно отдаляя ее от стены, концы при это соединятся в самом низу, где это ничему не помешает.
Мы считаем, что найдется такое расположение веревок в каждой точке самопересечения, при котором они друг за друга не цепляются. Хотя, по-хорошему, нужно еще доказать, что найдется.
Дык, если это предположение было бы верно, то Ваше решение не было бы решением.
Доказательство абсолютно элементарно.
Поясните лучше, как решение Ocelot было бы решением, если бы верёвка проходила сквозь саму себя.
Мое решение совпадает с решением Biga. Решение Ocelot я не смотрел, если оно требует нетривиальности узла, то в моей формализации его описать невозможно.
> как решение Ocelot было бы решением, если бы верёвка проходила сквозь саму себя
Естественно, никак. Тогда у вас возникнет встречный вопрос: «Если веревка не проходит сквозь себя, как может быть верным решение Kallikanzarid?»
Отвечу: для того, чтобы это решение работало, не обязательно, чтобы веревка проходила через саму себя. Достаточно, чтобы можно было определить взаимное расположение в каждой из точек самопересечения так, чтобы на веревке не возникало узлов.
В моем решении уже указано, какие участки веревки проходят снизу, а какие сверху, неоднозначности там нет.
Only those users with full accounts are able to leave comments. Log in, please.