A B. 4234. feladat (2010. január)

B. 4234. Egy \(\displaystyle k\) elemű ABC-ből képezzük az összes olyan \(\displaystyle 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ő?

CIIM, Kolumbia, 2009

(4 pont)

A beküldési határidő 2010. február 10-én LEJÁRT.

Megoldás. Ha \(\displaystyle k<n\), akkor egyáltalán nem képezhető ilyen szó, ha pedig \(\displaystyle k=n\), akkor a gráfnak egyáltalán nincs éle, tehát csak a \(\displaystyle k>n\) esettel foglalkozunk. Ha \(\displaystyle n=1\), akkor a gráf teljes, átmérője 1. Ha \(\displaystyle a,b,c,d\) különböző betűket jelölnek, akkor az

\(\displaystyle ab-ad-cd,\qquad ab-cb-ca,\qquad ab-ac-bc,\qquad ab-ac-bc-ba\)

utak mutatják, hogy \(\displaystyle n=2\) esetén \(\displaystyle k\) értékétől függetlenül a gráf átmérője 3, hiszen az \(\displaystyle ab\) szóból a \(\displaystyle ba\)-ba nem lehet 3-nál kevesebb lépéssel eljutni. Megmutatjuk, hogy \(\displaystyle 1\le n<k\) esetén a gráf átmérője \(\displaystyle k\) értékétől függetlenül \(\displaystyle d_n=[3n/2]\).

Az alsó becslés igazolásához tegyük fel, hogy \(\displaystyle a_1,\ldots,a_n, a_{n+1}\) különböző betűk a \(\displaystyle \Sigma\) ABC-ben. Legyen először \(\displaystyle n=2m\). Ha az \(\displaystyle S_1=a_1a_2\ldots a_{2m}\) szót egy út összeköti az \(\displaystyle S_2=a_2a_1a_4a_3\ldots a_{2m}a_{2m-1}\) szóval, akkor annak legalább \(\displaystyle 3m\) éle van, ugyanis minden \(\displaystyle 1\le i\le m\) esetén az \(\displaystyle a_{2i}a_{2i-1}\) blokk megfordításához legalább 3 lépés szükséges. Ha pedig \(\displaystyle n=2m+1\), akkor az \(\displaystyle S_1a_n\) szó és az \(\displaystyle S_2a_{n+1}\) szó távolsága legalább \(\displaystyle 3m+1\). (Itt az \(\displaystyle Sx\) jelölés azt jelenti, hogy az \(\displaystyle n-1\) hosszúságú \(\displaystyle S\) szó végére odaírtuk az \(\displaystyle x\) betűt.) Ezzel beláttuk, hogy \(\displaystyle d_n\ge [3n/2]\).

A \(\displaystyle d_n\le [3n/2]\) állítást \(\displaystyle n\) szerinti teljes indukcióval igazoljuk. Azt már láttuk, hogy \(\displaystyle n=1,2\) esetén ez igaz. Tegyük fel tehát, hogy legfeljebb \(\displaystyle n-1\) hosszúságú szavakra, ahol \(\displaystyle n\ge 2\), az egyenlőtlenséget már igazoltuk, és lássuk be, hogy akkor \(\displaystyle n\) hosszúságú szavakra is igaz.

Ehhez tegyük fel először, hogy az \(\displaystyle S_1=a_1a_2\ldots a_{n}\) és \(\displaystyle S_2=b_1b_2\ldots b_{n}\) szavak nem azonos betűkből állnak, ekkor van egy olyan \(\displaystyle x\) betű, amely \(\displaystyle S_1\)-ben szerepel, de \(\displaystyle S_2\)-ben nem. Az egyszerőség kedvéért feltehetjük, hogy \(\displaystyle x=a_n\). Ekkor az indukciós feltevés szerint a \(\displaystyle \Sigma\setminus\{ x\}\) ABC-hez tartozó \(\displaystyle (k-1,n-1)\) paraméterő gráfban létezik egy olyan \(\displaystyle T_0,T_1,\ldots,T_d\) út, amelyre \(\displaystyle T_0=a_1a_2\ldots a_{n-1}\), \(\displaystyle T_d=b_1b_2\ldots b_{n-1}\) és \(\displaystyle d\le d_{n-1}\le [3(n-1)/2]\). Ekkor az eredeti gráfban a \(\displaystyle d+1\le [3(n-1)/2]+1\le [3n/2]\) hosszú \(\displaystyle T_0x,T_1x,\ldots,T_dx,T_db_n\) út összeköti az \(\displaystyle S_1\) és \(\displaystyle S_2\) szavakat.

Most vizsgáljuk meg azt az esetet is, amikor az \(\displaystyle S_1\) és \(\displaystyle S_2\) szavak ugyanazokból a betűkből állnak, vagyis \(\displaystyle \{ a_1,\ldots,a_n\}= \{ b_1,\ldots,b_n\}\), és a \(\displaystyle \Sigma\) ABC-ben van olyan \(\displaystyle x\) betű, amely nem szerepel ezek között. Tekintsük az \(\displaystyle \{1,2,\ldots,n\}\) számoknak a legkisebb olyan nem üres \(\displaystyle \{ i_1,\ldots,i_r\}\) részhalmazát, amelyre \(\displaystyle \{ a_{i_1},\ldots,a_{i_r}\}=\{ b_{i_1},\ldots,b_{i_r}\}\) teljesül, nyilván \(\displaystyle r\le n\). Ha \(\displaystyle r<n\), akkor használjuk fel az indukciós feltevést. Az \(\displaystyle a_{i_1},\ldots,a_{i_r}, x\) betűket felhasználva az \(\displaystyle S_1\) szóban az \(\displaystyle a_{i_1},\ldots,a_{i_r}\) betűket legfeljebb \(\displaystyle d_r\le [3r/2]\) lépésben kicserélhetjük a \(\displaystyle b_{i_1},\ldots,b_{i_r}\) betűkre, majd hasonlóképpen a maradék \(\displaystyle n-r\) betűt legfeljebb \(\displaystyle d_{n-r}\le [3(n-r)/2]\) lépésben kicserélve eljutunk az \(\displaystyle S_2\) szóhoz, vagyis az \(\displaystyle S_1\), \(\displaystyle S_2\) szavak távolsága a gráfban nem nagyobb, mint

\(\displaystyle d_r+d_{n-r}\le [3r/2]+[3(n-r)/2]\le [3n/2].\)

Végezetül vizsgáljuk meg az \(\displaystyle r=n\) esetet. Az egyszerőség kedvéért tegyük fel, hogy \(\displaystyle b_1=a_n, b_n=a_{n-1},b_{n-1}=a_{n-2},\ldots, b_2=a_1\). Cseréljük ki először az \(\displaystyle a_n\) betűt \(\displaystyle x\)-re. Ezután \(\displaystyle a_1\) helyére már beírhatjuk \(\displaystyle b_1=a_n\)-et, majd \(\displaystyle a_2\) helyére \(\displaystyle b_2=a_3\)-at, és így tovább, amíg az \(\displaystyle n\)-edik lépés után el nem jutunk a \(\displaystyle b_1b_2\ldots b_{n-1}x\) szóhoz. Végül az \(\displaystyle n+1\)-edik lépésben \(\displaystyle x\)-et \(\displaystyle b_{n}\)-re cserélve megkapjuk az \(\displaystyle S_2\) szót. Vagyis ebben az esetben \(\displaystyle S_1\) és \(\displaystyle S_2\) távolsága nem nagyobb mint, \(\displaystyle n+1\le [3n/2]\). Ezzel az indukciós lépést befejeztük.

Statisztika:

46 dolgozat érkezett.
4 pontot kapott:	Á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.
3 pontot kapott:	Beke Lilla, Kovács 888 Adrienn, Strenner Péter, Szabó 124 Zsolt.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	14 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2010. januári matematika feladatai