Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 151
Под падали подразумевается, что она должна начать движение вниз, или что это движение потом не должно прекращаться?
Это я к чему. Если гвоздики забить в шахматном порядке выше-ниже (хотя можно и лево-право) и пропустить веревку змейкой через все их — то вытаскивание любого приведет к проскальзывании картины вниз на расстояние между этими шахматными рядами. Вроде как при большом расстоянии можно считать, что картина падает.
Хотя это, наверняка, не тот вариант :)
Хотя это, наверняка, не тот вариант :)
Эммм, тупо на одном гвозде? при его вытаскивании картина упадет.
Так в задаче же не один гвоздь, а практически любое их количество.
Сказанно, N. Ограничения на него не даны, потому и можно предположить что N=1. А вообще, в задаче по факту не стоит то, что требуется найти. Взаимное расположение гвоздей и веревки для любого N? Из формулировки «Требуется повесить её на N вбитых в стену гвоздей так, чтобы при вытаскивании из стены одного любого гвоздя картина и веревка падали. » как раз и вытекает, что требование задачи — сделать падающую картину. И можно взять для этого любое количество гвоздей. Вот я и взял то количество, что посчитал нужным — 1.
Нехорошо такие задачки в разгар понедельника постить.
Я понимаю, условие «повесить на N гвоздей» означает «каждый из N гвоздей должен касаться веревки»?
Казалось бы, к чему сейчас эта картинка стоит перед мысленным взором
Мне кажется тут что-то с натяжением верёвки — один гвоздь убираешь, верёвка даёт слабину и сползает.
Как один из неправдоподобных вариантов: сложить верёвку вместе и продеть её через N рядом стоящих гвоздей так, чтобы верёвка касалась каждого из них. Картина держится на трении, гвозди вбиты так, что убирая любой из них трение уменьшается, становится не достаточным, верёвка проскальзывает и картина падает.
Как один из неправдоподобных вариантов: сложить верёвку вместе и продеть её через N рядом стоящих гвоздей так, чтобы верёвка касалась каждого из них. Картина держится на трении, гвозди вбиты так, что убирая любой из них трение уменьшается, становится не достаточным, верёвка проскальзывает и картина падает.
Давайте представим, что это не картина, а микроскоп, тогда можнно сменить топпик на «Микроскоп и гвозди» 8))
Хотите, чтобы за вас решили пятибальную задачу с braingames? ;)
1) Эту задачу на braingames (пятибалльную, да) я уже решил.
2) Послеочередного падения braingames эта задача оттуда пропала. Когда добавят обратно — неясно.
2) После
Никуда не пропало. www.braingames.ru/?path=comments&puzzle=468
А зачем на хабр выложили? Просто чтобы другие мозги понапрягали? :)
Да, кстати, из-за падения пропали большие решения некоторых задач (надо же было их именно в это время посылать =_=). Теперь снова все это печатать уже не хочется…
Да, кстати, из-за падения пропали большие решения некоторых задач (надо же было их именно в это время посылать =_=). Теперь снова все это печатать уже не хочется…
))) Опередили
Один гвоздь.
Надо вбить гвоздь в стену через веревку. Таким образом, гвоздь будет чем-то вроде «затычки», удерживая веревку.
Вынимаете этот гвоздь — картина падает.
Надо вбить гвоздь в стену через веревку. Таким образом, гвоздь будет чем-то вроде «затычки», удерживая веревку.
Вынимаете этот гвоздь — картина падает.
Тут всё не так сложно. На самом деле, особо рисовать не надо, тут просто индукцией доказывается что если мы смогли повесить её на N гвоздей, то нехитрым способом сможем забить еще 1 гвоздь и повесить её в соответствии с условиями, зная как вешать на N гвоздей.
Вспомнилось моё одно творение на эту тему. Одной непрерывной ниткой по 350 гвоздям. :)
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6266.jpg
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6239.jpg
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6241.jpg
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6266.jpg
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6239.jpg
i46.photobucket.com/albums/f132/Sinoptic3/IMG_6241.jpg
Ну хоть шнурки из ботинок доставай!
Думаю, тут идея в том, что гвозди могут быть вбиты в стену на произвольную глубину. И/или могут быть разной длины.
«Имеется картина, к которой двумя концами привязана длинная веревка. Требуется повесить её на N вбитых в стену гвоздей...»
Кого её? Картину или веревку?
Картину ставим на два гвоздя, выдергиваем любой — картина падает вместе с веревкой.
На любое N решение не масштабируется :-)
Кого её? Картину или веревку?
Картину ставим на два гвоздя, выдергиваем любой — картина падает вместе с веревкой.
На любое N решение не масштабируется :-)
Первое что пришло в голову: вбить все гвозди в один вертикальный ряд, достаточно близко и глубоко. Веревку продеть перекрученной следующим образом: на самый высокий гвоздь (первый) вешать как обычно (без перекручивания), перевернуть картину мордой к стенке, положить перекрестие на второй гвоздь, перевернуть картину обратно, положить перекрестие веревки на третий гвоздь и т.д. При выдергивании любого гвоздя веревка начинает раскручиваться, и слетает с гвоздей.
Интересно, насколько далеко я от решения. :)
Интересно, насколько далеко я от решения. :)
Вариант: Выдернуть гвоздь из картины, где веревка крепится.
Для двух: расположить гвозди один под другим, веревку, сложенную вдвое, обвести сначала мимо нижнего гвоздя, потом обвернуть над верхним и, наконец, зацепить петлей за нижний гвоздь.
Тогда это и есть решение. Нужно продолжать эту мысль на все остальные гвозди.
Если верхний вытянуть — на нижнем повиснет.
опередил на 10 минут
По условиям ясно, что веревка ОБЯЗАТЕЛЬНО касается всех гвоздей. Потому что при выдергивании любого она должна упасть. Взял резинку, набил гвоздей, сижу протягиваю резинку меж них…
Мне кажется тут надо быть последовательным:
— как решить для N=1 всем понятно
— для N=2 уже сложнее, вот картинка одного из возможных вариантов:
кто для N=3 нарисует? там, глядишь, и до логического разрешения не далеко, хоть и не уверен
— как решить для N=1 всем понятно
— для N=2 уже сложнее, вот картинка одного из возможных вариантов:
кто для N=3 нарисует? там, глядишь, и до логического разрешения не далеко, хоть и не уверен
Каждый следующий гвоздь вбиваем так, чтобы его шляпка была над шляпкой предыдущего. На последний вешаем картину. На рисунке — «вид сверху».
Я чего то не понял или картина весит только на последнем гвозде? А если я любой другой выдерну?
Остроумное решение!
Это читерство! И потом, что будете делать, если вам выдадут гвозди без шляпок?
вот уж действительно thinking out of the box
я бы Вас на работу сразу взял
хотя вроде как по условию задачи гвозди уже вбиты в стену
интересно кстати, могут ли они быть вбиты так что решения в принципе не существует…
я бы Вас на работу сразу взял
хотя вроде как по условию задачи гвозди уже вбиты в стену
интересно кстати, могут ли они быть вбиты так что решения в принципе не существует…
Любое расположение точек-гвоздей на плоскости будет топологически эквивалентно любому другому их расположению. Так что можно добавить уловие, что гвозди уже вбиты произвольным образом. Только тогда нужно сделать оговорку, что мы можем потребовать веревку любой конечной длины.
ну а если вбить два гвоздя «абсолютно вплотную друг к другу»?
веревка по условию «имеет пренебрежимо малую толщину»
но непонятно чья мантра в кавычках сильнее в даннном случае, т.е. можно ли между такими двумя гвоздями веревку провести
опять же, в условии не плоскость а стена
есть ли у стены края? примыкает ли стена к другой стене так что гвоздь вбивается «абсолютно вплотную к соседней стене»?
веревка по условию «имеет пренебрежимо малую толщину»
но непонятно чья мантра в кавычках сильнее в даннном случае, т.е. можно ли между такими двумя гвоздями веревку провести
опять же, в условии не плоскость а стена
есть ли у стены края? примыкает ли стена к другой стене так что гвоздь вбивается «абсолютно вплотную к соседней стене»?
а если гвозди полые и разной толщины и один вбит в другой?
какая тут нафик топологическая эквивалентность?
какая тут нафик топологическая эквивалентность?
Боюсь, коллеги, что для N>2 решений нет. Для двух предложили три человека решения, но эти решения не позволяют увеличить число гвоздей.
Мне напомнило другую задачу с верёвкой, которая вроде бы решение имеет, но сложное. Задача по-моему из Мартина Гарднера.
На полу лежит закольцованная верёвка (у неё скреплены 2 конца). Она лежит неровно, несколько раз пересекается сама с собой. Нам не очень хорошо видны места пересечения, поэтому непонятно, какая часть сверху в каждом из пересечений, а какая снизу.
Зная количество пересечений, необходимо подсчитать вероятность того, что при растягивании верёвки она завяжется узлом (а не просто растянется в 2 параллельных отрезка).
На полу лежит закольцованная верёвка (у неё скреплены 2 конца). Она лежит неровно, несколько раз пересекается сама с собой. Нам не очень хорошо видны места пересечения, поэтому непонятно, какая часть сверху в каждом из пересечений, а какая снизу.
Зная количество пересечений, необходимо подсчитать вероятность того, что при растягивании верёвки она завяжется узлом (а не просто растянется в 2 параллельных отрезка).
Мой вариант. Там где толстая линия означает, что две нити идут.
Вытаскиваем любой, кроме того, что в петле и ничего не падает.
habrastorage.org/storage1/49f5b203/58ce2be8/8a71f3d2/e256831f.jpg
Не годится, к сожалению. Картина падает, только если выдернуть самый правый гвоздь.
Не годится, к сожалению. Картина падает, только если выдернуть самый правый гвоздь.
Кажись доперло наушниками на пальцах. Но мозги уже сварены, и буквописью не осилю.
Решение как-то связано с наматыванием в один оборот?
Решение как-то связано с наматыванием в один оборот?
Решение для трёх гвоздей. Основано на решении для двух гвоздей, но вместо гвоздей в первом случае пропускаются петли, которые идут дальше.
Аналогично расширяется «пирамидкой» до N гвоздей.
Ох ты ж..! Неужели правда работает?
Я попытался это распутать. При выдергивании правого гвоздя получается система петель для N=2, но картина не падает:
habrastorage.org/storage1/053e80ab/7f624d56/ba31adaa/919d4a54.gif
habrastorage.org/storage1/053e80ab/7f624d56/ba31adaa/919d4a54.gif
Вот более четко идея рекурсии. Продолжается на сколько угодно гвоздей по бинарному дереву.
habrastorage.org/storage1/f080f7e1/7b8f4c5c/bba0755a/6d201e3b.jpg
habrastorage.org/storage1/f080f7e1/7b8f4c5c/bba0755a/6d201e3b.jpg
Что-то не сходится… Выдергиваем, допустим, средний гвоздь. Получается вот такая фигня:
habrastorage.org/storage1/b19b03f3/a65fd8c1/00c3a166/4fc6afb5.gif
habrastorage.org/storage1/b19b03f3/a65fd8c1/00c3a166/4fc6afb5.gif
Немного не те петли зарекурсировал, но решение явно видно.
Пока не видно :) Тут всегда кажется, что «еще чуть-чуть и получится». Попробуйте нарисовать правильное решение.
Прошу простить меня. Поторопился. Я просто на пальцах со шнурком проверил, а нарисовал не так как сделал.
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
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
Вот такой вариант.
Что-то туплю. Скорее так:
Если это решение правильное (а оно вроде бы да), то оно масштабируется до N.
Увы, где-то просчет:
habrastorage.org/storage1/3a462e3f/b9632d29/bd62c80b/f6eebed9.gif
habrastorage.org/storage1/3a462e3f/b9632d29/bd62c80b/f6eebed9.gif
Проверьте, пожалуйста, аккуратно ещё раз. У меня всё нормально получается.
Извините, всё верно. Я увидел два перехлёста там, где у вас один.
Решение для N=3 найдено! А каким образом оно масштабируется?
Решение для N=3 найдено! А каким образом оно масштабируется?
Точно так же: удваиваете верёвку, захлёстываете петлю за четвёртый гвоздь, и не забываете свободный конец завести за него. (Картинка кликабельна.)
Ух! Пожалуй, придется поверить вам на слово, т.к. проверять это я буду очень долго :)
Вот «размотка» для четырёх.
www.habrastorage.com/images/wire4u1.png
www.habrastorage.com/images/wire4u2.png
www.habrastorage.com/images/wire4u3.png
(Дальше видно, что красная половина идёт направо, и вся верёвка оказывается снизу.)
www.habrastorage.com/images/wire4u1.png
www.habrastorage.com/images/wire4u2.png
www.habrastorage.com/images/wire4u3.png
(Дальше видно, что красная половина идёт направо, и вся верёвка оказывается снизу.)
Прочитал 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) Если в списке остались только отрицательные числа или список пуст, то — «картина упала», иначе нет.
Что-то я закономерностей не вижу… ну кроме как рекуррентно динамикой строить :)
Если обозначить гвозди цифрами 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.: С утра еще повнимательнее гляну.
или этой:
P.S.: С утра еще повнимательнее гляну.
Мне кажется, что решение для трёх гвоздей можно «зациклить» способом, аналогичным моей первой попытке: www.habrastorage.com/?v=wire.png
Будет время на работе — попробую придумать что-нибудь. =)
Будет время на работе — попробую придумать что-нибудь. =)
Вот мой вариант «раскручивания», его удобнее смотреть, чем гиф, имхо:
www.habrastorage.com/images/wire3u1.png
www.habrastorage.com/images/wire3u2.png
www.habrastorage.com/images/wire3u3.png
www.habrastorage.com/images/wire3u1.png
www.habrastorage.com/images/wire3u2.png
www.habrastorage.com/images/wire3u3.png
Не могу это описать словами, а тем более нарисовать. Сфоткал. Для 2х гвоздей получается красиво и наглядно, а вот для 3 уже мешанина( но принцип тот же, что и при переходе от одного гвоздя к двум)
1) Один гвоздь.
2) Два
3) Два с половиной
4) Три гвоздя
Для 4хпальцевгвоздей не пробовал — длины шнурка не хватает.
1) Один гвоздь.
2) Два
3) Два с половиной
4) Три гвоздя
Для 4х
А разве при снятии шнура со среднего пальца конструкция не превращается обратно в то, что на первой фотографии?
Проверил — отлично снимается при убирании любого ил пальцев. Процесс перехода от 3 пункта к 4 такой же, как от перовго ко второму. Заводим петлю из п.3 за безымянный палец и накидываем на средний. При этом левая часть петли из 3-ей картинки будет ближе к нам.
Были бы гвозди сантиметров по 10 и длинная лента — можно было бы наглядно разложить. Тоже получилось бы красиво. Лента нигде не перегибается
Были бы гвозди сантиметров по 10 и длинная лента — можно было бы наглядно разложить. Тоже получилось бы красиво. Лента нигде не перегибается
Да, действительно, работает. Дальше, я так понимаю, N можно увеличивать рекурсивно? То есть за 4 палец заводится петля из 8 шнурков, за 5 — из 16 и т.д.
Можно и так, но думается что это не лучший способ. Из N=3 можно ещё использовать 2 шнурка с указательного пальца и обмотать их аналогичным образом вокруг большого( обмотать то получается, но вытащить из этой связки какой-то один палец я не могу, так что проверить не могу, но должно работать).
И в любом случае остаются указательный с средний пальцы, на которых получаются концы петли, остальные верёвки просто проходят рядом с этими пальцами. Наверное можно каждый раз аналогичным образом эту петлю расширять на ещё один гвоздь.
ЗЫ Чё-то я уже запутался в пальцах-гвоздях
И в любом случае остаются указательный с средний пальцы, на которых получаются концы петли, остальные верёвки просто проходят рядом с этими пальцами. Наверное можно каждый раз аналогичным образом эту петлю расширять на ещё один гвоздь.
ЗЫ Чё-то я уже запутался в пальцах-гвоздях
А если сложить веревку вдвое, поставить картину на гвоздь, пропустить сложенную вдвое верёвку (теперь как единую) по забитым в шахматном порядке гвоздям, а конец веревки подложить под картину на гвоздь, на котором она стоит. По условию задачи имеем право найти хрупкое равновесие?
Как-то так:
Как-то так:
0. Вариант с двумя гвоздями и вообще без верёвки.
1. Решение для одного гвоздя.
2. Решение для двух гвоздей.
Из решения с 1 гвоздём можно перейти к решению с двумя гвоздями. Видно, как область выделенная пунктиром сводится к решению с 1 гвоздём.
Это скорее всего повторение предыдущих рекурсивных решений… но как-то нагляднее и аккуратнее.
Выложил своё решение. Читаем UPD4.
Супер несущая петля на каждом гвозде держится не за гвоздь, а за петлю. Опять убеждаюсь, что верное решение очень изящно выглядит )
Мне при решении таких задач всегда кажется, что решение должен находить 5-10 летний человечек, по-моему в данном случае, это возможно
Мне при решении таких задач всегда кажется, что решение должен находить 5-10 летний человечек, по-моему в данном случае, это возможно
Это почти такой же узел, которым укладывали раньше стропы в парашюте! Очевидное рядом (:
Очень круто. Приходило на ум что-то такое, но до конца додумать не смог
Вариант задачи без трения можно решить строго, для этого достаточно привлечь лишь элементарную теорию гомотопий. Я опишу суть решения, детали — по требованию.
Для начала нужно эту задачу формализовать. Мы будем считать, что стена — это плоскость, а веревка — это петля (замкнутый непрерывный путь) на ней. Картина выполняет просто роль груза и для решения задачи не нужна. Поскольку веревка никогда не сможет пройти сквозь гвоздь, то точки плоскости, в которые вбиты гвозди, можно считать выколотыми. Если в данной конфигурации картина упадет, то рано или поздно вся веревка окажется ниже всех гвоздей. Но поскольку движение непрерывно, это означает, что веревка упадет тогда и только тогда, когда соответствующая петля гомотопически эквивалентна тривиальной (т.е. ее можно непрерывным движением стянуть в точку).
Таким образом задача сводится к следующей: найти нетривиальную петлю на плоскости с выколотыми N точками, который станет тривиальной, если вернуть любую одну точку на место. Фундаментальная группа этого пространства — свободная группа с N порождающими (доказательство — по требованию, там будет довольно много писанины и поясняющих картинок, без латеха набрать нереально), можно зафиксировать их представителей, например, так:
Для определенности также зафиксируем направление их обхода — против часовой стрелки. Таким образом любому гомотопическому классу петель (т.е. любому элементу фундаментальной группы) мы сможем сопоставить реальную петлю, «намотанную» на эти представители в соответствии с ее выражением через порождающие.
Выниманию 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
Если что-то непонятно или вы хотите, чтобы я лучше обосновал тот или иной переход, я буду рад пояснить столь подробно, сколь потребуется.
Для начала нужно эту задачу формализовать. Мы будем считать, что стена — это плоскость, а веревка — это петля (замкнутый непрерывный путь) на ней. Картина выполняет просто роль груза и для решения задачи не нужна. Поскольку веревка никогда не сможет пройти сквозь гвоздь, то точки плоскости, в которые вбиты гвозди, можно считать выколотыми. Если в данной конфигурации картина упадет, то рано или поздно вся веревка окажется ниже всех гвоздей. Но поскольку движение непрерывно, это означает, что веревка упадет тогда и только тогда, когда соответствующая петля гомотопически эквивалентна тривиальной (т.е. ее можно непрерывным движением стянуть в точку).
Таким образом задача сводится к следующей: найти нетривиальную петлю на плоскости с выколотыми N точками, который станет тривиальной, если вернуть любую одну точку на место. Фундаментальная группа этого пространства — свободная группа с N порождающими (доказательство — по требованию, там будет довольно много писанины и поясняющих картинок, без латеха набрать нереально), можно зафиксировать их представителей, например, так:
Для определенности также зафиксируем направление их обхода — против часовой стрелки. Таким образом любому гомотопическому классу петель (т.е. любому элементу фундаментальной группы) мы сможем сопоставить реальную петлю, «намотанную» на эти представители в соответствии с ее выражением через порождающие.
Выниманию 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?»
Отвечу: для того, чтобы это решение работало, не обязательно, чтобы веревка проходила через саму себя. Достаточно, чтобы можно было определить взаимное расположение в каждой из точек самопересечения так, чтобы на веревке не возникало узлов.
В моем решении уже указано, какие участки веревки проходят снизу, а какие сверху, неоднозначности там нет.
Естественно, никак. Тогда у вас возникнет встречный вопрос: «Если веревка не проходит сквозь себя, как может быть верным решение Kallikanzarid?»
Отвечу: для того, чтобы это решение работало, не обязательно, чтобы веревка проходила через саму себя. Достаточно, чтобы можно было определить взаимное расположение в каждой из точек самопересечения так, чтобы на веревке не возникало узлов.
В моем решении уже указано, какие участки веревки проходят снизу, а какие сверху, неоднозначности там нет.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Картина и гвозди