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

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

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

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

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

Верхні межі

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

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

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття