Как стать автором
Обновить

Через 243 года «неразрешимая» головоломка Эйлера получила наконец решение с помощью странной физики кота Шредингера

Время на прочтение6 мин
Количество просмотров58K
Всего голосов 37: ↑16 и ↓21+3
Комментарии75

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

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

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

И что эта картинка означает? Ведь точно такую же картинку можно нарисовать для квадрата 4x4, где решение существует (поросто мысленно отрежте крайние клетки от этой доски)?


Максимум что вы тут доказали, что именно вот таким вот образом начинать расстановку фигур — не стоит.

Я понял, что по одной диагонали — звания (фигура), по другой - полки (цвет), но как это мешает решить задачу (в той постановке, в которой она в статье), я не понял.

Спасибо за замечание, просто я час потратил на таскание фигурок и почему-то мне показалось что я смог показать типа вырожденный случай почему это невозможно. Вы правы, моё предположение необоснованно, и вообще надо было сразу признаться что я ненастоящий математик :(

Все-таки интересно, любопытства ради, где взять столько уверенности в себе, чтобы после того, как прочитав что сам Эйлер не смог найти доказательства, и что его нашли только 100 лет спустя, сразу же попытаться найти его самому, да еще так, чтобы показать одной картинкой без лишних обьяснений? :)

Я не пытаюсь победить Эйлера — я пытаюсь понять, как ПРАВИЛЬНО звучит условие задачи. Потому что "чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лишь один раз" — тривиально: присваиваем однозначное соответствие "полк 1 = звание 1" ... "полк 6 = звание 6", и вуаля.

Читаем в начале статьи:

в каждом из шести разных армейских полков есть по шесть офицеров различных званий

Поскольку сам Эйлер считал задачку нетривиальной и неразрешимой, Ваше толкование условий, очевидно, ошибочно. Надо понимать так, что в каждом полку нет двух офицеров в одном звании. Там даже для наглядности картинку с шахматными фигурками привели: нет двух совпадающих фигур одного цвета, они там вообще все уникальны - каждая отличается от остальных как минимум цветом или "званием".

Надо понимать так, что в каждом полку нет двух офицеров в одном звании.

Звучит логично. Только теперь вопрос: почему это не написал автор статьи, а мы с Вами вынуждены догадываться?

в каждом из шести разных армейских полков есть по шесть офицеров различных званий

офицеров различных званий

"различных" != "не имеющих одинаковых".

"полковник, два сержанта и сто подпоручиков" — это вполне "в полку офицеры различных званий".

Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"

Ну так это как в том анекдоте — программистам дали задание "постройте мне самолёт". Через месяц приходят принимать — стоит на взлётной полосе самолёт. Бетонный. "А как же он летает? — ЛЕТАЕТ??? В техзадании про полёты ничего не было!!!"

В математике "различных" означает именно "не одинаковых"

В моём примере далеко не все офицеры "одинаковые". В постановке задач должно было быть "в полку не может быть двух одинаковых офицеров". Тогда у нас выходит аж пять критерия уникальности:

  • уникально звание в строке

  • уникально звание в столбце

  • уникален полк в строке

  • уникален полк в столбце

  • уникально звание в полку

То есть задача на самом деле трёхмерная (третья ось — "звание").

Здесь не пикабу какой, здесь программисты собрались. А у нас профдеформация — компьютеру задачи нужно записывать именно так, как в в конце статьи по Вашей ссылке.

То есть задача на самом деле трёхмерная (третья ось — "звание").

По постановке 4-мерная: 2 пространственных оси, плюс звание и полк. Но есть принципы запрета (не может быть двух офицеров в одном сотсотянии, не может быть двух однополчан в одном звании и др.), что снижает размерность конфигурационного пространства. Да и вообще оно дискретно и конечно. Задача в том, чтобы доказать, что при условиях Эйлера (в рядах и стролбцах не должно быть совпадений по полкам и званиям), число допустимых состояний меньше 36.

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

где взять столько уверенности в себе, чтобы после того, как прочитав что сам Эйлер не смог найти доказательства
Нужно быть на неправильном пике кривой Даннинга-Крюгера. Согласитесь, задача выглядит ну очень простой, с учётом того что (кажется) решение обязательно должно быть симметричным. Не так страшно опростоволоситься, как ничего из этого не вынести.

Я ведь правильно понимаю, что оригинальную головоломку все же не решили? А решили ее модификацию, добавив условия, которые позволили ее решить.

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

я думаю мало кто вживую видел запутанных офицеров полков.

Я видел парочку.

насколько помню, они всегда запутанные

Только если от венерических заболеваний не лечатся.

Погодите. Что значит "нам придётся", если речь о чётком факте, который может быть выражен как "да" или "нет" и никак иначе? Если мы не знаем, да или нет, мы так и говорим: не знаем, неизвестно, не выявлено. А то ведь, знаете ли, жизнь на Альфа-Центавре тоже в суперпозиции: то ли есть, то ли нет.

В оригинальной головоломке есть условие: офицеры разных званий и разных полков. Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания. Если мы заменим офицеров на спортсменов, полки на стили боевых искусств, а звания на пояса, то, в принципе, описанное вами станет возможно - но это будет уже другая задача и у неё будет дополнительное условие.

Проще говоря: исходная задача до сих пор не решена, вместо этого решили что-то другое и отчитались об успехе. Молодцы, конечно, но не в том направлении.

>Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания.

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

Просто добавили в Устав возможность службы по совместительству для офицеров.

У военных если звание (сержант, лейтенант, etc), и должность - типа командир взвода, начальник штаба и т.д. Должности они вполне себе совмещают (например, кто то в отпуске), но вот чтоб один погон капитанский, а второй лейтенантский... Хотя бывает:

Кадры расположены именно в том порядке, в каком появляются в фильме - и его не понизили в звании, а наоборот доверили АПЛ. Но киноделам можно, у них постоянно "квантовая неопределенность" с одеждой/оружием/техникой :)

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

Я знаю что на скриншотах не "лейтенантский" и "капитанский" погоны (у них один просвет на погоне, а у капитана вообще 4 звезды) - эти звания в коментарии я привел для примера. Свою ошибку - не совсем четкую формулировку - я осознал когда редактировать комментарий было уже поздно.

Отчего ж не "капитанский"? Слева - капитан 1 ранга, справа - 2-го.

Оригинальная головоломка для 36 офицеров давно решена и доказано, что решение отсутствует.

НЛО прилетело и опубликовало эту надпись здесь

Я думаю, что Леонард Эйлер русский математик.

Жил в России с 1727 по 1741 год и с 1766 по 1783 год до своей смерти, был членом Академии наук России большую часть своей жизни.

Все правильно, 1927 г. Эйлера стал адъюнктом высшей математики, в Швейцарии он только учился (на факультета искусств).

Российский

Ну, так вы и Хуго Шмайссера сделаете российским. Напомню, его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова. А сам Калашников даже в руках этот автомат не умеет правильно держать.
Эйлер никогда не был ни русским, ни российским математиком. Он был приглашённым швейцарским математиком в Росссийской Империи.

его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова.

Настало время прохладных историй.

О, боже.

Если кому интересно, то клаш — это американская винтовка Гранда (да-да, та самая, которая большой палец закусывала), развернутая вверх ногами (чтоб не сверху магазин вставлять) и с приделанным стволом от СКС.
Немцы там и рядом не валялись, у них своя «родовая линия» от шушпангевера — HK (я держал в руках оба (пострелять так и не дали) — реально как внук и дедушка).

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

Ну Вы сравнили!
Шмайссер был насильно привезён в СССР уже состоявшимся профессионалом (было ему за 60), инженером с массой уникальных разработок (кстати, военнопленным он не был - ему просто сделали предложение, от которого он не смог отказаться, получая при этом весьма неплохую зарплату). А Эйлер швейцарским оставался лишь по подданству. Приехал в Россию добровольно, в 20 лет покинув родную Швейцарию (в которую, кстати, больше не вернулся). Учёным с мировым именем он стал работая именно в Российской Академии. В России прожил большую часть жизни, здесь же написал большую часть своих трудов, здесь же и похоронен (как и его потомки). Впрочем, прусский период его творчества также имеет большое значение.
А следуя Вашей логике и Екатерина II не была Российской Императрицей, так, немецкой девочкой по вызову.

Сложный момент. С одной стороны, это не решение задачи, это взгляд на нее с другой стороны, с созданием новых условий. Но с другой стороны, математика его времени не могла решить эту задачу, в то время как нынешняя предлагает решение, но можно ли называть и то и то математикой, ведь за 243 года, квантовая математика стала своего рода аддоном для обычной, как евклидова геометрия, или макрофизика, которая тоже живет по своим правилам. Мой вывод, нет задача не решена, потому что здесь идет подмена понятий с добавлением "вариантов"

Это не решение. Они построили другую задачу, где искомые объекты уже не квадраты из разноцветных фигур, а из чего-то сильно более сложного (каждый объект обладает какой-то непрервыной комбинацией свойств). В такой формулировки эта задача решается.


Как вот нельзя в целых числах решить x^2-2=0, но при переходе к вещественным числам решение появляется. Но это уже другая задача.

Может, глупый вопрос, но все же: эту задачу нельзя решить простым перебором?

Перебором можно подтвердить, что для 6х6 таких расстановок нет. Это и будет решение - вопрос-то ставился "можно ли". Простенькое упражнение на кодинг.

Число возможных сочетаний: факториал от 36. На самом деле в несколько раз меньше, так как например поворот квадрата на 90 градусов фактически не приводит к новому варианту решения, но да неважно - главное порядоч значений.

36! ~= 37 * 10^40

Допустим на проверку одного решения требуется наносекунда. Тогда

(37 * 10^40 * 10^-9) / 60 / 60 / 24 / 365 лет ~= 10^25 лет

Предположим что за счёт использования суперкомпьютера с множеством ядер выиграли еще несколько порядков, останется (оптимистично) 10^20 лет

Возраст Вселенной - 13,75 ± 0,13 * 10^9 лет, что в 100 миллиардов раз меньше...

факториал от 36

Не надо так драматизировать. Здесь два факториала от 6 - расставать звания по ячейкам матрицы (6!), расставить полки по ячейкам (6!), каждую расстановку проверить, что присутствуют все возможные пары (звание, полк). Итого порядка 36 * 6! * 6! проверок

Нет, туплю. 36 * 6! * 6! * 6! будет. За каждым полком закрепляем горизонтальную строку матрицы. Перебираем независимо: все перестановки полков по столбцам (6!), все перестановки званий по строкам (6!), все перестановки званий по столбцам (6!), и на каждой из таких комбинаций проверка 36 пар (звание, полк)

НЛО прилетело и опубликовало эту надпись здесь
Все равно не так — нужно добиться чтобы в строках и столбцах небыло повторов, а не просто переставлять строки/столбцы. Получается для 1й строки 6!=720 комбинаций, для 2й нужно исключить дублирование значений в столбцах из 1й и т.д., последняя строка будет без вариантов состоять из того, что еще не встречалось в столбцах. Итого 720*309*112*32*6*1 = 4 784 209 920 комбинаций. Приемлимо для перебора. Цвет можно захардкодить как в картинке из статьи: c=(x+y)%size, а тип перебирать, решение будет найдено если в матрице нет одинаковых комбинаций цвет+тип.

А точно такое решение будет существовать? Почему вы считаете, что можно хардкодить цвет по диоганалям?

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

при этом точной формулы количества «уникальных» квадратов до сих пор нет — находят «ручками». Для 6х6 — it's over 9000 (совсем немного, вроде бы).

 Более века спустя французский математик Гастон Тарри доказал, что действительно невозможно расположить 36 офицеров Эйлера в квадрате 6 на 6 без повторений. 

Давайте повсюду совать так популярную нынче квантовую запутанность и говорить, что мяукало Шрёдингера решает все проблемы

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

Да, нынче бедного котика к месту и не к месту поминают, хотя кот Шрёдингера - иллюстрация суперпозиции квантовых состояний, а не квантовых корреляций (aka квантовой запутанности). Более того, Шрёдингер придумал своего кота, как пример системы, для которой описание в терминах суперпозиции состояний не является адекватным (как и для офицеров из задачки Эйлера). Если же мы допускаем суперпозицию, то описываем явно не кота, а нечто иное.

Допустим у меня есть керамическая плитка 10 разных цветов 10х10 см, и я хочу выложить ей стену 100х200 см так, чтобы линии не повторялись.

Есть ли какие-то методики, чтобы рассчитать такую раскладку ?

Тут все относительно, если проецировать эту задачу на наш мир то да, через квантовую физику она решается. Но если это задача чисто логическая, и где нет квантового мира, то в рамках того мира она не решаема.

В 1779 году швейцарский математик Леонард Эйлер

А ничего что Леонард Эйлер полжизни прожил и проработал в России, создал Императорскую Академию Наук, и похоронен в Санкт Петербурге? "Швейцарский математик"...

Можно Эйлера вывезти из Швейцарии, но Швейцарию из Эйлера - никогда!

Помню в годы учебы на физфаке МГУ была такая шутка - если бы Эйлер был русским, то МГУ был бы имени Эйлера.

Ну если Новоселов и Гейм - русские физики, то Эйлер, безусловно, швейцарский математик.

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

Великий Эйлер ошибся по поводу двух взаимно ортогональных квадратов 10*10: они таки да существуют. Их построили в 1959- м Паркер, Боуз и Шрикхенд. А вот трех до сих пор никто не нашел!

Three MOLS of order 10 not exist!

Т.е. фигуры в квадратах заданы «динамически», и их значение зависит от того, на какую из них наблюдатель смотрит в данный момент?

Не считается, это чит. Подобно тому как придумали мнимую единицу, чтобы квадратные корни отрицательных чисел вычислять.

Вот как раз мнимая единица не чит, а элемент поля комплексных чисел.

Моя вечная проблема - что шучу с "мордой кирпичом". Конечно же, и то и другое - не чит, а расширение взгляда на задачу. Вот это вот детское "не считается" должно было настроить на шутливый лад

Чем моё решение не соответствует заявленныим требованиям задачи? В решении 6 разных офицеров шести разных полков, что явно выражено в цифровом формате.

У вас офицеры — не разные. Каждого типа — по шесть штук, и соответственно, 30 типов просто отсутствуют (например, где все шестёрки, которые не (6,6)? И все другие пары, где сумма элементов не равна 6?).
А по условиям Эйлера нужно расставить 36 уникальных пар.

Для начала сделайте это хотя бы для 2х2 — всего 4 уникальные пары!

P.S.
(Автору статьи и просто понимающим людям) хотя бы для этого случая (2х2) объясните конкретный механизм как эта квантовая запутанность задачу решает.

В каждом полку - шесть одинаковых званий

Так эта задача не решаема только для квадрата 6х6 ?? Или вообще для любого квадрата с четной стороной? А для любого квадрата с нечетной строной решаема? Я сейчас бегло проверил - для квадратов 2х2 и 4х4 не получилось построить.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории