Problem B. 4234. (January 2010)

B. 4234. All possible strings of \(\displaystyle n\) different letters are formed out of a \(\displaystyle k\)-element alphabet. Two such strings are connected with an edge if they only differ in a single position. What is the diameter of the resulting graph?

CIIM, Columbia, 2009

(4 pont)

Deadline expired on February 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

46 students sent a solution.
4 points:	Á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 points:	Beke Lilla, Kovács 888 Adrienn, Strenner Péter, Szabó 124 Zsolt.
2 points:	1 student.
1 point:	12 students.
0 point:	14 students.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, January 2010