Проблема с ожерельем - Necklace problem

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

• Alon, N .; Caro, Y .; Красиков, И .; Родитти, Ю. (1989). «Комбинаторные задачи реконструкции». J. Combin. Теория Сер. B. 47: 153–161. Дои:10.1016/0095-8956(89)90016-6.
• Рэдклифф, А. Дж .; Скотт, А. Д. (1998). "Реконструкция подмножеств Z_п". J. Combin. Теория Сер. А. 83: 169–187. Дои:10.1006 / jcta.1998.2870.
• Пебоди, Люк (2004). «Реконструируемость конечных абелевых групп». Комбинировать. Вероятно. Comput. 13: 867–892. Дои:10.1017 / S0963548303005807.
• Пебоди, Люк (2007). «Реконструкция странных ожерелий». Комбинировать. Вероятно. Вычислить. 16: 503–514. Дои:10.1017 / S0963548306007875.
• Пол К. Стокмейер (1974). «Проблема браслета-оберега и его применения». В Бари, Рут А.; Харари, Фрэнк (ред.). Графы и комбинаторика: материалы конференции Capital по теории графов и комбинаторике в Университете Джорджа Вашингтона, 18–22 июня 1973 г.. Конспект лекций по математике. 406. С. 339–349. Дои:10.1007 / BFb0066456. ISBN  978-3-540-06854-9.