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 (a_i₁,...,a_{i_k}) alakú sorozatok, ahol 0 $\le$ k $\le$ n é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 w₁,w₂,... 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 w₁,w₂,... szavakban előforduló betűk száma. A Tételt k szerinti indukcióval bizonyítjuk. Ha k=0, akkor w₁,w₂,... mindegyike az üres szó, ezért az állítás triviális. Tegyük tehát fel, hogy k $\ge$ 1, é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 c_n=(1,2,...,n), azaz c_n 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=(x₁,...,x_|w|) szóra, mert az x₁ betű biztosan szerepel c_k|w| első k betűje között, az x₂ betű biztosan szerepel c_k|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(w₁),f(w₂),... számsorozat nem korlátos, azaz az f(w_i) értékek között bármilyen nagy értékek előfordulnak.

Ekkor az i₁,i₂,... sorozatot a következő rekurzióval definiáljuk. Legyen i₁=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(w₁),f(w₂),... 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(w₁),f(w₂),... számsorozat korlátos, azaz az f(w_i) értékek között csak véges sok féle érték szerepel.

Ekkor az f(w_i) é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=(x₁,...,x_s) 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 h₁-edik betű. Az ezután következő betűk között keressük az első 2-est, legyen ez a h₂-edik betű; és így tovább, az utolsó lépésben az x_{h_m-1+1},...,x_s betűk között keressük meg az első m-est, ami x_m. 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 h₁=1, akkor p₀(w) az üres szó.)

Ekkor

w=p₁(w)+p₂(w)+...+p_m+1(w),

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

A definícióban szereplő h₁,...,h_m indexek valóban léteznek, mert $c_m\prec m$ . A definíció szerint minden 1 $\le$ j $\le$ m-re a p_j(w) szóban nem szerepel a j betű, és p_j+1(w) első betűje j. Végül, a p_m+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:

w_{j_0,1}=p₁(w_{j_0,1})+p₂(w_{j_0,1})+...+p_m+1(w_{j_0,1}),

w_{j_0,2}=p₁(w_{j_0,2})+p₂(w_{j_0,2})+...+p_m+1(w_{j_0,2}),

w_{j_0,3}=p₁(w_{j_0,3})+p₂(w_{j_0,3})+...+p_m+1(w_{j_0,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 i₁,i₂,... 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

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ő.

Már regisztráltál?
Új vendég vagy?