Нет, вы только посмотрите какая прелестная задачка!

Картину с прикрепленной к ней обоими концами длинной веревкой минимозгу просто необходимо повесить на стену с помощью N гвоздей таким образом, чтобы при вытаскивании любого гвоздя картина падала. Как это сделать?

GD Star Rating
loading...
Задача про картину, 10.0 out of 10 based on 1 rating
Tagged with →  

30 Responses to Задача про картину

  1. Peels:

    Традиционная просьба к решившим постараться удержаться от соблазна немедленно похвастаться достижением, выложив спойлер как можно скорее и испортив остальным удовольствие персонального открытия. Предлагаю методы подъема самооценки ограничить комментарием «Ура, я решил», а собственно детали решения обсуждать с проверяющими на braingames.

  2. ReMonkey:

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

  3. ReMonkey:

    для нечётного количества можно попробовать расмотреть схему «звезда», но для чётного она не годится.

  4. Peels:

    Типа того, да. Сама идея что это можно сделать по–моему гениальна.
    Отсюда один шаг до того, чтобы писать веревкой по гвоздям булевы формулы 🙂
    Веревка с гвоздями turing complete!

  5. ReMonkey:

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

  6. Peels:

    Пробуй для N=2 сначала.

  7. ReMonkey:

    проблема в том, что для двух точек у меня уже не получается заплести.

  8. ThDad:

    Я думаю, что надо сделать так: прибить картину к стене гвоздём, а потом прибивать к гвоздю N гвоздей. Если мы потянем за любой из гвоздей, вся конструкция из стены выдернется и картина упадёт на пол!

  9. ReMonkey:

    вбить в стену дырку, в неё вбить гвоздь, в гвоздь вбить эн дырок, в них вбить эн гвоздей.

  10. ReMonkey:

    удавка наоборот какая–то.

  11. ThDad:

    нет, что ты такое говоришь, как можно вбить дырку? Дырку можно просверлить, а вбить в неё — дюбель! А в дюбель завернуть шуруп и на него повесить картину.

  12. Peels:

    Не, ты че, лучше вбить в стену маленьких наноботов, сообщающихся по беспроводному протоколу, а поверх них закрутить шурупы, на которые повесить веревку. Наноботов запрограммировать следующим образом: как только один из шурупов выкручивают, соответствующий нанобот выпускает сигнал АЙАЙАЙ, в ответ на который все остальные наноботы начинают выкручивать свои шурупы, и картина падает!

  13. ErBoo:

    подсказку дайте

  14. Peels:

    верхний гвоздь
    петля огибает ловко
    нижним прибита

  15. Lakm:

    Задача с Соросовской олимпиады по математике для 8 или 9 класса где–то за 1997–1998 год.

  16. Rafol:

    Все дело в том, что фундаментальная группа плоскости без n точек является свободной ранга n, а в такой группе есть слово, которое превращается в 1 если на 1 заменить хотя бы одну образующую. Если кому–то будет интересно, готов рассказать подробнее.

  17. Peels:

    Клевая интерпретация. Расскажи, раз уж груздем назвался.

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

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

  18. Orenegue:

    твоя идея помогла, хоть я и не понял, как.
    конфигурации на рисунке соответствует слово –a,b,a,–b
    для трёх гвоздей уже не получается.

    размер 400x300, 2.53 kb

  19. Peels:

    Ыыыы, сиииськи…

    Подсказка: дальше рекурсивно.

  20. Orenegue:

    подробнее, желательно в терминах «abc..»
    ясно, что верёвка должна иметь полное число зацепления M, равное нулю, при том, что каждое огибание гвоздя верёвкой даёт вклад в M, равный +1 или –1, в зависимости от направления обхода. выдёргивание гвоздя не должно менять M, поэтому для каждого i–го гвоздя должно быть M_i=0. как найти такую конфигурацию, я не знаю.

  21. UgSuper:

    вбить 2 гвоздя и поставить на них картину

  22. Peels:

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

    Что ты про «число зацепления» написал, что такое M и М_i и причем там +1, –1 и 0 я честно говоря не понял.

  23. Rafol:

    Немного теории.
    Петлей называется любое непрерывное отображение f отрезка [0,1] в некоторое пространство *, такое, что f(0) = f(1) = *0. В нашем случае * это плоскость с выколотыми точками (a, b, c на рисунке).

    размер 363*310, 35.22 kb

    Проще говоря, петля это веревочка оба конца которой привязаны к одной фиксированной точке *0 (это то место где веревочка крепится к картине). Важно видеть где у веревочки начало, а где конец — на картинке это изображено стрелками.

    Разных петель много. Но многие из них похожи: 2 петли называются гомотопными если их можно непрерывно (не разрывая веревочку) превратить одну в другую. На картинке все петли 1–5 гомотопны. Видно, что их можно делать все меньше и меньше, в пределе они сведутся к нулевой петле, которая совпадает с точкой *0.

    Петля 6 не гомотопна ни одной из петель 1–5, ее нельзя свести к нулевой петле — мешается выколотая точка a (гвоздь в стене).

    С точки зрения топологии нет нужды различать петли гомотопные друг другу — их считают одинаковыми. Для нашей задачи это тоже справедливо: все веревочки 1–5 ведут себя одинаково по отношению к картине и гвоздям, поэтому для нас они тоже одинаковы.

  24. Rafol:

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

    размер 363x340, 35.33 kb

  25. Rafol:

    Так вот оказывается, что петли вместе с таким умножением образуют группу. Причем единичным элементом является нулевая петля (та, что не захватывает выколотых точек и может быть стянута в *0). Обратная петля получается если на исходной петле сменить направление обхода. Эта группа называется фундаментальной группой.

    В нашем частном случае (плоскость с выколотыми точками), фундаментальная группа оказывается свободной с базисом образованном петлями обхватывающими выколотые точки (петли A, B, C на рисунке).

    размер 282*239, 33.02 kb

    Всякая петля может быть разложена в произведение базовых петель. Например, Z = C–1B–1AC (если вы поняли почему это так, значит вы разобрались с фундаметальными группами).

  26. Rafol:

    Применим описанную выше машинерию к нашей задаче. Рамочка (точка *0) упадет если и только если петля на которой она висит нулевая (по определению нулевой петли!). Значит, скажем, если она висит на петле В, или ABC, или A–1BA, или A100B–100C23, то она не упадет, а если на петле A–1A, то упадет.

    Когда мы выдираем гвоздь «a» все буквы «A» в описании веревочки нужно заменить на 1, потому что после удаления гвоздя «a» петля «A» становится нулевой (ее можно стянуть к *0).

    Задача состоит в том, чтобы сконструировать в свободной группе слово не равное 1, которое, вместе с тем, становится равным 1 если любую из образующих заменить на 1.

    Такое слово есть! Это, так называемый, коммутатор [A, B] = ABA–1B–1. Действительно, [A, B] не равно 1, но [1, B] = 1B1B–1 = BB–1 = 1, и аналогично [A, 1] = 1.

    Но нужно еще задействовать гвоздь «с». Это просто, подойдет вложенный коммутатор [[A, B], C] = ABA–1B–1CBAB–1A–1C–1. Теперь задача — нарисуйте петлю отвечающую этому вложенному коммутатору.

  27. Peels:

    Спасибо за развернутое объяснение с картинками (на чем рисовал, кстати? я не узнаю программу).
    Самое неочевидное место тут (для того кто не в теме, конечно) на мой взгляд в том обалденном факте, что фундаментальная группа свободна. Хоть оно конечно и не противоречит интуиции, я с трудом представляю как это показывается. Например, как формально показать хотя бы такой факт что, скажем, петли ABA–1, и B — разные.

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

  28. ThDad:

    А кто такой минимозг?

  29. Peels:

    Редкий персонаж из терминологического мира braingames.ru.

  30. MikeMike:

    Peels: Теперь задача — нарисуйте петлю отвечающую этому вложенному коммутатору.

    Зарисовал. И объяснение простое и понятное, спасибо. Только петля получается уж очень замысловатой. Самое интересное, что так повесить картину можно при любом числе гвоздей. Интересно только, нет ли более простого решения для некоторых типов чисел.

Добавить комментарий