Feladat: B.4234 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Ágoston Péter ,  Ágoston Tamás ,  Csuka Róbert ,  Damásdi Gábor ,  Éles András ,  Énekes Péter ,  Janzer Olivér ,  Karkus Zsuzsa ,  Mester Márton ,  Mészáros András ,  Somogyi Ákos ,  Weisz Ágoston ,  Zelena Réka 
Füzet: 2010/október, 412 - 413. oldal  PDF file
Témakör(ök): Feladat, Gráfelmélet
Hivatkozás(ok):Feladatok: 2010/január: B.4234

Egy k elemű ABC-ből képezzük az összes olyan n hosszúságú szót, amely csupa különböző betűből áll. Két ilyen szót összekötünk egy éllel, ha csak egyetlenegy helyen különböznek. Az így kapott gráfban mekkora az átmérő?

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.

Megoldás. A feladatnak nyilván csak nk esetén van értelme. Ha n=k, akkor bármely két szó legalább két helyen különbözik, tehát nincs él a gráfban; ekkor a gráf átmérője végtelen. Legyen a továbbiakban n<k.
Megmutatjuk, hogy a gráf átmérője (az érdektelen n=1 esettől eltekintve) [3n2]. Tekintsük először azt az esetet, amikor n páros. Vegyünk egy tetszőleges A1A2A3...An szót. Vizsgáljuk meg, hogy ez milyen távol van az A2A1A4A3...AnAn-1 szótól. Nézzük meg, hány élen kell végigmenni, hogy az A1A2 részből A2A1 legyen. Nevezzük lépésnek azt, amikor egy élen áthaladunk. Mivel különböző betűkből állnak a szavak, kell lennie egy olyan lépésnek, ahol A1 vagy A2 megváltozik egy A1-től és A2-től különböző betűre. Kell még két lépés, amikor az első helyre A2, és amikor a másodikra A1 kerül. Tehát legalább három lépésre van szükség. A különböző helyeken lévő változások egymást nem befolyásolják, ezért n23 lépést kell (legalább) elvégezni ahhoz, hogy A1A2A3...An-ből A2A1A4A3...AnAn-1-be érjünk.
Ha n páratlan, akkor az A1A2A3...An és az A2A1A4A3...An-1An-2An+1 szó távolsága (ahol An+1A1,A2,A3,...,An) az előző esethez hasonlóan

3n-12+1=[3n2],
mivel az n-12 darab kételemű szakasz egyenként három lépésben változtatható meg, az egyelemű pedig nyilván egyetlen lépésben.
Eddig igazoltuk, hogy a gráfban léteznek egymástól [3n2] távolságra lévő pontok. Be kell még látnunk, hogy minden csúcs elérhető legfeljebb n23 lépéssel a többi csúcs bármelyikéből. Tekintsünk ehhez két tetszőleges csúcsot, A=A1A2A3...An-et és B=B1B2B3...Bn-et. Ekkor A-ból B-be eljuthatunk a következő lépések ismételt alkalmazásával: Lépjünk egy olyan csúcsra, hogy egy A-beli betű a megfelelő helyen álló B-beli betűre változzon ‐ nevezzük az ilyen lépést termékenynek. Csak akkor nem tudunk termékeny lépést tenni, ha olyan csúcson állunk, amely ugyanazokból a betűkből áll mint B, de más sorrendben; emiatt a B-től való távolsága még legalább 2. Ebben az esetben úgy lépjünk, hogy valamelyik ‐ a B-ben elfoglalt helyétől eltérő helyen álló ‐ Ai betű helyére egy olyan V betűt írunk, amely nem fordul elő B-ben. Az eddig megfelelőre változtatott betűket ezzel nem rontjuk el; nevezzük az ilyen típusú lépést terméketlennek. A következő lépésben Ai-t a (B-ben elfoglalt) helyére rakhatjuk. Mivel ekkor a (B-ben nem található) V benne marad a szóban, egy további betűt még biztosan a helyére tudunk rakni. Ezzel elérjük, hogy minden terméketlen lépést követni fog (legalább) két termékeny. Mivel a termékeny lépések száma n, a terméketleneké legfeljebb n2 lehet, tehát összesen legfeljebb n+n2=3n2 lépés elegendő.
 Damásdi Gábor megoldása