Картина и гвозди

Под падали подразумевается, что она должна начать движение вниз, или что это движение потом не должно прекращаться?

Эммм, тупо на одном гвозде? при его вытаскивании картина упадет.

Нехорошо такие задачки в разгар понедельника постить.

Я понимаю, условие «повесить на N гвоздей» означает «каждый из N гвоздей должен касаться веревки»?

Казалось бы, к чему сейчас эта картинка стоит перед мысленным взором

Мне кажется тут что-то с натяжением верёвки — один гвоздь убираешь, верёвка даёт слабину и сползает.
Как один из неправдоподобных вариантов: сложить верёвку вместе и продеть её через N рядом стоящих гвоздей так, чтобы верёвка касалась каждого из них. Картина держится на трении, гвозди вбиты так, что убирая любой из них трение уменьшается, становится не достаточным, верёвка проскальзывает и картина падает.

Давайте представим, что это не картина, а микроскоп, тогда можнно сменить топпик на «Микроскоп и гвозди» 8))

Хотите, чтобы за вас решили пятибальную задачу с braingames? ;)

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

Ну хоть шнурки из ботинок доставай!

Думаю, тут идея в том, что гвозди могут быть вбиты в стену на произвольную глубину. И/или могут быть разной длины.

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

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

На любое N решение не масштабируется :-)

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

Для двух: расположить гвозди один под другим, веревку, сложенную вдвое, обвести сначала мимо нижнего гвоздя, потом обвернуть над верхним и, наконец, зацепить петлей за нижний гвоздь.

По условиям ясно, что веревка ОБЯЗАТЕЛЬНО касается всех гвоздей. Потому что при выдергивании любого она должна упасть. Взял резинку, набил гвоздей, сижу протягиваю резинку меж них…

Мне кажется тут надо быть последовательным:
— как решить для N=1 всем понятно
— для N=2 уже сложнее, вот картинка одного из возможных вариантов:


кто для N=3 нарисует? там, глядишь, и до логического разрешения не далеко, хоть и не уверен

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

Боюсь, коллеги, что для N>2 решений нет. Для двух предложили три человека решения, но эти решения не позволяют увеличить число гвоздей.

Мне напомнило другую задачу с верёвкой, которая вроде бы решение имеет, но сложное. Задача по-моему из Мартина Гарднера.
На полу лежит закольцованная верёвка (у неё скреплены 2 конца). Она лежит неровно, несколько раз пересекается сама с собой. Нам не очень хорошо видны места пересечения, поэтому непонятно, какая часть сверху в каждом из пересечений, а какая снизу.
Зная количество пересечений, необходимо подсчитать вероятность того, что при растягивании верёвки она завяжется узлом (а не просто растянется в 2 параллельных отрезка).

Мой вариант. Там где толстая линия означает, что две нити идут.

Кажись доперло наушниками на пальцах. Но мозги уже сварены, и буквописью не осилю.
Решение как-то связано с наматыванием в один оборот?

Решение для трёх гвоздей. Основано на решении для двух гвоздей, но вместо гвоздей в первом случае пропускаются петли, которые идут дальше.
Аналогично расширяется «пирамидкой» до N гвоздей.

Рекурсия!

habrastorage.org/storage1/bb2c3fdd/920e2ae7/2f070aa8/043f8c02.jpg

Вот такой вариант.

Не могу это описать словами, а тем более нарисовать. Сфоткал. Для 2х гвоздей получается красиво и наглядно, а вот для 3 уже мешанина( но принцип тот же, что и при переходе от одного гвоздя к двум)
1) Один гвоздь.


2) Два


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


4) Три гвоздя


Для 4х пальцевгвоздей не пробовал — длины шнурка не хватает.

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

Как-то так:

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

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

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

Это скорее всего повторение предыдущих рекурсивных решений… но как-то нагляднее и аккуратнее.

Выложил своё решение. Читаем UPD4.

Вариант задачи без трения можно решить строго, для этого достаточно привлечь лишь элементарную теорию гомотопий. Я опишу суть решения, детали — по требованию.

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

Таким образом задача сводится к следующей: найти нетривиальную петлю на плоскости с выколотыми 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

Если что-то непонятно или вы хотите, чтобы я лучше обосновал тот или иной переход, я буду рад пояснить столь подробно, сколь потребуется.