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

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

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

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

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

Верхні межі

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

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

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

Див. також

• Намисто (комбінаторика)
• Браслет (комбінаторика)
• ^[en]
• Задача про розрізання намиста

Примітки

Література

• Alon N., Caro Y., Krasikov I., Roditty Y. Combinatorial reconstruction problems // . — 1989. — Т. 47 (8 липня). — С. 153–161. — DOI:10.1016/0095-8956(89)90016-6.
• RadcliffeA. J., Scott A. D. Reconstructing subsets of Z_n // . — 1998. — Т. 83 (8 липня). — С. 169–187. — DOI:10.1006/jcta.1998.2870.
• Luke Pebody. The reconstructibility of finite abelian groups // . — 2004. — Т. 13 (8 липня). — С. 867–892. — DOI:10.1017/S0963548303005807.
• Luke Pebody. Reconstructing Odd Necklaces // Combin. Probab. Comput.. — 2007. — Т. 16 (8 липня). — С. 503–514. — DOI:10.1017/S0963548306007875.
• Paul K. Stockmeyer. The charm bracelet problem and its applications // . — 1974. — Т. 406 (8 липня). — С. 339–349. — DOI:10.1007/BFb0066456.