Feladat: Pontversenyen kívüli P.127 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Balogh Z. ,  Füredi Z. ,  Hermann P. ,  Kollár István ,  Reviczky J. ,  Szász Gy. 
Füzet: 1973/szeptember, 19 - 20. oldal  PDF  |  MathML 
Témakör(ök): Egyéb feladványok, Kombinatorikai leszámolási problémák, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1972/január: Pontversenyen kívüli P.127

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A kétféle betűből képezhető, n elemből álló, egymástól különböző betűsorok száma 2n, ezek az A és O elemek ismétléses n-ed osztályú variációi. A nyelvben szóként használt, n betűből álló betűsorok számát jelöljük N-nel. (Természetesen csak az n3 értékekről lehet szó.)
Tekintsük azokat a betűsorokat, amelyek a nyelv egy n-betűs szavából úgy állnak elő, hogy ennek egy betűjét megváltoztatjuk, és nevezzük ezek halmazát ‐ magával a szóval együtt ‐ a szó bokrának. Minden egyes betűben egyféle változtatás lehetséges, az A-nak O-ra cserélése vagy fordítva, így minden egyes szó bokra (n+1) betűsorból áll. ‐ A nyelv szavaiból képzett bokrok száma ugyancsak N.
Minden egyes betűsor legföljebb egy bokorba tartozik bele. Ha ugyanis a β betűsor az s1 és s2 szavak bokrába is beletartozna ‐ de ő maga nem szó ‐, akkor s1 és s2 csak két helyen (két betűben) különböznének egymástól ‐ az első változtatás s1-ből β-t állítaná elő, a második pedig β-ból s2-t ‐, ezt pedig a nyelv leírása kizárta. Így a bokrokba besorolt betűsorok száma pontosan N(n+1), s mivel ez nem nagyobb a betűsorok 2n számánál, azért a bokrok és velük együtt a nyelv szavainak számára valóban fennáll:

N2nn+1.

 
Megjegyzések. Eredményünkben egyenlőség csak n=1, 3, 7, 15, ..., 2k-1, ... mellett jöhet szóba, de az már jóval nehezebb kérdés, hogy sikerül-e pl. 7 betűvel a maximális 16 szót összeállítani.
2. Háromféle ,,betűt'', az 1, x, 2 jeleket megengedve a bokroknak legföljebb 1 hibapontos totószelvény-kitöltsek felelnek meg, de ott minden egyes helyen 2-féle torzítás jön szóba.