Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 541. feladat (2011. szeptember)

A. 541. A H halmaz elemei olyan véges sorozatok, amelyek elemei 1, 2 és 3 közül kerülnek ki, továbbá egyik H-beli sorozat sem részsorozata egyetlen másik H-beli sorozatnak sem. Igazoljuk, hogy H véges. (Az (a_1,\ldots,a_n) sorozat részsorozatai az (ai1,...,aik) alakú sorozatok, ahol 0\lek\len és i_1<\ldots<i_k.)

Javasolta: Pongrácz András (Budapest)

(5 pont)

A beküldési határidő 2011. október 10-én LEJÁRT.


Megoldás. A véges sorozatokat szavaknak is fogjuk hívni, a szavak elemeit betűknek. Megengedjük az üres szót is. Ha u részsorozata az v szónak, akkor ezt u\prec v-vel fogjuk jelölni. A \prec reláció reflexív és tranzitív: minden szó részsorozata önmagának (azaz u\prec u), és ha u\prec v és v\prec w, akkor u\prec w. Két szó egymás után írását a + jellel fogjuk jelölni, pl, (1,2)+(3,4)=(1,2,3,4). A w szó hosszát |w| jelöli.

A következő, általánosabb állítást bizonyítjuk:

Tétel. Tegyük fel, hogy w1,w2,... szavak egy végtelen sorozata, amelyekben összesen csak véges sok féle betű szerepel. Ekkor létezik pozitív egészeknek egy olyan i_1<i_2<\ldots végtelen sorozata, amelyre w_{i_1}\prec
  w_{i_2}\prec w_{i_3}\prec\ldots.

A Tételből a feladat állítása azonal következik. Ha ugyanis a H halmaznak végtelen sok eleme lenne, akkor ezek egy tetszőleges felsorolására almazhatnánk a Tételt.

Legyen k a w1,w2,... szavakban előforduló betűk száma. A Tételt k szerinti indukcióval bizonyítjuk. Ha k=0, akkor w1,w2,... mindegyike az üres szó, ezért az állítás triviális. Tegyük tehát fel, hogy k\ge1, és kevesebb féle betű esetén az állítás igaz. A betűk legyenek 1,2,...,k. A betűket modulo k értelmezzük, tehát például k+1=1.

Tetszőleges n nemnegatív egészre legyen cn=(1,2,...,n), azaz cn jelenti a k szerint periodikus 1,2,...,k,1,2,... végtelen sorozatból az első n elemet. Vegyük észre, hogy w\prec
c_{k|w|} bármely w=(x1,...,x|w|) szóra, mert az x1 betű biztosan szerepel ck|w| első k betűje között, az x2 betű biztosan szerepel ck|w| második k betűje között és így tovább.

Tetszőleges w szóra legyen f(w) a legnagyobb olyan egész, amire c_{f(w)}\prec w; nyilván f(w)\le|w|.

1. eset: az f(w1),f(w2),... számsorozat nem korlátos, azaz az f(wi) értékek között bármilyen nagy értékek előfordulnak.

Ekkor az i1,i2,... sorozatot a következő rekurzióval definiáljuk. Legyen i1=1. Ha i_\ell-et már definiáltuk, akkor legyen i_{\ell+1} az első olyan index, amire i_{\ell+1}>i_\ell és f(w_{i_{\ell+1}})\ge k|w_{i_\ell}|. Mivel az f(w1),f(w2),... számsorozat nem korlátos, ilyen index létezik. Továbbá w_{i_\ell}
\prec c_{k|w_{i_\ell}|} \prec c_{f(w_{i_{\ell+1}})} \prec
w_{i_{\ell+1}}. Az ilyen módon konstruált sorozatban tehát i_1<i_2<\ldots és w_{i_1}\prec w_{i_2}\prec\ldots is teljesül.

2. eset: az f(w1),f(w2),... számsorozat korlátos, azaz az f(wi) értékek között csak véges sok féle érték szerepel.

Ekkor az f(wi) értékek között van olyan, ami végtelen sokszor előfordul; legyen m egy ilyen érték. Ekkor létezik egy olyan j_{0,1}<j_{0,2}<j_{0,3}<\ldots indexsorozat, amire f(w_{j_{0,1}})=f(w_{j_{0,2}})=\ldots=m.

Tekintsünk most egy tetszőleges w=(x1,...,xs) szót, amire f(w)=m. Ezt a szót m+1 darabra vágjuk a következőképpen. Keressük meg a szóban az első 1-est, legyen ez a h1-edik betű. Az ezután következő betűk között keressük az első 2-est, legyen ez a h2-edik betű; és így tovább, az utolsó lépésben az xhm-1+1,...,xs betűk között keressük meg az első m-est, ami xm. Ezután legyen


p_1(w) = (x_1,\dots,x_{h_1-1}), \quad
p_2(w) = (x_{h_1},\dots,x_{h_2-1}), \quad
\ldots, \quad
p_{m+1}(w) = (x_{h_m},\dots,x_s).

(Ha h1=1, akkor p0(w) az üres szó.)

Ekkor

w=p1(w)+p2(w)+...+pm+1(w),

és valóban m+1 darabra vágtuk a w szót.

A definícióban szereplő h1,...,hm indexek valóban léteznek, mert c_m\prec m. A definíció szerint minden 1\lej\lem-re a pj(w) szóban nem szerepel a j betű, és pj+1(w) első betűje j. Végül, a pm+1(w) szóban nem szerepelhet az m+1 betű, ugyanis ellenkező esetben c_{m+1}\prec w is teljesülne, ami ellentmond annak, hogy f(w)=m.

Most vágjuk m+1 darabra a fentiek szerint a w_{j_{0,1}},w_{j_{0,2}},\ldots sorozat mindegyik elemét:

wj0,1=p1(wj0,1)+p2(wj0,1)+...+pm+1(wj0,1),

wj0,2=p1(wj0,2)+p2(wj0,2)+...+pm+1(wj0,2),

wj0,3=p1(wj0,3)+p2(wj0,3)+...+pm+1(wj0,3),


\ldots

A p_1(w_{j_{0,1}}),p_1(w_{j_{0,2}}),p_1(w_{j_{0,3}}),\ldots szavak egyikében sem szerepel az 1 betű. Ezért erre a sorozatra alkalmazhatjuk az indukciós feltevést: a j_{0,1}<j_{0,2}<\ldots indexsorozatnak van egy olyan j_{1,1}<j_{1,2}<\ldots végtelen részsorozata, amire p_1(w_{j_{1,1}})\prec p_1(w_{j_{1,2}})\prec\ldots.

Ezután tekintsük a p_2(w_{j_{1,1}}),p_2(w_{j_{1,2}}),\ldots sorozatot. Ezek a szavak nem tartalmazzák a 2 betűt, tehát ismét alkalmazhatjuk az indukciós feltevést; az j_{1,1}<j_{1,2}<\ldots sorozatnak van egy olyan j_{2,1}<j_{2,2}<\ldots végtelen részsorozata, amire p_2(w_{j_{21}})\prec p_2(w_{j_{22}})\prec\ldots.

Ezt az eljárást összesen (m+1)-szer megismételve, egy olyan i_1=j_{m+1,1}<i_2=j_{m+1,2}<\ldots végtelen indexsorozatot kapunk, amellyel minden egyes \ell pozitív egészre p_1(w_{i_\ell}) \prec
p_1(w_{i_{\ell+1}}), p_2(w_{i_\ell}) \prec p_2(w_{i_{\ell+1}}), ..., p_m(w_{i_\ell}) \prec p_m(w_{i_{\ell+1}}) és p_{m+1}(w_{i_\ell}) \prec p_{m+1}(w_{i_{\ell+1}}). Ezekből viszont következik, hogy


w_{i_\ell} =
p_1(w_{i_\ell}) + \ldots + p_{m+1}(w_{i_\ell}) \prec
p_1(w_{i_{\ell+1}}) + \ldots + p_{m+1}(w_{i_{\ell+1}}) =
w_{i_{\ell+1}}.

Ezzel a 2. esetben is megkonstruáltuk a kívánt i1,i2,... sorozatot.


Statisztika:

9 dolgozat érkezett.
5 pontot kapott:Ágoston Tamás, Janzer Olivér, Mester Márton, Omer Cerrahoglu, Strenner Péter.
0 pontot kapott:4 versenyző.

A KöMaL 2011. szeptemberi matematika feladatai