Задача о восстановлении бус ({g;gcg k fkvvmgukflyunn Qrv)

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

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

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

Решение

Алон, Каро, Красиков и Родитти показали, что $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:10.1016/0095-8956(89)90016-6.
RadcliffeA. J., Scott A. D. Reconstructing subsets of Z_n // J. Combin. Theory Ser. A. — 1998. — Т. 83. — С. 169–187. — doi:10.1006/jcta.1998.2870.
Luke Pebody. The reconstructibility of finite abelian groups // Combin. Probab. Comput.. — 2004. — Т. 13. — С. 867–892. — doi:10.1017/S0963548303005807.
Luke Pebody. Reconstructing Odd Necklaces // Combin. Probab. Comput.. — 2007. — Т. 16. — С. 503–514. — doi:10.1017/S0963548306007875.
Paul K. Stockmeyer. The charm bracelet problem and its applications // Lecture Notes in Mathematics. — 1974. — Т. 406. — С. 339–349. — doi:10.1007/BFb0066456.