Задача о восстановлении бус
Задача о восстановлении бус — это задача занимательной математики, решённая в начале 21-го века.
Формулировка
Задача восстановления бус требует восстановления бус, состоящих из n бусинок, каждая из которых либо чёрная, либо белая, зная частичную информацию. Назовём k-конфигурацией в бусах подмножество k позицией в бусах. Две конфигурации изоморфны, если одна может быть получена из другой вращением бус. На шаге k процесса восстановления доступна частичная информация, содержащая для каждой k-конфигурации число ей изоморфных k-конфигураций, содержащих только чёрные бусинки. Задача состоит в установлении числа шагов для данного n, необходимых (в худшем случае) для точного восстановления чередования чёрных и белых бусинок.
Решение
Алон, Каро, Красиков и Родитти показали, что шагов достаточно, если использовать остроумно улучшенный принцип включений-исключений.
Рэдклифф и Скотт показали, что в случае простого n 3 шагов достаточно, а для произвольного n достаточно 9-кратного числа простых множителей числа n.
Люк Пебоди показал, что для любого n достаточно 6 шагов.