Проблема с ожерельем

Эта статья об определении порядка драгоценных камней на ожерелье. Информацию о комбинаторной задаче справедливого деления см. в разделе Задача разделения ожерелья .

— Проблема ожерелья это задача развлекательной математики, касающаяся восстановления ожерелья (циклического расположения двоичных значений) на основе частичной информации.

Формулировка

Задача о ожерелье включает в себя реконструкцию ожерелья из $n$ бусины, каждая из которых либо черная, либо белая, по частичной информации. Информация указывает, сколько копий каждого возможного расположения содержит ожерелье. $k$ черные бусины. Например, для $k=2$, указанная информация дает количество пар черных бусин, разделенных $i$ должности, для $i=0,\dots ,\lfloor n/2-1\rfloor$.Это можно сделать формальным, определив $k$-конфигурация в виде ожерелья $k$ черные бусины и $n-k$ белые бусины и посчитаем количество способов вращения $k$-настроить так, чтобы каждая его черная бусина совпадала с одной из черных бусинок данного колье.

Задача ожерелья спрашивает: если $n$ задано, а также количество копий каждого $k$-конфигурация известна до некоторого порога $k\leq K$, насколько велик порог $K$ должно быть до того, как эта информация полностью определит ожерелье, которое она описывает? Аналогично, если информация о $k$-конфигурации предоставляются поэтапно, где $k$Этап определяет количество копий каждого $k$-конфигурация, сколько этапов необходимо (в худшем случае) для того, чтобы воссоздать точный узор из черно-белых бусин в оригинальном колье?

Верхние границы

Алон , Каро , Красиков и Родитти показали, что 1 + log ₂ ( n ) достаточно, используя хитроумно усовершенствованный принцип включения-исключения .

Рэдклифф и Скотт показали, что если n простое, достаточно 3, а для любого n 9-кратного количества простых делителей числа n достаточно .

Пибоди показал, что для любого n достаточно 6, а в последующей статье, что для нечетного n достаточно 4. Он предположил, что 4 снова достаточно даже для n, большего 10, но это остается недоказанным.

См. также

• Ожерелье (комбинаторика)
• Браслет (комбинаторика)
• Функция подсчета ожерелья Моро
• Проблема раскола ожерелья

Ссылки

• Алон, Н.; Каро, Ю.; Красиков И.; Родитти, Ю. (1989). «Задачи комбинаторной реконструкции» . Дж. Комбин. Теория Сер. Б. ​ 47 (2): 153–161. CiteSeerX   10.1.1.300.9350 . дои : 10.1016/0095-8956(89)90016-6 .
• Рэдклифф, Эй Джей; Скотт, AD (1998). «Реконструкция подмножеств Z _n » . Дж. Комбин. Теория Сер. А. ​ 83 (2): 169–187. дои : 10.1006/jcta.1998.2870 .
• Пибоди, Люк (2004). «Реконструируемость конечных абелевых групп». Комбинировать. Вероятно. Вычислить. 13 (6): 867–892. дои : 10.1017/S0963548303005807 . S2CID   37756823 .
• Пибоди, Люк (2007). «Реконструкция странных ожерелий». Комбинировать. Вероятно. Вычислить . 16 (4): 503–514. дои : 10.1017/S0963548306007875 . S2CID   13278945 .
• Пол К. Стокмейер (1974). «Проблема браслета-шарма и ее применение». В Бари, Рут А .; Харари, Фрэнк (ред.). Графы и комбинаторика: материалы Столичной конференции по теории графов и комбинаторике в Университете Джорджа Вашингтона, 18–22 июня 1973 г. Конспект лекций по математике. Том. 406. стр. 339–349. дои : 10.1007/BFb0066456 . ISBN  978-3-540-06854-9 .