Gyöngy helyreállítási probléma
A Bead Restoration Problem egy szórakoztató matematikai feladat , amelyet a 21. század elején oldottak meg.
Megfogalmazás
A gyöngy-visszanyerési probléma megköveteli az n gyöngyből álló gyöngyök visszanyerését , amelyek mindegyike fekete vagy fehér, részleges információ mellett. Nevezzük a k -konfigurációt a gyöngyökben a k pozíció részhalmazának a gyöngyökben. Két konfiguráció izomorf, ha az egyik a másikból a gyöngyök forgatásával nyerhető. A helyreállítási folyamat k lépésében részinformációk állnak rendelkezésre, amelyek minden k -konfigurációhoz tartalmazzák a vele izomorf k -konfigurációk számát , amelyek csak fekete gyöngyöket tartalmaznak. A probléma az, hogy meghatározzuk egy adott n -hez szükséges lépések számát (a legrosszabb esetben), hogy pontosan visszaállítsuk a fekete-fehér gyöngyök váltakozását.
Megoldás
Alon , Karo, Krasikov és Roditti megmutatták, hogy a lépések elegendőek egy zseniálisan továbbfejlesztett befogadási-kizárási elv használatával .
Radcliffe és Scott kimutatta, hogy n prím esetén 3 lépés elegendő, tetszőleges n esetén pedig n prímtényezőinek számának 9-szerese is elegendő .
Luke Pebody megmutatta, hogy bármely n esetén 6 lépés elegendő.
Lásd még
- Karkötő és gyöngyök
- Moro gyöngyszámláló funkció
- Nyaklánc vágási probléma
Jegyzetek
Irodalom
- Alon N., Caro Y., Krasikov I., Roditty Y. Kombinatorikus rekonstrukciós problémák // J. Combin. Elmélet Ser. b . - 1989. - T. 47 . – S. 153–161 . - doi : 10.1016/0095-8956(89)90016-6 .
- RadcliffeA. J., Scott AD Reconstructing subsets of Z n // J. Combin. Elmélet Ser. A. _ - 1998. - T. 83 . – S. 169–187 . - doi : 10.1006/jcta.1998.2870 .
- Luke Pebody. Véges Abel-csoportok rekonstruálhatósága // Combin. Valószínűleg. Comput. . - 2004. - T. 13 . – S. 867–892 . - doi : 10.1017/S0963548303005807 .
- Luke Pebody. Reconstructing Odd Necklaces // Combin. Valószínűleg. Számítógép.. - 2007. - T. 16 . – S. 503–514 . - doi : 10.1017/S0963548306007875 .