Задача о восстановлении бус

Задача о восстановлении бус — это задача занимательной математики, решённая в начале 21-го века.

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

Задача восстановления бус требует восстановления бус, состоящих из n бусинок, каждая из которых либо чёрная, либо белая, зная частичную информацию. Назовём k-конфигурацией в бусах подмножество k позицией в бусах. Две конфигурации изоморфны, если одна может быть получена из другой вращением бус. На шаге k процесса восстановления доступна частичная информация, содержащая для каждой k-конфигурации число ей изоморфных k-конфигураций, содержащих только чёрные бусинки. Задача состоит в установлении числа шагов для данного n, необходимых (в худшем случае) для точного восстановления чередования чёрных и белых бусинок.

Решение

Алон, Каро, Красиков и Родитти показали, что ${\displaystyle 1+\log _{2}(n)}$ шагов достаточно, если использовать остроумно улучшенный принцип включений-исключений.

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

Люк Пебоди показал, что для любого n достаточно 6 шагов.

См. также

• Браслет и Бусы^[англ.]
• Функция Моро подсчёта бусин^[англ.]
• Задача о разрезании ожерелья