Математики нашли способ одновременного соприкосновения 7 цилиндров



    Более 50 лет назад автор популярных статей о математике в журнале Scientific American Мартин Гарднер предложил читателям задачу: «Можете ли вы разместить семь сигарет таким образом, чтобы каждая из них соприкасалась со всеми остальными?»

    Гарднер сам нашёл решение, но оно его не удовлетворяло, потому что основания некоторых цилиндров соприкасались с боковыми поверхностями. Он хотел такое решение, в котором основания цилиндров бы не использовались. То есть для случая с бесконечно длинными цилиндрами.

    Спустя полвека — 20 марта 2014 года — на конференции Gathering 4 Gardner в честь Гарднера, математик из Венгерской академии наук Шандор Бозоки (Sándor Bozóki) огласил-таки подходящее решение. Прошлым летом оно было опубликовано в научной статье на ArXiv.

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

    Количество возможных конфигураций оценивалось примерно в 121 млрд, и проверить все из них не представлялось возможным. Но учёным повезло: уже после проверки 80 млн конфигураций были найдены два решения.



    Оба результата проверили с помощью программы AlphaCertified, чтобы доказать, что найденные решения — не результат каких-то компьютерных ошибок округления. Учёные даже изготовили реальную физическую модель из дерева. Впрочем, в производстве деревянных деталей погрешности ещё больше, чем могут быть погрешности округления в компьютерных вычислениях, так что эта модель сделана исключительно в демонстрационных целях.
    Поделиться публикацией

    Комментарии 105

      +70
      Надо запомнить схему и спорить на пьянках. Только вот я не курю, и не пью…
        +8
        Может рисуете? Карандаши подойдут.
          +11
          Где вы на пьянке найдете карандаши? Соломинки для коктейлей.

          Интересно, какое максимальное количество цилиндров можно разместить в 3-х мерном пространстве, чтобы каждая из них соприкасалась со всеми остальными? Или 7 максимум?
            +2
            если пьянка по работе — то у всех есть карандаши, а у кого-нибудь — и маркер для белой доски
              +6
              Думается, критически важно чтобы диаметр цилиндров был одинаков.
                –4
                думаю неважно
                  +1
                  на первой фотке если уменьшать диаметр синего цилиндра, тогда он коснется или зеленого или темно серого верхнего
                    +1
                    ох… извиняюсь. я жестко ступил. Firtz прав
                  +1
                  С цилиндрами произвольных размеров — это просто ещё одна задача )
                  • НЛО прилетело и опубликовало эту надпись здесь
                +25
                Вы сформулировали новую задачу и спровоцировали трату еще 3-х месяцев компьютерного времени
                  +1
                  Если экстраполировать количество найденных решений на всё множество — получается около 3 тыс. вариантов из 7 цилиндров (хотя там наверняка алгоритм был не полной переборкой, а с эвристикой, и из возможных 121 миллиардов перебранные 80 миллионов — «лучшие из»).
                  Получается — к этим 3 тыс. (в лучшем случае) решений с 7 цилиндрами нужно попробовать добавить 8-й.
                0
                Боюсь, что можете проспорить :) Для первого случая, судя по картинке длинны сигареты не хватит, для второго нужно пробовать. В статье стоило бы указать и минимально возможную длину цилиндра, а точнее соотношение длины к диаметру.
                  +12
                  Поищите на антресолях. Наверняка там завалялся десяток-другой бесконечно длинных цилиндров :)
                    +4
                    Ха. Я случайно в кладовке шарик из подшипника танка нашел. Советские антресольно-кладовые залежи — стратегический запас!
                      +6
                      А я в подвале нашёл танк без одного шарика в подшипнике. Вот так и живём.
                    0
                    По ходу можно спорить на что угодно — если не получится продемонстрировать — сослаться на погрешности физической модели. Кстати неплохой тост, если вдруг передумаете. Хабра-смайл.
                    +3
                    Интересен вопрос про «округление». Сам сталкивался с ним когда баловался со «Шри-янтрой».
                    Т.е. Практически задачу решить можно и достаточно легко. НО доказать аналитически что решение строгое, а не приближенное — фактически невозможно.
                    Не могли бы рассказать подробнее что за программа AlphaCertified — для проверки полученных решений?
                      +22
                      bit.ly/1kA3L8a
                      А у этого автора вы ответа не дождетесь…
                        0
                        > Т.е. Практически задачу решить можно и достаточно легко.

                        Ну не так уж легко.
                        Аналитически вообше не решена.
                          +1
                          А вот и ответ на ваш вопрос: habrahabr.ru/post/220909/#comment_7534981
                          +6
                          Вроде и статья не «желтая», вроде и о математике, а ведь так и знал, что автор — alizar :)
                          И как он умудряется?.. Талант…
                            +69
                            Критерии очень просты:
                            1. Это перевод, но как перевод он не помечен.
                            2. Сам автор никакого отношения к статье не имеет и никакого анализа, предпосылок или выводов не предоставляет.
                            3. Сложные части либо перевраны (не в этот раз) либо просто пропущены (как раз в этот раз — см. статью первоисточника).
                              +8
                              Идет пересказ своими словами там где он не нужен, это очень чувствуется, особенно если автор не разбирается в тематике статьи. А пересказ делается с единственной целью — забрать «авторство» себе.

                              Собственно так заполняется контентом огромное количество сайтов и очень обидно, что такой подход работает на хабре (судя по рейтингу alizara и ему подобных рерайтеров).
                                0
                                А с другой стороны, где бы я еще узнал о способе соединения 7 бескончных цилиндров… Вроде информация и бесполезная, но довольно познавательная… Кстати наверное и рейтинг у него такой высокий, что выбирает не совсем уж полную фигню, а что-то интересное, не находите?
                                  +1
                                  Фишка в том, что когда это отмечено переводом, то можно предположить, что могут быть неточности перевода и есть первоисточник, где эти неточности обычно отсутствуют.
                              +95
                              Семь перпендикулярных красных прямых линий…
                                +24
                                Зашел сюда прочитать этот комментарий.
                                  +14
                                  Всегда плюсую тех, кто пишет «зашел сюда прочитать этот комментарий».
                                    +22
                                    — Зашёл сюда прочитать комментарий о том, кто всегда плюсует тех, кто пишет «зашёл сюда прочитать этот комментарий».

                                    — Всегда плюсую тех, кто пишет «зашёл сюда прочитать комментарий о том, кто всегда плюсует тех, кто пишет "зашёл сюда прочитать этот комментарий"».

                                    — …
                                      +28
                                      — Зашел минусануть Мицгола? :)

                                      PS Минус не мой.
                                  +35
                                  Не перевирайте классику! «Семь перпендикулярных красных прямых линий, часть из которых нарисованы зелёным цветом, а часть — прозрачны»
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                    +1
                                    Вы тоже не перевирайте. В оригинальном техзадании нету «красных прямых линий», есть просто «красные линии». То, что линии прямые — это уже «специалист» сам додумал. Без этой отсебятины вполне можно нарисовать 7 взаимно-перпендикулярных линий.
                                      0
                                      Правильно, нужно думать шире. И исполнителю нужно было узнать что подразумевается под перпендикулярностью и когда она может быть не взаимной, чтобы не ошибиться.
                                        0
                                        Во-первых, «взаимно» там тоже не было. Во-вторых, а ну изобразите 7 не прямых перпендикулярных линий.
                                          +2
                                          Нууу… как-то так, например?
                                          Семь красно-зелёных перпендикулярных линий


                                          disclaimer: рисовано на коленке за 2 минуты.
                                            +1
                                            Слушайте ещё переход прозрачности от 100% до 0% сделать по ходу линий — и Вы фактически выполнили исходное задание!
                                              +2
                                              Я не знал, что будет собрание, и не подготовился :)

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

                                              И котиков я рисовать не умею :(
                                              0
                                              Семь красно-зелёных перпендикулярных линий

                                              Они все желтые.
                                                +3
                                                Нет, они красно-зелёные. Возьмите увеличительное стекло и убедитесь.
                                                  +1
                                                  Жёлтый цвет — это цвет излучения с длиной волны ~580 нм. Данные линии излучают смесь красного и зелёного цветов, что есть совершенно другой цвет. Наше несовершенное зрение ощущает его как «жёлтый», но это иллюзия. Если дать линии какому-нибудь роботу со спектроанализатором, он обнаружит красный и зелёный.
                                              +1
                                              Откуда информация?

                                              Оригинальное ТЗ:
                                              — Так вот, — говорит Морковьева. — Нам нужно нарисовать семь красных линий. Все они должны быть строго перпендикулярны, и кроме того, некоторые нужно нарисовать зеленым цветом, а еще некоторые — прозрачным. Как вы считаете, это реально?
                                                +1
                                                Не вижу тут слово «прямых». Ну разве что оно написано прозрачным цветом :)
                                                  –1
                                                  Слово «прямых» подразумевается когда говорится, что линии перпендикулярны.
                                                    +2
                                                    Меридиан и экватор — перпендикулярны?
                                                      +1
                                                      Я не большой специалист в тонкостях. Но, как мне видится, перпендикулярность в евклидовом пространстве определяется через: две прямые; прямую и плоскость; плоскость и плоскость. Поэтому в евклидовом пространстве меридиан и экватор не перпендикулярны по определению, вернее его отсутствию. Насколько я понимаю, в сферической геометрии меридиан и экватор могут быть перпендикулярны.
                                                        +1
                                                        Слишком много подразумеваний и неявных предположений. Это не то, что нужно от хорошего техзадания. Настоящий специалист должен преодолевать инерцию мышления и воздерживаться от спекулятивных предположений. Иначе он никогда не выйдет за рамки привычного и не сделает ничего нового.
                                                          0
                                                          Все-таки «техническое задание» должно быть пригодным для однозначного восприятия и последующей проверки. Поэтому в нем нужно явно писать критичные вещи (что линии должны быть перпендикулярны) и стоит пропускать некритичные (прямая ли должна быть линия).

                                                          Если ТЗ неоднозначно понимается разными людьми или содержит субъективные неизмеряемые признаки («должно быть красиво»), резко возрастает вероятность получения на выходе чего-то, не устраивающего заказчика.
                                                      +1
                                                      Слово «прямая» подразумевает «кратчайшее растояние между двумя точками». Растояние зависит от метрики пространства. На моём рисунке — прямые в пространстве с манхэттенской метрикой
                                                        +1
                                                        Короче, заказчику и исполнителю нужно было синхронизировать понятийный аппарат.: )
                                                          +3
                                                          На том совещании не было заказчика, там был представитель заказчика, который явно вообще никаких понятий не имел. По-хорошему, исполнителю нужно было просить встречи непосредственно с заказчиком, чтобы не играть в испорченый телефон. Или подходить к заданию исключительно формально.
                                              +2
                                              Семь перпендикулярных красных прямых линий…

                                              На фото еще 2 цилиндра есть, только они прозрачные…
                                                +1
                                                На сложной поверхности, напоминающей котёнка, семь прямых могут быть взаимно перпендикулярны. Для того, чтобы нарисовать зелёным красные линии, надо взять красный фон и рисовать на нём зелёным. Вопрос прозрачности совершенно понятен — «прозрачный зелёный» вполне себе цвет материала.

                                                Если чуть-чуть головой думать, вполне себе упражнение на топологию и сообразительность, а не закатанные к потолку глаза.
                                                  +1
                                                  Для того, чтобы нарисовать зелёным красные линии, надо взять красный фон и рисовать на нём зелёным.


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

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

                                                    А дзен инженерии в том, что абсурдные на обывательский взгляд требования можно выполнить в осмысленном виде. Даже если авторы ролика ничего такого не подразумевали.
                                                      0
                                                      Если на красном фоне зеленым зарисовать почти все, то можно оставить как раз красные линии )
                                                  +25
                                                  Я в детстве с интересом читал книги, издававшиеся в СССР, состоявшие из сборников задач Гарднера, опубликованных им в журналах. Однако я совершенно не мог найти решения к ним, т.к. задачи эти были, на мой тогдашний взгляд, нереально сложными. Да и теперь, честно говоря, они меня в ступор повергают.
                                                  Некоторые я даже до сих пор помню.
                                                  К примеру, вот (если правильно запомнил): на земле лежит верёвка, и она сама себя несколько раз пересекает. Количество пересечений мы знаем, но нам не видно, как именно на пересечениях лежит веревка, т.е. какая часть сверху, какая — снизу. Какова вероятность того, что если её поднять с земли, она завяжется в узел?
                                                  В общем, математики — это какие-то очень особенные люди…
                                                    +2
                                                    Ждем головоломку с сенсорными «цилиндрами» с автоматической проверкой количества соприкосновений =)
                                                      +7
                                                      математик из Венгерской академии наук Сандор Бозоки (Sándor Bozóki)
                                                      Шандор, у венгров весьма своеобразный взгляд на латиницу.
                                                        +1
                                                        У людей есть супер-компьютеры… и вот как они их используют :)
                                                          +33
                                                          Наверно имеет смысл приложить изначальное решение, в котором бесконечно длинные цилиндры не допускаются…
                                                          image
                                                            +8
                                                            Зато оно красивее рассчётного.
                                                            0
                                                            Спойлерить-то зачем? :(
                                                              +26
                                                              А я на выходных склеил из карандашей вот такую параболическую н. е. х.: imgur.com/a/V2yEI
                                                                +11
                                                                Это ж насколько должно быть нечего делать.
                                                                  +8
                                                                  Напротив. Когда от работы мозги начинают закипать, очень хорошо бывает переключаться на подобное занятие. Несколько подходов в течение двух дней, в общей сложности часа два-три.

                                                                  Потом с constpetrov считали угол получившегося зазора. Расчет показал, что в круг вписывается 5.1 тетраэдров, и это число совпало с практикой. :)
                                                                    +10
                                                                    Может, расслабиться вам помогает не само занятие, а запах клея? :)
                                                                      +9
                                                                      Нет, клей очень бодрит, особенно когда он, горячий, капает с сопла клей-пистолета прямо на ноготь.
                                                                        0
                                                                        Переходит на низкотемпературные виды )
                                                                        Либо на некапающий пистолет
                                                                  +3
                                                                  Круто! Только есть подозрение что н.е.х. не параболическая, а седловидная. По крайней мере очень похоже на иллюстрацию к прохождении прямых по поверхности седла. Если это так, то это лучшая визуализация седла. Хотя другой название — гиперболический параболоид, так что параболическая в том числе.
                                                                    +12
                                                                    > есть подозрение что н.е.х. не параболическая, а седловидная

                                                                    Ну, я назвал ее параболической только потому, что вижу параболу в проекции на плоскость (на фотке, то бишь).

                                                                    > гиперболический параболоид

                                                                    Круто! Спасибо за наводку. Буду понтоваться: «не абажур, а, на минуточку, гиперболический параболоид!» :D А еще я теперь знаю, что такое линейчатая поверхность. НУЖНО БОЛЬШЕ КАРАНДАШЕЙ
                                                                      +3
                                                                      вижу параболу в проекции на плоскость

                                                                      Там на фотках в проекции как раз гиперболы. Хоть они чем-то и похожи, но есть коренное отличие: ветки гипербол асимтотически приближаются к прямым (продолжениям лучей на фотке), а у парабол нет таких асимптот.
                                                                        0
                                                                        Как вы определили, что это гиперболы? На глаз?
                                                                          +3
                                                                          Нет, по построению.

                                                                          Форма проекций на фото — звездчатая, т.е. есть из центра можно провести бесконечные лучи.Представьте, что карандаши — бесконечной длины, и вы поймёте, что огибающие между лучами никогда не пересекут друг друга, а будут бесконечно асимптотически приближаться к линиям лучей. Если есть асимптота — значит это не парабола.
                                                                            +1
                                                                            Простите, не владею математической терминологией и не уверен, что понял вас. Попробую возразить как могу.

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

                                                                            Внешняя ссылка,
                                                                            Раскрывашка
                                                                            image

                                                                            На иллюстрации угол между лучами 90 градусов, а у карандашной модели — 70.53 градуса, но сути это не меняет.

                                                                            Видно, что «карандаши» продолжают пересекаться на каждом шаге. Как сюда пристроить асимптоту, я не знаю. По-моему, типичная парабола.
                                                                              +1
                                                                              Погуглил использованные вами термины и нашел такое определение в статье "Огибающая":
                                                                              Парабола является огибающей семейства срединных перпендикуляров для отрезков, соединяющих фиксированную точку (фокус параболы) и фиксированную прямую (директрису параболы).

                                                                              Карандаши — это, как я понял, срединные перпендикуляры.
                                                                    –1
                                                                    Не совсем понял условия задачи.
                                                                    Нужно разместить цилиндры, опираясь на плоскость в устойчивое положение равновесия?
                                                                    Нужно разместить цилиндры, опираясь на плоскость в НЕустойчивое положения равновесия?
                                                                    Нужно разместить цилиндры в пространстве, используя какие-то опоры?

                                                                    И дальше «разместить семь сигарет таким образом, чтобы каждая из них соприкасалась со всеми остальными»
                                                                      0
                                                                      Равновесие необязательно, можно на клей. Задача — расположить семь цилиндров так, чтобы каждый соприкасался с каждым, вот и все.
                                                                      –2
                                                                      А для большего количества цилиндров нет решения? Почему задача только для 7 штук, могли при моделировании просчитать бы все варианты, а то может там и для десятка есть одно решение, которое будет куда менее тривиальным. А до такого решения можно было и без компьютера додуматься, явно просто не всех эта задача интересовала на мой взгляд.
                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                          0
                                                                          Задача легко представима физическими объектами — как во времена великих открытий, взять напилить цилиндров попробовать найти решение, потом по формулам проверить, что решение подлинное. Я что-то не думаю, что эта задача была сильно важной и популярной, поэтому и не было предложено такого решения, а так много людей увлеченных решением математических проблем нашли бы одно решение и без компьютера.

                                                                          Ну и во все времена если не доказать, что для большего числа нет решений, то найденное частное решение не имеет особой ценности, так как общая задача то не решена, да и решение найдено перебором.
                                                                          –1
                                                                          Если всё так как в статье, то вообще не понятно в чём достижение. Забрутфорсили решение системы нелинейных уравнений, ни анализа решения, ни единственности, ничего нет. Таких «научных статей» можно нагенерить миллионы.
                                                                            +1
                                                                            Откуда там единственность? 22 степени свободы на 21 ограничение — понятно, что у любого решения будет хоть какой диапазон свободы. Но странно, что этого не было сделано раньше. Хотя, конечно, задачка не из простых.
                                                                              0
                                                                              Представьте что цилиндры короткие и толстые. Тогда предложенным способом их сложить не удастся. Значит при каких-то h/R решения есть, а при каких-то нет.
                                                                                +1
                                                                                В статье явно написано, что задача решалась для бесконечно длинных цилиндров.
                                                                          +10
                                                                          Теперь можно строить сразу 7 веток метро!
                                                                            +2
                                                                            Причём не менее одной из них — под углом около 45°, а значит, удастся пассажиров примучить.
                                                                              0
                                                                              Американские горки
                                                                              0
                                                                              эм… я так понимаю, решение основывается на допущении «допустим, длина сигарет может быть разной»
                                                                                0
                                                                                решение основывается на допущении «допустим, длина сигарет может быть разной»

                                                                                Нет

                                                                                на допущении «допустим, длина сигарет может быть разной»

                                                                                А это уже не допущение, а истина.
                                                                                +2
                                                                                Наверное, нарвусь на минусы, но все же. Объясните мне практическое приложение конкретно этой задачи?
                                                                                Мне кажется, она очень узко сформулирована и полученный результат (на который потратили три месяца времени суперкомпьютера) не особо применим в реальном мире и, т.к. это просто численное решение, а не аналитический вывод некоего закона, даже не открывает никаких теоретических горизонтов.
                                                                                Тогда зачем? Кроме как «because we can»?
                                                                                  +2
                                                                                  Какой-нибудь класс архихитрых подшипников или узлов нагрузки в архитектурных конструкциях. Математики люди странные.
                                                                                    0
                                                                                    Но они не вывели, как найти все решения. И если я решу создать такой подшипник с 7 цилиндрами, я не смогу найти оптимальной компановки, так как у меня нет общей формулы для поиска решений.
                                                                                    +1
                                                                                    Задачи решения систем алгебраических неравенств (и анализа топологии полученных решений, например, наличия пути из одной точки в другую) весьма сложны, и при этом полезны (особенно при современном уровне прогресса роботехники). В сочетании с немалой долей комбинаторной геометрии (описание и анализ «конфигураций») — получается ещё круче. Другое дело, что в представленном решении могло не оказаться заметных продвижений в этих задачах, а всего лишь использование каких-нибудь известных методов (или продвижения были, но остались на компьютере авторов). Но назвать такое решение «численным» мне не кажется правильным — любое наличие работы с конфигурациями само по себе переводит задачу на следующий уровень.
                                                                                    +1
                                                                                    Интересно, а сама задача имеет практическое применение в какой-то отрасли на данный момент, или пока всё считали «забавы ради»?
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                        0
                                                                                        Я еще в 7 классе нашел способ соприкосновения восьми.
                                                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                                                            0
                                                                                            я заминусован… (
                                                                                            если кто поможет — обязательно расскажу
                                                                                              0
                                                                                              да, и в моем решении все-таки основания некоторых цилиндров соприкасаются с боковыми поверхностями, зато не 7, а 8 цилиндров.
                                                                                                0
                                                                                                  0
                                                                                                  в теме рассматривался такой способ, при котором цилиндры соприкасались бы не основаниями

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

                                                                                            Самое читаемое