Comments 15
Меня эта задача навела на другую мысль. Вот, например, если Незнайка записал на листке бумаги ПИН-код от своей банковской карточки, изменив в нём одну-единственную цифру, а Винтик со Шпунтиком нашли эту записку, то поможет ли им полученная информация воспользоваться банковской карточкой Незнайки?
UPD: То есть Винтику со Шпунтиком известно, что в записи ПИН-кода изменена одна-единственная цифра, но они не знают, какая именно.
Поправьте меня, но задача кажется тривиальной. Допустим, он договорились, что остаток от деления суммы цифр числа на 10 - порядкой номер новой цифры. Всё, что надо - указать недостающую цифру так, чтобы остаток был правильный.
К примеру, если число 777..777777, т.е пропущена 4я позиция (остаток=3), сумма цифр = 9*7=63 = 3 (mod 10). Т.е., нам надо вписать 0: 7770777777
Да. Но это только одно решение. А надо посчитать все :)
Спасибо за понятное объяснение решения. Это напоминает методы генерирования контрольного разряда в разных идентификаторах.
UPD. Полагаю, что можно «изобрести» бесконечно много таких «способов», отличающихся весовыми коэффициентами и правилами свёртки вычисленного результата в единственную цифру.
Винтик суммирует все цифры числа и вписывает своё, что б остаток от деления суммы всех цифр на 10 был равен индексу вписанного числа.
Шпунтику достаточно различать почерк Винтика и Незнайки :)
По некоторым пунктам:
3. В качестве представителя можно взять лексикографически максимальный по всем эквивалентным объектам. Представителей всех классов эквивалентности (а значит и сами классы) можно найти перебором с отсечениями. Просто генерируем элементы объектов в порядке учета их в лексикографическом порядке, применяем действия группы, если удалось перемешать элементы объекта так, что получился объект лексикографически больше - то окатываемся.
4. Можем. Для этого надо представить каждый элемент группы в виде последовательности базовых действий группы. Например, для куба 4х4х4: сначала вращение, потом перестановка слоев по оси x, потом по оси y, потом z. Теперь, пусть мы повращали и переставили слои по оси x. Тогда дальше у нас будут переставляться только блоки из 4 элементов. Но если множество этих блоков не совпадает с множеством блоков начального куба, то смысла их переставлять нет - там нет элементов стабилизатора.
Ну или можно глубже вникнуть в структуру группы. Например, для группы всех перестановок
мощность стабилизатора для объекта
(состоящего из
элементов), на который действует группа, равна произведению факториалов размеров подмножеств одинаковых элементов в.
У меня еще есть непонятки по прочитанному. Я у себя в голове немного другую модель задачи построил, она на изложенную в статье не до конца накладывается. Например, мне не до конца понятно почему для последних двух линий (двух "гиперслоев" в кватернарном случае) надо домножать на какую-то фиксированную степень двойки. У меня двойки для тернарного случая вылезают из функции Ф.
Если что, я свою модельку закодил, и она тоже дает 10752 для тернарного случая. Но наверно поля комментария будут "слишком узки", чтобы расписывать ее во всех подробностях.
Спасибо огромное за комментарий. Именно то, чего я ждал долгое время. И уже думал не дождусь. :) Мне сейчас нужно некоторое время чтобы "переварить". При этом хочу убедиться, что я все понял правильно. Напишу в ЛС. Здесь же - не расскажете, как ваша модель устроена? Хотя бы общую идею?
У меня задача получилась эквивалентная такой. На примере тернарного случая: нужно посчитать количество способов расставить в кубе 3х3х3 числа от 1 до 3 так, чтобы в каждом ряду (из 3х элементов), параллельному оси x, была ровно одна единица, в каждом ряду, параллельному оси y, была ровно одна двойка, и в каждом ряду, параллельному оси z, была ровно одна тройка. Для кватернарного случая это будет уже гиперкуб 4х4х4х4, числа от 1 до 4, направлений осей 4. Ну и так далее.
Вот эти ваши "дефекты" по сути кодируют положения всех единиц, где цвет - это номер слоя, в котором эти единицы располагаются. Как только мы зафиксировали положения единиц, задача распадается на X независимых - нам нужно посчитать для каждого слоя (или "гиперслоя" при X>3) количество способов расставить там остальные числа, после чего количество этих способов по всем слоям перемножить (это по сути функция Ф). Ну и ответом будем сумма способов по всем "дефектам".
Из ограничений выше следует, что в каждом гиперслое единиц должно быть поровну, иначе числа для других осей в этот гиперслой не поместятся. То есть в тернарном случае в каждом слое должно быть по 3 единицы, в кватернарном - по 16 (там гиперслои - это кубы 4х4х4). Так повезло, что для каждой расстановки трех единиц в одном слое в тернарном случае дальше способов заполнить либо 2, либо 0 (если расстановка этих трех единиц в один ряд). В кватернарном случае, боюсь, будет все сложнее, и просто умножением на степень двойки не отделаться.
Итого количество "дефектов" для кватернарного случая равно 64! / (16!)^4, что довольно много, поэтому объединять их в классы эквивалентности - хорошая идея. Но что-то классов эквивалентности тоже пока получается много)
Мы получили 10752 = 2^9 37. Это выглядит странно. /.../ И непонятно, откуда взялась семерка в задаче, где интуитивно больше ожидаешь троек.
По этому поводу наверно можно даже диссертацию написать, о том как анализ известного решения задачи, например через разложение этого решения на простые множители, позволяет найти эффективный метод решения этой задачи. Я хорошо помню как в школе я иногда заглядывал в ответы и это сразу помогало найти хитрый способ решения любой хитро-закрученной задачи.
Но мне интереснее было бы написать диссертацию о критериях эффективности реализации алгоритма на заданной системе команд, заданной разрядности (то есть на заданном ассемблере). Для примера DCT, Хафмана, LDPC, ... на MMX-ах, SSE, ...
Потому что решение может конечно Искусственный Интеллект сгенерировать, но если у нас нет объективных критериев оценки этого решения численных, распространять это решение будет чревато.
Интересно, кстати, получилось бы применить теорию множеств при формулировании таких критериев, пригодилась бы она там?
Винтик и Шпунтик — Сhallenge продолжается