Problém s náhrdelníkem - Necklace problem

The problém s náhrdelníkem je problém v rekreační matematika o rekonstrukci náhrdelníky (cyklické uspořádání binárních hodnot) z dílčích informací.

Formulace

Problém s náhrdelníkem zahrnuje rekonstrukci a náhrdelník z ${ displaystyle n}$ korálky, z nichž každý je buď černý nebo bílý, z částečných informací. Tato informace určuje, kolik kopií náhrdelník obsahuje každé možné uspořádání ${ displaystyle k}$ černé korálky. Například pro ${ displaystyle k = 2}$ , zadaná informace udává počet párů černých korálků, které jsou odděleny ${ displaystyle i}$ pozice, pro ${ displaystyle i = 0, dots lfloor n / 2-1 rfloor}$ Toho lze dosáhnout formálním definováním a ${ displaystyle k}$ -konfigurace být náhrdelníkem ${ displaystyle k}$ černé korálky a ${ displaystyle n-k}$ bílé korálky a počítání počtu způsobů otáčení a ${ displaystyle k}$ -konfigurace tak, aby se každý z jeho černých korálků shodoval s jedním z černých korálků daného náhrdelníku.

Problém s náhrdelníkem se ptá: pokud ${ displaystyle n}$ je uveden počet kopií každého z nich ${ displaystyle k}$ -konfigurace jsou známy až do určité prahové hodnoty ${ displaystyle k leq K}$ , jak velká je prahová hodnota ${ displaystyle K}$ musí být, než tato informace zcela určí náhrdelník, který popisuje? Ekvivalentně, pokud informace o ${ displaystyle k}$ -configurations je poskytována ve fázích, kdy ${ displaystyle k}$ th stage provides the numbers of copies of each ${ displaystyle k}$ -konfigurace, kolik fází je potřeba (v nejhorším případě) k rekonstrukci přesného vzoru černobílých korálků v původním náhrdelníku?

Horní hranice

Alon, Caro, Krasikov a Roditty ukázal, že 1 + log₂(n) je dostačující, s využitím chytře vylepšeného zásada začlenění - vyloučení.

Radcliffe a Scott ukázal, že pokud n je prime, 3 je dostačující a pro všechny n, 9násobek počtu hlavních faktorů n je dostačující.

Pebody to ukázal každému n, 6 je dostačující a v návazném článku to pro liché n, 4 je dostačující. Domníval se, že 4 je opět dostačující pro sudé n větší než 10, ale zůstává to neprokázané.

Viz také

Reference

Alon, N .; Caro, Y .; Krasikov, I .; Roditty, Y. (1989). „Problémy kombinatorické rekonstrukce“. J. Combin. Theory Ser. B. 47: 153–161. doi:10.1016/0095-8956(89)90016-6.
Radcliffe, A. J .; Scott, A. D. (1998). "Rekonstrukce podskupin Z_n". J. Combin. Theory Ser. A. 83: 169–187. doi:10.1006 / jcta.1998.2870.
Pebody, Luke (2004). "Rekonstruovatelnost konečných abelianských skupin". Kombinovat. Probab. Comput. 13: 867–892. doi:10.1017 / S0963548303005807.
Pebody, Luke (2007). "Rekonstrukce lichých náhrdelníků". Kombinovat. Probab. Comput. 16: 503–514. doi:10.1017 / S0963548306007875.
Paul K. Stockmeyer (1974). Msgstr "Problém s náramkem a jeho aplikacemi". v Bari, Ruth A.; Harary, Franku (eds.). Grafy a kombinatorika: Sborník příspěvků z hlavní konference o teorii grafů a kombinatorice na Univerzitě George Washingtona, 18. – 22. Června 1973. Přednášky z matematiky. 406. 339–349. doi:10.1007 / BFb0066456. ISBN 978-3-540-06854-9.