Оглавление
Проблема с ожерельем
-
Задача об ожерелье
- Задача о восстановлении ожерелья из двоичных значений по частичной информации.
- Информация указывает количество копий каждого расположения украшений.
-
Формальное определение
- Определение k-конфигурации для ожерелья из k черных и n-k белых бусин.
- Подсчет количества способов вращения k-конфигурации, чтобы каждая черная бусина совпадала с черной бусиной исходного ожерелья.
-
Проблема определения порога
- Вопрос о том, насколько большим должен быть порог K, чтобы информация полностью определяла ожерелье.
- Эквивалентно, сколько этапов требуется для воссоздания точного узора из черных и белых бусин.
-
Верхние границы
- Алон, Каро, Красиков и Родитти показали, что достаточно 1 + log2(n).
- Рэдклифф и Скотт доказали, что для простых чисел достаточно 3, а для любого числа – 9-кратного числа простых множителей.
- Пебоди показал, что достаточно 6 для любого числа, а в последующих работах – что для нечетных чисел достаточно 4.
-
Рекомендации и примечания
- Статья содержит ссылки на другие статьи и информацию о форматировании и стилизации текста.
Полный текст статьи: