Задача про відновлення намиста

Задача про відновлення намиста — це задача цікавої математики, розв'язана на початку XXI століття.

Формулювання

Задача передбачає відновлення намиста з $n$ намистин, кожна з яких чорна або біла, за частковою інформацією. Інформація вказує, скільки разів містить намисто кожне можливе розташування $k$ чорних намистин. Наприклад, для $k=2$, зазначена інформація дає кількість пар чорних намистин, які розділені $i$ позиціями, для $i=0,\dots \lfloor n/2-1\rfloor$. Це можна формалізувати, визначивши $k$-конфігурацію як намисто з $k$ чорних намистин і $n-k$ білих намистин та підрахувавши кількість способів обертання $k$-конфігурації так, щоб кожна її чорна намистина збігалася з однією з чорних намистин даного намиста.

В задачі про відновлення намиста запитується: якщо дано $n$, і кількості копій кожної $k$-конфігурації відомі до певного порогу $k\leq K$, наскільки великий поріг $K$ потрібно, щоб ця інформація повністю визначила намисто, яке вона описує? Еквівалентно, якщо інформація про $k$-конфігурації надається поетапно, де $k$-й етап надає кількість копій кожної $k$-конфігурації, скільки етапів потрібно (в гіршому випадку) для того, щоб відновити точне розташування чорних і білих намистин в намисті?

Верхні межі

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

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

Пібоді показав, що для будь-якого n достатньо 6, а в наступній статті, що для непарного n достатньо 4. Він припустив, що 4 також достатньо навіть для n більше 10, але це залишається недоведеним.

Див. також

• Намисто (комбінаторика)
• Браслет (комбінаторика)
• Функція Моро підрахунку намистин
• Задача про розрізання намиста

Література

• Alon N., Caro Y., Krasikov I., Roditty Y. Combinatorial reconstruction problems // J. Combin. Theory Ser. B. — 1989. — Т. 47 (5 травня). — С. 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 (5 травня). — С. 169–187. — DOI:10.1006/jcta.1998.2870.
• Luke Pebody. The reconstructibility of finite abelian groups // Combin. Probab. Comput.. — 2004. — Т. 13 (5 травня). — С. 867–892. — DOI:10.1017/S0963548303005807.
• Luke Pebody. Reconstructing Odd Necklaces // Combin. Probab. Comput.. — 2007. — Т. 16 (5 травня). — С. 503–514. — DOI:10.1017/S0963548306007875.
• Paul K. Stockmeyer. The charm bracelet problem and its applications // Lecture Notes in Mathematics. — 1974. — Т. 406 (5 травня). — С. 339–349. — DOI:10.1007/BFb0066456.