Problem z naszyjnikiem

Ten artykuł dotyczy określania kolejności klejnotów w naszyjniku. Aby zapoznać się z problemem uczciwego podziału kombinatorycznego , zobacz Problem dzielenia naszyjnika .

Problem naszyjnika to problem w matematyce rekreacyjnej dotyczący rekonstrukcji naszyjników (cyklicznych układów wartości binarnych) z częściowych informacji.

Sformułowanie

Problem z naszyjnikiem polega na rekonstrukcji naszyjnika z koralików $,$ z których każdy jest czarny lub biały, na podstawie częściowych informacji $,$ ile kopii zawiera naszyjnik każdego możliwego układu koralików. Na przykład dla , $pozycjami$ podaje liczbę par czarnych koralików, $są$ dla ${\ Displaystyle i = 0, \ kropki \ lfloor n/2-1 \ rfloor}$ . Można $koralików$ uczynić formalnym, definiując konfigurację jako naszyjnik z $koralików$ i białych i licząc liczbę sposobów obracania a k { $\$${\ displaystyle k}$ -konfiguracja tak, aby każdy z jej czarnych koralików pokrywał się z jednym z czarnych koralików danego naszyjnika.

Problem z naszyjnikiem polega na tym, że jeśli $podano$$kopii$ każdej $jest$ znana do pewnego progu , jak czy próg musi być, zanim ta informacja całkowicie określi naszyjnik, który $opisuje$$Równoważnie$ , jeśli informacje o są dostarczane etapami, gdzie ${\ displaystyle k}$ etap zawiera liczbę kopii każdej $,$ ile etapów jest potrzebnych (w najgorszym przypadku) do odtworzenia dokładnego wzoru czarno-białych koralików w oryginalnym naszyjniku?

Górne granice

Alon , Caro, Krasikov i Roditty wykazali, że 1 + log ₂ ( n ) jest wystarczające, używając sprytnie ulepszonej zasady włączania-wyłączania .

Radcliffe i Scott wykazali, że jeśli n jest liczbą pierwszą, wystarczy 3, a dla każdego n wystarczy 9-krotna liczba czynników pierwszych n .

Pebody wykazał, że dla dowolnego n wystarczy 6, aw kolejnej pracy, że dla nieparzystego n wystarczy 4. Przypuszczał, że 4 jest ponownie wystarczające nawet dla n większego niż 10, ale pozostaje to nieudowodnione.

Zobacz też

• Naszyjnik (kombinatoryka)
• Bransoletka (kombinatoryka)
• Funkcja liczenia naszyjników Moreau
• Problem z pękającym naszyjnikiem

• Alon, N.; Caro, Y.; Krasikow, I.; Roditty, Y. (1989). „Problemy rekonstrukcji kombinatorycznej” . J. Kombajn. Teoria Ser. B. _ 47 (2): 153–161. doi : 10.1016/0095-8956(89)90016-6 .
• Radcliffe, AJ; Scott, AD (1998). _{Rekonstrukcja} podzbiorów Zn ” . J. Kombajn. Teoria Ser. A. _ 83 (2): 169–187. doi : 10.1006/jcta.1998.2870 .
• Pebody, Łukasz (2004). „Odtwarzalność skończonych grup abelowych”. Połącz. Prawdopodobne. Oblicz. 13 (6): 867–892. doi : 10.1017/S0963548303005807 .
• Pebody, Łukasz (2007). „Rekonstrukcja dziwnych naszyjników”. Połącz. Prawdopodobne. Oblicz . 16 (4): 503–514. doi : 10.1017/S0963548306007875 .
•   Paul K. Stockmeyer (1974). „Problem bransoletki z wisiorkiem i jego zastosowania”. W Bari, Ruth A .; Harary, Frank (red.). Grafy i kombinatoryka: Proceedings of the Capital Conference on Graph Theory and Combinatoryics na George Washington University, 18–22 czerwca 1973 . Notatki z wykładów z matematyki. Tom. 406. s. 339–349. doi : 10.1007/BFb0066456 . ISBN 978-3-540-06854-9 .