Удивительное новое решение знаменитой «головоломки 36 офицеров» Леонарда Эйлера предлагает нам новый способ кодирования квантовой информации.
В 1779 году швейцарский математик Леонард Эйлер придумал задачу: если в каждом из шести разных армейских полков есть по шесть офицеров различных званий, можно ли построить эти 36 офицеров в квадрат 6 на 6 так, чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лишь один раз?
Головоломка легко решается, когда есть пять званий и пять полков, или семь званий и семь полков. Но после безуспешных поисков решения для случая с 36 офицерами Эйлер пришел к выводу, что «такое расположение невозможно, хотя мы и не можем дать строгого доказательства этого». Более века спустя французский математик Гастон Тарри доказал, что действительно невозможно расположить 36 офицеров Эйлера в квадрате 6 на 6 без повторений. В 1960 году математики использовали компьютеры, чтобы доказать, что решения существуют для любого количества полков и рангов больше двух, за исключением случая шести.
Такие загадки очаровывают людей уже более 2000 лет. Культуры по всему миру создавали «магические квадраты» — таблицы чисел, которые складываются в одну и ту же сумму в каждой строке и столбце, и «латинские квадраты», заполненные символами, каждый из которых появляется лишь один раз в строке и столбце. Эти квадраты использовались в искусстве и городском планировании, а также просто для развлечения. В одном популярном латинском квадрате — судоку — есть подквадраты, в которых также отсутствуют повторяющиеся символы. Задача Эйлера о 36 офицерах требует «ортогонального латинского квадрата», в котором два набора свойств, таких как звания и полки, одновременно удовлетворяют правилам латинского квадрата.
Хотя Эйлер считал, что такого квадрата 6 на 6 не существует, недавно все поменялось. В статье, представленной к публикации в журнале Physical Review Letters , группа квантовых физиков из Индии и Польши продемонстрировала, что можно расположить 36 офицеров таким образом, чтобы они соответствовали критериям головоломки Эйлера, но при условии, что офицеры могут иметь квантовую смесь званий и полков. Результатом стала последняя работа в области разработки квантовых версий головоломок с магическим и латинским квадратом, которая представляет собой уже не просто развлечение или игру, но и предоставляет возможность практического применения ее для квантовой связи и квантовых вычислений.
«Я считаю, что их статья весьма красива», — сказала Джемма Де лас Куэвас , квантовый физик из Университета Инсбрука, которая не участвовала в работе. — «Там много квантовой магии. И не только это, на протяжении всей статьи чувствуется их любовь к проблеме».
Новая эра квантовой головоломки началась в 2016 году, когда Джейми Викари из Кембриджского университета и его тогдашний студент Бен Мусто пришли к неожиданной идее, что записи в латинских квадратах можно сделать квантовыми.
В квантовой механике такие объекты, как электроны, могут находиться в «суперпозиции» нескольких возможных состояний: например, одновременно магнитно ориентированы как вверх, так и вниз. Квантовые объекты остаются в этой неопределенности до тех пор, пока они не будут измерены, и именно в этот момент они определяются в одном конкретном состоянии. Записи квантовых латинских квадратов также являются квантовыми состояниями, которые могут находиться в квантовых суперпозициях. Математически квантовое состояние представлено вектором, имеющим длину и направление подобно стрелке. Суперпозиция — это стрелка, образованная объединением нескольких векторов. По аналогии с требованием, чтобы символы вдоль каждой строки и столбца латинского квадрата не повторялись, квантовые состояния вдоль каждой строки или столбца квантового латинского квадрата должны соответствовать векторам, перпендикулярным друг другу.
Квантовые латинские квадраты были быстро приняты сообществом физиков-теоретиков и математиков, заинтересованных в их необычных свойствах. В прошлом году французские физики-математики Ион Нечита и Жорди Пийе создали квантовую версию судоку — SudoQ . Вместо использования целых чисел от 0 до 9 в SudoQ строки, столбцы и подквадраты имеют девять перпендикулярных векторов.
Эти достижения побудили Адама Бурхардта, научного сотрудника Ягеллонского университета в Польше, и его коллег заново пересмотреть старую загадку Эйлера о 36 офицерах. Они задались вопросом, а что, если офицеры Эйлера станут квантовыми?
В классическом варианте задачи каждая запись — это офицер с четко определенным званием и полком. Для простоты можно представить себе 36 офицеров как разноцветные шахматные фигуры, каждая из которых может быть королем, ферзем, ладьей, слоном, конем или пешкой, а полк представлен красным, оранжевым, желтым, зеленым, синим или фиолетовым цветом. Но в квантовой версии офицеры формируются из суперпозиций званий и полков. Например, офицер может быть суперпозицией красного короля и оранжевой королевы.
Критически важно, что квантовые состояния, в которых находятся эти офицеры, имеют особое отношения, называемое запутанностью, которое включает корреляцию между различными сущностями. Например, если красный король запутан с оранжевым ферзем, то даже если и король, и ферзь находятся в суперпозиции нескольких полков, наблюдение того, что рядом есть красный король, сразу означает, что в этом случае наша фигура - оранжевый ферзь (при запутывании состояние одного объекта информирует нас о состоянии другого). Именно из-за специфического характера запутывания все офицеры на каждой линии могут быть перпендикулярны.
Теория, казалось, работала, но для доказательства её авторам пришлось построить массив размером 6 на 6, заполненный квантовыми офицерами. Огромное количество возможных конфигураций и запутанных ситуаций означало, что им пришлось полагаться на помощь компьютера. Исследователи подключили классическое "почти" решение (расстановка из 36 классических офицеров с несколькими повторениями званий и полков в одном ряду или столбце) и применили алгоритм, который настроил расположение в сторону истинного квантового решения. Алгоритм немного похож на сборку кубика Рубика методом brute force, когда вы исправляете и затем фиксируете первую строку, затем первый столбец, второй столбец и так далее. Когда они повторяли алгоритм снова и снова, массив головоломки становился все ближе и ближе к истинному решению. В конце концов, исследователи достигли точки, когда они смогли увидеть шаблон и заполнить несколько оставшихся записей вручную.
В каком-то смысле Эйлер оказался неправ — хотя в XVIII веке он не мог представить появления квантовых офицеров.
«Они перевернули страницу с этой головоломкой, что уже очень приятно», — сказал Нечита. — «Это очень красивый результат, и мне нравится, как они его получают».
Одна удивительная особенность их решения, по словам соавтора Сухайла Разера, физика из Индийского технологического института в Мадрасе в Ченнаи, заключается в том, что офицерские звания перепутаны только с соседними званиями (короли с ферзями, ладьи со слонами, кони с пешками) и полки с соседними полками. Еще одним сюрпризом стали коэффициенты, появляющиеся в записях квантового латинского квадрата. Эти коэффициенты представляют собой числа, которые, по сути, говорят вам, какой вес придавать различным терминам в суперпозиции. Любопытно, что соотношение коэффициентов, на котором остановился алгоритм, было 1,618… — знаменитое золотое сечение.
Решение также известно как абсолютно максимально запутанное состояние (AMЗ), расположение квантовых объектов, которое считается важным для ряда приложений, включая квантовую коррекцию ошибок — способа избыточного хранения информации в квантовых компьютерах, чтобы она сохранялась даже при повреждении данных. В АМЗ корреляции между измерениями квантовых объектов настолько сильны, насколько это возможно: если у Алисы и Боба "запутались" монеты, и Алиса подбрасывает свою монету и выпадает орел, она точно знает, что у Боба решка, и наоборот. Две монеты могут быть максимально запутаны, как и три, но не четыре: если Кэрол и Дэйв присоединятся к подбрасыванию монеты, Алиса никогда не сможет быть уверена, что получит Боб.
Однако новое исследование доказывает, что если у вас есть набор из четырех запутанных игральных костей, а не монет, они могут быть максимально запутаны. Расположение шестигранных игральных костей эквивалентно квантовому латинскому квадрату 6 на 6. Из-за присутствия золотого сечения в их решении исследователи назвали его «золотым AMЗ».
Исследователи ранее разработали другие AMЗ, начав с классических кодов с исправлением ошибок и найдя аналогичные квантовые версии. Но новоявленный золотой AMЗ отличается от него и не имеет классического криптографического аналога. Бурхардт подозревает, что это может быть первый представитель нового класса квантовых кодов с исправлением ошибок. С другой стороны, может оказаться не менее интересно, если золотой AMЗ останется уникальным.
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.
Комментарии (72)
Gaikotsu
24.01.2022 09:46+32Я ведь правильно понимаю, что оригинальную головоломку все же не решили? А решили ее модификацию, добавив условия, которые позволили ее решить.
LKamrad Автор
24.01.2022 09:57-18Решили, добавив запутанность. Но, заметьте, в условии оригинальной головоломки нет отрицания использования запутанности. Это примерно как с котом Шредингера. Разумеется, когда откроем ящик, он будет или мертв, или жив, но не открывая ящик, нам придется определить его состояние как суперпозицию живого-мертвого кота.
StjarnornasFred
24.01.2022 12:33+22Погодите. Что значит "нам придётся", если речь о чётком факте, который может быть выражен как "да" или "нет" и никак иначе? Если мы не знаем, да или нет, мы так и говорим: не знаем, неизвестно, не выявлено. А то ведь, знаете ли, жизнь на Альфа-Центавре тоже в суперпозиции: то ли есть, то ли нет.
В оригинальной головоломке есть условие: офицеры разных званий и разных полков. Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания. Если мы заменим офицеров на спортсменов, полки на стили боевых искусств, а звания на пояса, то, в принципе, описанное вами станет возможно - но это будет уже другая задача и у неё будет дополнительное условие.
Проще говоря: исходная задача до сих пор не решена, вместо этого решили что-то другое и отчитались об успехе. Молодцы, конечно, но не в том направлении.
ZiggiPop
24.01.2022 18:50+7>Один и тот же офицер не может служить одновременно в разных полках и иметь разные звания.
Ну почему же? Полковник Советской Армии Исаев одновременно был штандартенфюрером СС (младший полковник). В условиях задачи не оговорено, что воинские формирования обязательно должны быть в рамках одной страны.
Delsian
24.01.2022 10:34+9Просто добавили в Устав возможность службы по совместительству для офицеров.
Old_Chroft
25.01.2022 03:44+1У военных если звание (сержант, лейтенант, etc), и должность - типа командир взвода, начальник штаба и т.д. Должности они вполне себе совмещают (например, кто то в отпуске), но вот чтоб один погон капитанский, а второй лейтенантский... Хотя бывает:
Кадры расположены именно в том порядке, в каком появляются в фильме - и его не понизили в звании, а наоборот доверили АПЛ. Но киноделам можно, у них постоянно "квантовая неопределенность" с одеждой/оружием/техникой :)
Bamboleoni
26.01.2022 09:48+2вот чисто зарегался, чтоб ответить. где ты тут увидел погон лейтенанта? если это погоны капитанов 1 и второго рангов соответственно? это ж вмф. плюс, даже если не приглядываться, видно, что это погоны старшего офицера.
Old_Chroft
26.01.2022 10:04Я знаю что на скриншотах не "лейтенантский" и "капитанский" погоны (у них один просвет на погоне, а у капитана вообще 4 звезды) - эти звания в коментарии я привел для примера. Свою ошибку - не совсем четкую формулировку - я осознал когда редактировать комментарий было уже поздно.
ITMatika
24.01.2022 11:33+16Оригинальная головоломка для 36 офицеров давно решена и доказано, что решение отсутствует.
warlock13
24.01.2022 20:52+2Да, конечно. Только не добавив условия, а придумав совсем другую задачу, которая, однако, имеет вполне определённую связь с исходной. (Так, исходную задачу можно получить из "квантовой", наложив дополнительные условия "классичности" офицеров.)
Knight_Kotlin
24.01.2022 09:46-3Я думаю, что Леонард Эйлер русский математик.
LKamrad Автор
24.01.2022 10:04Жил в России с 1727 по 1741 год и с 1766 по 1783 год до своей смерти, был членом Академии наук России большую часть своей жизни.
Knight_Kotlin
24.01.2022 11:10-2Все правильно, 1927 г. Эйлера стал адъюнктом высшей математики, в Швейцарии он только учился (на факультета искусств).
Vitter
24.01.2022 17:02+9Ну, так вы и Хуго Шмайссера сделаете российским. Напомню, его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова. А сам Калашников даже в руках этот автомат не умеет правильно держать.
Эйлер никогда не был ни русским, ни российским математиком. Он был приглашённым швейцарским математиком в Росссийской Империи.
Wesha
24.01.2022 21:51+8его после Второй Мировой интернировали военнопленным в СССР, где он изобрёл автомат .. Калашникова.
Настало время прохладных историй.
ksbes
25.01.2022 09:58+1Если кому интересно, то клаш — это американская винтовка Гранда (да-да, та самая, которая большой палец закусывала), развернутая вверх ногами (чтоб не сверху магазин вставлять) и с приделанным стволом от СКС.
Немцы там и рядом не валялись, у них своя «родовая линия» от шушпангевера — HK (я держал в руках оба (пострелять так и не дали) — реально как внук и дедушка).
Но все такие рассуждения конечно же — очень большое утрирование. Это как написать свой очередной интернет магазин: все те же фреймворки и тонны заимствования идей в композиции и UI, но магазин всё равно свой, отличный от других.
Walker_XXI
25.01.2022 11:20+5Ну Вы сравнили!
Шмайссер был насильно привезён в СССР уже состоявшимся профессионалом (было ему за 60), инженером с массой уникальных разработок (кстати, военнопленным он не был - ему просто сделали предложение, от которого он не смог отказаться, получая при этом весьма неплохую зарплату). А Эйлер швейцарским оставался лишь по подданству. Приехал в Россию добровольно, в 20 лет покинув родную Швейцарию (в которую, кстати, больше не вернулся). Учёным с мировым именем он стал работая именно в Российской Академии. В России прожил большую часть жизни, здесь же написал большую часть своих трудов, здесь же и похоронен (как и его потомки). Впрочем, прусский период его творчества также имеет большое значение.
А следуя Вашей логике и Екатерина II не была Российской Императрицей, так, немецкой девочкой по вызову.
BARONtheKNIGHT
24.01.2022 11:22+1Сложный момент. С одной стороны, это не решение задачи, это взгляд на нее с другой стороны, с созданием новых условий. Но с другой стороны, математика его времени не могла решить эту задачу, в то время как нынешняя предлагает решение, но можно ли называть и то и то математикой, ведь за 243 года, квантовая математика стала своего рода аддоном для обычной, как евклидова геометрия, или макрофизика, которая тоже живет по своим правилам. Мой вывод, нет задача не решена, потому что здесь идет подмена понятий с добавлением "вариантов"
wataru
24.01.2022 19:50+6Это не решение. Они построили другую задачу, где искомые объекты уже не квадраты из разноцветных фигур, а из чего-то сильно более сложного (каждый объект обладает какой-то непрервыной комбинацией свойств). В такой формулировки эта задача решается.
Как вот нельзя в целых числах решить x^2-2=0, но при переходе к вещественным числам решение появляется. Но это уже другая задача.
igrishaev
24.01.2022 12:41+1Может, глупый вопрос, но все же: эту задачу нельзя решить простым перебором?
Alexandroppolus
24.01.2022 14:31+3Перебором можно подтвердить, что для 6х6 таких расстановок нет. Это и будет решение - вопрос-то ставился "можно ли". Простенькое упражнение на кодинг.
navferty
24.01.2022 14:33-2Число возможных сочетаний: факториал от 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 миллиардов раз меньше...
Alexandroppolus
24.01.2022 14:38+3факториал от 36
Не надо так драматизировать. Здесь два факториала от 6 - расставать звания по ячейкам матрицы (6!), расставить полки по ячейкам (6!), каждую расстановку проверить, что присутствуют все возможные пары (звание, полк). Итого порядка 36 * 6! * 6! проверок
Alexandroppolus
24.01.2022 14:51+2Нет, туплю. 36 * 6! * 6! * 6! будет. За каждым полком закрепляем горизонтальную строку матрицы. Перебираем независимо: все перестановки полков по столбцам (6!), все перестановки званий по строкам (6!), все перестановки званий по столбцам (6!), и на каждой из таких комбинаций проверка 36 пар (звание, полк)
ibKpoxa
24.01.2022 16:14Ну и еще в 36 раз меньше, например можно захардкодить офицера в ключевом углу, принципиально ничего не изменит, а вариантов меньше.
XenRE
24.01.2022 20:43Все равно не так — нужно добиться чтобы в строках и столбцах небыло повторов, а не просто переставлять строки/столбцы. Получается для 1й строки 6!=720 комбинаций, для 2й нужно исключить дублирование значений в столбцах из 1й и т.д., последняя строка будет без вариантов состоять из того, что еще не встречалось в столбцах. Итого 720*309*112*32*6*1 = 4 784 209 920 комбинаций. Приемлимо для перебора. Цвет можно захардкодить как в картинке из статьи: c=(x+y)%size, а тип перебирать, решение будет найдено если в матрице нет одинаковых комбинаций цвет+тип.
wataru
25.01.2022 01:05А точно такое решение будет существовать? Почему вы считаете, что можно хардкодить цвет по диоганалям?
ksbes
25.01.2022 11:47+1вообще в латинских квадратах принято хардкодить не диагональ, а первый столбец и строку. Т.к. от перестановки местами строк или столбцов в уже сложенном латинском квадрате ничего не поменяется и потому любой сложенный квадрат можно привести к такому виду.
при этом точной формулы количества «уникальных» квадратов до сих пор нет — находят «ручками». Для 6х6 — it's over 9000 (совсем немного, вроде бы).
vics001
24.01.2022 23:40Более века спустя французский математик Гастон Тарри доказал, что действительно невозможно расположить 36 офицеров Эйлера в квадрате 6 на 6 без повторений.
bBars
24.01.2022 20:47+5Давайте повсюду совать так популярную нынче квантовую запутанность и говорить, что мяукало Шрёдингера решает все проблемы
sim31r
25.01.2022 09:47+1Можно начать с расчета заработной платы и премий. Типа вы хорошо подумали, но ваша премия квантово запутана, она есть, но наблюдать за ней не нужно, иначе разрушается квантвая суперпозиция.
Walker_XXI
25.01.2022 12:12+5Да, нынче бедного котика к месту и не к месту поминают, хотя кот Шрёдингера - иллюстрация суперпозиции квантовых состояний, а не квантовых корреляций (aka квантовой запутанности). Более того, Шрёдингер придумал своего кота, как пример системы, для которой описание в терминах суперпозиции состояний не является адекватным (как и для офицеров из задачки Эйлера). Если же мы допускаем суперпозицию, то описываем явно не кота, а нечто иное.
PavelMos
24.01.2022 23:53+2Допустим у меня есть керамическая плитка 10 разных цветов 10х10 см, и я хочу выложить ей стену 100х200 см так, чтобы линии не повторялись.
Есть ли какие-то методики, чтобы рассчитать такую раскладку ?
sokratstoforandov
24.01.2022 23:53Тут все относительно, если проецировать эту задачу на наш мир то да, через квантовую физику она решается. Но если это задача чисто логическая, и где нет квантового мира, то в рамках того мира она не решаема.
kantocoder
25.01.2022 02:29В 1779 году швейцарский математик Леонард Эйлер
А ничего что Леонард Эйлер полжизни прожил и проработал в России, создал Императорскую Академию Наук, и похоронен в Санкт Петербурге? "Швейцарский математик"...
zhuravlev_oe
25.01.2022 07:42+3Можно Эйлера вывезти из Швейцарии, но Швейцарию из Эйлера - никогда!
rrrav
25.01.2022 08:23+2Помню в годы учебы на физфаке МГУ была такая шутка - если бы Эйлер был русским, то МГУ был бы имени Эйлера.
GomboTs
25.01.2022 08:39+2Ну если Новоселов и Гейм - русские физики, то Эйлер, безусловно, швейцарский математик.
Walker_XXI
25.01.2022 11:30Тут же можно и Георгия Гамова вспомнить - согласно англоязычной википедии он американский учёный, родившийся в России.
Yanuka
25.01.2022 12:25Великий Эйлер ошибся по поводу двух взаимно ортогональных квадратов 10*10: они таки да существуют. Их построили в 1959- м Паркер, Боуз и Шрикхенд. А вот трех до сих пор никто не нашел!
Three MOLS of order 10 not exist!
LevOrdabesov
25.01.2022 13:29Т.е. фигуры в квадратах заданы «динамически», и их значение зависит от того, на какую из них наблюдатель смотрит в данный момент?
dMac
25.01.2022 15:22-1Не считается, это чит. Подобно тому как придумали мнимую единицу, чтобы квадратные корни отрицательных чисел вычислять.
mayorovp
26.01.2022 11:54+1Вот как раз мнимая единица не чит, а элемент поля комплексных чисел.
dMac
26.01.2022 23:23Моя вечная проблема - что шучу с "мордой кирпичом". Конечно же, и то и другое - не чит, а расширение взгляда на задачу. Вот это вот детское "не считается" должно было настроить на шутливый лад
maxxurg6
26.01.2022 09:49Чем моё решение не соответствует заявленныим требованиям задачи? В решении 6 разных офицеров шести разных полков, что явно выражено в цифровом формате.
ksbes
26.01.2022 11:30У вас офицеры — не разные. Каждого типа — по шесть штук, и соответственно, 30 типов просто отсутствуют (например, где все шестёрки, которые не (6,6)? И все другие пары, где сумма элементов не равна 6?).
А по условиям Эйлера нужно расставить 36 уникальных пар.
Для начала сделайте это хотя бы для 2х2 — всего 4 уникальные пары!
P.S.
(Автору статьи и просто понимающим людям) хотя бы для этого случая (2х2) объясните конкретный механизм как эта квантовая запутанность задачу решает.
AllexIn
Я, наверно, тупенький. Но выглядит так, что они просто добавили вариантов.
eimrine
Для тех кому не понятно почему задача не решается, во избежание трат времени других людей.
wataru
И что эта картинка означает? Ведь точно такую же картинку можно нарисовать для квадрата 4x4, где решение существует (поросто мысленно отрежте крайние клетки от этой доски)?
Максимум что вы тут доказали, что именно вот таким вот образом начинать расстановку фигур — не стоит.
Wesha
Я понял, что по одной диагонали — звания (фигура), по другой - полки (цвет), но как это мешает решить задачу (в той постановке, в которой она в статье), я не понял.
eimrine
Спасибо за замечание, просто я час потратил на таскание фигурок и почему-то мне показалось что я смог показать типа вырожденный случай почему это невозможно. Вы правы, моё предположение необоснованно, и вообще надо было сразу признаться что я ненастоящий математик :(
RetroGuy
Все-таки интересно, любопытства ради, где взять столько уверенности в себе, чтобы после того, как прочитав что сам Эйлер не смог найти доказательства, и что его нашли только 100 лет спустя, сразу же попытаться найти его самому, да еще так, чтобы показать одной картинкой без лишних обьяснений? :)
Wesha
Я не пытаюсь победить Эйлера — я пытаюсь понять, как ПРАВИЛЬНО звучит условие задачи. Потому что "чтобы в каждом ряду и в каждой колонне каждый полк и звание встречались лишь один раз" — тривиально: присваиваем однозначное соответствие "полк 1 = звание 1" ... "полк 6 = звание 6", и вуаля.
Walker_XXI
Читаем в начале статьи:
Поскольку сам Эйлер считал задачку нетривиальной и неразрешимой, Ваше толкование условий, очевидно, ошибочно. Надо понимать так, что в каждом полку нет двух офицеров в одном звании. Там даже для наглядности картинку с шахматными фигурками привели: нет двух совпадающих фигур одного цвета, они там вообще все уникальны - каждая отличается от остальных как минимум цветом или "званием".
Wesha
Звучит логично. Только теперь вопрос: почему это не написал автор статьи, а мы с Вами вынуждены догадываться?
ShadowTheAge
Wesha
"различных" != "не имеющих одинаковых".
"полковник, два сержанта и сто подпоручиков" — это вполне "в полку офицеры различных званий".
ShadowTheAge
Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Wesha
Ну так это как в том анекдоте — программистам дали задание "постройте мне самолёт". Через месяц приходят принимать — стоит на взлётной полосе самолёт. Бетонный. "А как же он летает? — ЛЕТАЕТ??? В техзадании про полёты ничего не было!!!"
В моём примере далеко не все офицеры "одинаковые". В постановке задач должно было быть "в полку не может быть двух одинаковых офицеров". Тогда у нас выходит аж пять критерия уникальности:
уникально звание в строке
уникально звание в столбце
уникален полк в строке
уникален полк в столбце
уникально звание в полку
То есть задача на самом деле трёхмерная (третья ось — "звание").
mayorovp
https://habr.com/ru/post/262429/
Wesha
Здесь не пикабу какой, здесь программисты собрались. А у нас профдеформация — компьютеру задачи нужно записывать именно так, как в в конце статьи по Вашей ссылке.
Walker_XXI
По постановке 4-мерная: 2 пространственных оси, плюс звание и полк. Но есть принципы запрета (не может быть двух офицеров в одном сотсотянии, не может быть двух однополчан в одном звании и др.), что снижает размерность конфигурационного пространства. Да и вообще оно дискретно и конечно. Задача в том, чтобы доказать, что при условиях Эйлера (в рядах и стролбцах не должно быть совпадений по полкам и званиям), число допустимых состояний меньше 36.
Wesha
Звание и полк не независимы, между ними есть условие. Я долго колебался, записывать ли полк в отдельное измерение, и решил не делать этого.