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 esetén van értelme. Ha , 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 . Megmutatjuk, hogy a gráf átmérője (az érdektelen esettől eltekintve) . Tekintsük először azt az esetet, amikor páros. Vegyünk egy tetszőleges szót. Vizsgáljuk meg, hogy ez milyen távol van az szótól. Nézzük meg, hány élen kell végigmenni, hogy az részből 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 vagy megváltozik egy -től és -től különböző betűre. Kell még két lépés, amikor az első helyre , és amikor a másodikra 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 lépést kell (legalább) elvégezni ahhoz, hogy -ből -be érjünk. Ha páratlan, akkor az és az szó távolsága (ahol ) az előző esethez hasonlóan mivel az 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 távolságra lévő pontok. Be kell még látnunk, hogy minden csúcs elérhető legfeljebb lépéssel a többi csúcs bármelyikéből. Tekintsünk ehhez két tetszőleges csúcsot, -et és -et. Ekkor -ból -be eljuthatunk a következő lépések ismételt alkalmazásával: Lépjünk egy olyan csúcsra, hogy egy -beli betű a megfelelő helyen álló -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 , de más sorrendben; emiatt a -től való távolsága még legalább 2. Ebben az esetben úgy lépjünk, hogy valamelyik ‐ a -ben elfoglalt helyétől eltérő helyen álló ‐ betű helyére egy olyan betűt írunk, amely nem fordul elő -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 -t a (-ben elfoglalt) helyére rakhatjuk. Mivel ekkor a (-ben nem található) 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 , a terméketleneké legfeljebb lehet, tehát összesen legfeljebb lépés elegendő. Damásdi Gábor megoldása |