Комментарии 75
Я, наверно, тупенький. Но выглядит так, что они просто добавили вариантов.
И что эта картинка означает? Ведь точно такую же картинку можно нарисовать для квадрата 4x4, где решение существует (поросто мысленно отрежте крайние клетки от этой доски)?
Максимум что вы тут доказали, что именно вот таким вот образом начинать расстановку фигур — не стоит.
Я понял, что по одной диагонали — звания (фигура), по другой - полки (цвет), но как это мешает решить задачу (в той постановке, в которой она в статье), я не понял.
Спасибо за замечание, просто я час потратил на таскание фигурок и почему-то мне показалось что я смог показать типа вырожденный случай почему это невозможно. Вы правы, моё предположение необоснованно, и вообще надо было сразу признаться что я ненастоящий математик :(
Все-таки интересно, любопытства ради, где взять столько уверенности в себе, чтобы после того, как прочитав что сам Эйлер не смог найти доказательства, и что его нашли только 100 лет спустя, сразу же попытаться найти его самому, да еще так, чтобы показать одной картинкой без лишних обьяснений? :)
Я не пытаюсь победить Эйлера — я пытаюсь понять, как ПРАВИЛЬНО звучит условие задачи. Потому что "чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лишь один раз" — тривиально: присваиваем однозначное соответствие "полк 1 = звание 1" ... "полк 6 = звание 6", и вуаля.
Читаем в начале статьи:
в каждом из шести разных армейских полков есть по шесть офицеров различных званий
Поскольку сам Эйлер считал задачку нетривиальной и неразрешимой, Ваше толкование условий, очевидно, ошибочно. Надо понимать так, что в каждом полку нет двух офицеров в одном звании. Там даже для наглядности картинку с шахматными фигурками привели: нет двух совпадающих фигур одного цвета, они там вообще все уникальны - каждая отличается от остальных как минимум цветом или "званием".
Надо понимать так, что в каждом полку нет двух офицеров в одном звании.
Звучит логично. Только теперь вопрос: почему это не написал автор статьи, а мы с Вами вынуждены догадываться?
в каждом из шести разных армейских полков есть по шесть офицеров различных званий
офицеров различных званий
"различных" != "не имеющих одинаковых".
"полковник, два сержанта и сто подпоручиков" — это вполне "в полку офицеры различных званий".
Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Ну так это как в том анекдоте — программистам дали задание "постройте мне самолёт". Через месяц приходят принимать — стоит на взлётной полосе самолёт. Бетонный. "А как же он летает? — ЛЕТАЕТ??? В техзадании про полёты ничего не было!!!"
В математике "различных" означает именно "не одинаковых"
В моём примере далеко не все офицеры "одинаковые". В постановке задач должно было быть "в полку не может быть двух одинаковых офицеров". Тогда у нас выходит аж пять критерия уникальности:
уникально звание в строке
уникально звание в столбце
уникален полк в строке
уникален полк в столбце
уникально звание в полку
То есть задача на самом деле трёхмерная (третья ось — "звание").
То есть задача на самом деле трёхмерная (третья ось — "звание").
По постановке 4-мерная: 2 пространственных оси, плюс звание и полк. Но есть принципы запрета (не может быть двух офицеров в одном сотсотянии, не может быть двух однополчан в одном звании и др.), что снижает размерность конфигурационного пространства. Да и вообще оно дискретно и конечно. Задача в том, чтобы доказать, что при условиях Эйлера (в рядах и стролбцах не должно быть совпадений по полкам и званиям), число допустимых состояний меньше 36.
где взять столько уверенности в себе, чтобы после того, как прочитав что сам Эйлер не смог найти доказательстваНужно быть на неправильном пике кривой Даннинга-Крюгера. Согласитесь, задача выглядит ну очень простой, с учётом того что (кажется) решение обязательно должно быть симметричным. Не так страшно опростоволоситься, как ничего из этого не вынести.
Я ведь правильно понимаю, что оригинальную головоломку все же не решили? А решили ее модификацию, добавив условия, которые позволили ее решить.
Решили, добавив запутанность. Но, заметьте, в условии оригинальной головоломки нет отрицания использования запутанности. Это примерно как с котом Шредингера. Разумеется, когда откроем ящик, он будет или мертв, или жив, но не открывая ящик, нам придется определить его состояние как суперпозицию живого-мертвого кота.
я думаю мало кто вживую видел запутанных офицеров полков.
Погодите. Что значит "нам придётся", если речь о чётком факте, который может быть выражен как "да" или "нет" и никак иначе? Если мы не знаем, да или нет, мы так и говорим: не знаем, неизвестно, не выявлено. А то ведь, знаете ли, жизнь на Альфа-Центавре тоже в суперпозиции: то ли есть, то ли нет.
В оригинальной головоломке есть условие: офицеры разных званий и разных полков. Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания. Если мы заменим офицеров на спортсменов, полки на стили боевых искусств, а звания на пояса, то, в принципе, описанное вами станет возможно - но это будет уже другая задача и у неё будет дополнительное условие.
Проще говоря: исходная задача до сих пор не решена, вместо этого решили что-то другое и отчитались об успехе. Молодцы, конечно, но не в том направлении.
>Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания.
Ну почему же? Полковник Советской Армии Исаев одновременно был штандартенфюрером СС (младший полковник). В условиях задачи не оговорено, что воинские формирования обязательно должны быть в рамках одной страны.
Просто добавили в Устав возможность службы по совместительству для офицеров.
У военных если звание (сержант, лейтенант, etc), и должность - типа командир взвода, начальник штаба и т.д. Должности они вполне себе совмещают (например, кто то в отпуске), но вот чтоб один погон капитанский, а второй лейтенантский... Хотя бывает:
Кадры расположены именно в том порядке, в каком появляются в фильме - и его не понизили в звании, а наоборот доверили АПЛ. Но киноделам можно, у них постоянно "квантовая неопределенность" с одеждой/оружием/техникой :)
вот чисто зарегался, чтоб ответить. где ты тут увидел погон лейтенанта? если это погоны капитанов 1 и второго рангов соответственно? это ж вмф. плюс, даже если не приглядываться, видно, что это погоны старшего офицера.
Оригинальная головоломка для 36 офицеров давно решена и доказано, что решение отсутствует.
Я думаю, что Леонард Эйлер русский математик.
Жил в России с 1727 по 1741 год и с 1766 по 1783 год до своей смерти, был членом Академии наук России большую часть своей жизни.
Российский
Ну, так вы и Хуго Шмайссера сделаете российским. Напомню, его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова. А сам Калашников даже в руках этот автомат не умеет правильно держать.
Эйлер никогда не был ни русским, ни российским математиком. Он был приглашённым швейцарским математиком в Росссийской Империи.
его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова.
Настало время прохладных историй.
О, боже.
Немцы там и рядом не валялись, у них своя «родовая линия» от шушпангевера — 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 пар (звание, полк)
А точно такое решение будет существовать? Почему вы считаете, что можно хардкодить цвет по диоганалям?
при этом точной формулы количества «уникальных» квадратов до сих пор нет — находят «ручками». Для 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 разных офицеров шести разных полков, что явно выражено в цифровом формате.
А по условиям Эйлера нужно расставить 36 уникальных пар.
Для начала сделайте это хотя бы для 2х2 — всего 4 уникальные пары!
P.S.
(Автору статьи и просто понимающим людям) хотя бы для этого случая (2х2) объясните конкретный механизм как эта квантовая запутанность задачу решает.
Народ, видите? Я тут не единственный программист!
В каждом полку - шесть одинаковых званий
Так эта задача не решаема только для квадрата 6х6 ?? Или вообще для любого квадрата с четной стороной? А для любого квадрата с нечетной строной решаема? Я сейчас бегло проверил - для квадратов 2х2 и 4х4 не получилось построить.
Через 243 года «неразрешимая» головоломка Эйлера получила наконец решение с помощью странной физики кота Шредингера