Картина

[RIP]

Тоже, наверное, очень известная задача.
В стену вбито $n$ гвоздей. Доказать, что на них можно повесить картину так, что при вытаскивании любого гвоздя картина упадет на пол(картина на верёвке, верёвка достаточно длинная).

[Юстас]

Задача из разряда "сложнее придумать, чем решить"
Рассмотрим трёхмерное пространство с $N$ удаленными параллельными прямыми, и рассмотрим фундаментальную группу получившегося многообразия $G_N$. Это будет группа, порожденная элементами $a_1,\dots, a_N$, $a_i$ суть петля, обходящая прямую $l_i$ по часовой стрелке, соответственно $a_i^{-1}$ - против часовой. Мы хотим доказать, что $\forall N\ \exists Y_N$ такой что если в разложении $Y_n$ по образующим заменить хотя бы один из $a_i$ на единицу(суть выдернуть гвоздь), то петля, соответствующая $Y_N$, стянется в точку(то есть $Y_N$ перейдет в единицу). Докажем по индукции: $N=2, Y_2=a_1 a_2^{-1}a_1^{-1}a_2$удовлетвореят условию. Пусть $Y_N$ существует для всех $N\leq K$, докажем для $N=K+1$. Пусть $Z_{K+1}$ - $(K+1)$й образующий элемент, тогда положим $Y_{K+1}=(Y_K)^{-1}Z_{K+1}^{-1}Y_K Z_{K+1}$. Очевидно, $Y_{K+1}$ удовлетворяет требуему свойству.

[Kallikanzarid]

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

[MrDindows]

А можно вбивать один гвоздь в другой?)

[Kallikanzarid]

MrDindows в сообщении #501136 писал(а):

А можно вбивать один гвоздь в другой?)

Нет (тогда, в зависимости от интерпретации, задача могла бы быть нерешаема )

[Klad33]

Может, тут топология веревки?

[Kallikanzarid]

Klad33 в сообщении #501146 писал(а):

Может, тут топология веревки?

Может быть, а может быть и нет

[Хорхе]

А на картине есть колечко, чтобы веревку продевать?

[Kallikanzarid]

Поправка: требуется, чтобы картина падала при вынимании любого гвоздя.

[RIP]

Было.

Темы объединены. // maxal

[Хорхе]

Ну вот, а я уже чит с колечком придумал :)

[Kallikanzarid]

RIP
Ок

[Sinus]

Пока писал, уже дали ссылку на решение.

(Оффтоп)

Было у нас что-то подобное :)

Пусть у нас есть $n$ гвоздей. Мы можем отождествить каждый возможный способ повесить картину с элементом свободной группы, порожденной $n$ элементами.

Постараюсь пояснить, как именно. Пусть, например, $a_1a_2a_1^{-1}$ - элемент свободной группы. Что бы повесить картину соответствующим образом, перекинем веревку сначала по часовой стрелке над первым гвоздем, потом по часовой стрелке над вторым гвоздем, и затем против часовой стрелке над первым гвоздем.

Можно заметить, что картина будет висеть устойчиво если и только если элемент свободной группы, соответствующий способу, которым повесили веревку, не есть нейтральный элемент. Например, способ, соотвутствующий элементу $a_1a_1^{-1}$ неустойчив, картина упадет.

Также можно заметить, что при выдергивании одного гвоздя происходит следующее: в соответствующем элементе свободной группы просто вычеркивается образующий элемент, соответствующий гвоздю. Например, если способ повесить картину соответствовал элементу $a_1a_2a_3$ и мы выдернули второй гвоздь, то мы получим способ повесить картину, соответветствующий элементу $a_1a_3$.

Теперь задачу можно переформулировать алгебраически: найти такой $x$ элемент свободной группы, образованной $n$ элементами, что при отождествлении одного (любого) образующего элемента группы с единицей группы элемент $x$ станет равен нейтральному.

Это уже несложно, см. оффтоп.

[off]Для $n=2$ решение, например, $x=a_1a_2a_1^{-1}a_2^{-1}:$. Далее по индукции можно построить решение для всех $n$.

Данная задача произвела на меня сильное впечатление. Хотя, возможно, для алгебраистов подобное впорядке вещей

[Kallikanzarid]

Sinus
Угу, мне она тоже понравилась :) Я ее знаю под названием "магия коммутаторов", решением будет коммутатор $[\ldots[a_1, a_2], a_3], \ldots, a_n]$, где $a_1, \ldots, a_n$ - порождающие фундаментальной группы нашего пространства $X$ - плоскости без $n$ точек. В том, что эта группа - свободная, можно убедиться, доказав гомотопическую эквивалентность $X \cong \bigvee^n S^1$.

[ollyvs]

А может кто нибудь нарисовать решение для 3 4 5 хотя бы гвоздей, мне эта задача полгода спать не дает.