Matematické Fórum

Pro slovo délky n můžeš prostě postupně testovat, jesti je dělitelné nějakým číslem z rozsahu 2 až n - 1.

Například testování, jestli slovo „aaaaa“ má sudý počet znaků, se dá udělat tak, že ho budeš přepisovat dvěma znaky „bb“ – dostaneš tak na pásce postupně slova „bbaaa“, „bbbba“, a pak tam nenacpeš dvě b za sebe bez toho, aniž bys vylezl mimo rozsah původního slova – tedy počet a v tom slově není sudý.

Obecně bych si někde stranou na pásce vyrobil dělitele v jedničkové soustavě – na začátku by to bylo slovo třeba „bb“ a pak bych se pokoušel tohohle dělitele napasovat na to původní slovo. Když se mi to nepovede, tak dolezu k tomu děliteli, na konec mu přidám ještě jeden znak, a celé to opakuju, dokud dělitel není delší než to původní slovo.

Tzn. na pásce bych mohl mít například „SaaaaaYbbK“ (S, Y, K jsou pomocné symboly, aaaaa je původní slovo, bb je dělitel), hlava je na S. Dolezu doprava na první b, přepíšu ho na Z, mám tam „SaaaaaYZbK“, dolezu doleva na první a, přepíšu ho na b, mám „SbaaaaYZbK“, jedu doprava, přepíšu b na Z, doleva, dostanu „SbbaaaYZZK“. Pojedu doprava, tam už ale před K žádné b nenajdu – tak se vrátím, přepíšu všechny Z na b a opakuju.

Nakonec zjistím, že bb tam nepasuje, tak přepíšu všechno mezi S a Y zase na áčka, po Y přepíšu všechno na b, K taky přepíšu na b a přidám tam zase K na konec.

Přibližně tak.