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

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

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

Решение

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

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

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

См. также

• Задача о разрезании ожерелья

Примечания

Литература

• Alon N., Caro Y., Krasikov I., Roditty Y. Combinatorial reconstruction problems // J. Combin. Theory Ser. B . — 1989. — Т. 47 . — С. 153–161 . — doi : .
• RadcliffeA. J., Scott A. D. Reconstructing subsets of Z _n // J. Combin. Theory Ser. A . — 1998. — Т. 83 . — С. 169–187 . — doi : .
• Luke Pebody. The reconstructibility of finite abelian groups // . — 2004. — Т. 13 . — С. 867–892 . — doi : .
• Luke Pebody. Reconstructing Odd Necklaces // Combin. Probab. Comput.. — 2007. — Т. 16 . — С. 503–514 . — doi : .
• Paul K. Stockmeyer. The charm bracelet problem and its applications // . — 1974. — Т. 406 . — С. 339–349 . — doi : .