Feladat:	2015. évi Kürschák matematikaverseny 3. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Fleiner Tamás
Füzet:	2016/február, 70 - 71. oldal		PDF  |  MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Számsorozatok, Részhalmazok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2016/február: 2015. évi Kürschák matematikaverseny 3. feladata

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.   I. megoldás. A feladatban megfogalmazottnál erősebb állítást bizonyítunk. Legyen $A$ a $Q$-nak egy tetszőleges részhalmaza, és legyen $B=Q\setminus A$. Ekkor az olyan $\left(a\mathrm{,}b\right)$ párok száma, amelyekben $a\in A$, $b\in B$, továbbá az $a$ és $b$ sorozatok csak egyetlen tagban térnek el egymástól, legalább $\underset{}{\overset{}{\text{min}}}\left(|A|\mathrm{,}|B|\right)$. Világos, hogy a fenti állítás $|A|=2^{n-1}$ esetén éppen a kitűzött feladat. A fent megfogalmazott állítást $n$ szerinti teljes indukcióval igazoljuk. Ha $n=1$, akkor az állítás nyilvánvalóan igaz. Tegyük fel, hogy az állítás $n$-re igaz, és lássuk be $\left(n+1\right)$-re. Legyenek tehát az $A$ halmaz elemei bizonyos $n+1$ tagú $0/1$-sorozatok, $B$ pedig álljon a többi $n+1$ tagú $0/1$-sorozatból. Feltehetjük, hogy $|A|\le |B|$, mert ellenkező esetben felcserélhetjük $A$ és $B$ szerepét. Legyen az $A$-beli, $0$-ra végződő sorozatok száma $x$, az $1$-re végződőké $y$. Ekkor tehát $x+y=|A|\le 2^n$. Feltehetjük, hogy $x\ge y$. Ekkor $y\le 2^{n-1}$. A feladatban leszámlálandó $\left(a\mathrm{,}b\right)$ párok négyfélék lehetnek aszerint, hogy mi $a$, illetve $b$ utolsó tagja. 1. Olyan párokból, ahol ez a két utolsó tag $1$, az indukciós feltevés szerint legalább $\underset{}{\overset{}{\text{min}}}\left(y\mathrm{,}{2}^n-y\right)=y$ darab van. 2. Olyanokból, ahol ez a két utolsó tag $0$, az indukciós feltevés szerint legalább $\underset{}{\overset{}{\text{min}}}\left(x\mathrm{,}{2}^n-x\right)\ge y$ darab van. 3. Olyanokból, ahol $a$ utolsó tagja $0$, $b$-é pedig $1$, legalább $x-y$ darab van, hiszen az $x$ darab $A$-beli, $0$-ra végződő sorozat között legfeljebb $y$ olyan lehet, amelynek utolsó tagját $1$-re változtatva ismét $A$-beli sorozatot kapunk. 4. A negyedik fajta párból legalább $0$ darab van. A vizsgált párok száma tehát legalább $y+y+\left(x-y\right)+0=x+y=|A|$. Ezzel az indukciós lépést igazoltuk, a fent megfogalmazott állítás bizonyítását befejeztük.  $\square$   II. megoldás. Az I. megoldásban igazolt állításnál egy erősebbet bizonyítunk az alábbiakban. Azt mondjuk, hogy a $Q$-beli $q_1\mathrm{,}{q}_2\mathrm{,}\text{...}$ sorozatok monoton sort alkotnak, ha minden értelmes $i$-re $q_i$ és $q_{i+1}$ egyetlen tagban tér el egymástól, továbbá $q_i$ és $q_{i+1}$ eltérése korábban van, mint a $q_{i+1}$ és $q_{i+2}$ eltérése. Világos például, hogy egy monoton sor hossza legfeljebb $n+1$ lehet, de az is könnyen látható, hogy tetszőleges $x\mathrm{,}y\in Q$ sorozatokra pontosan egy olyan monoton sor létezik, amely $x$-szel kezdődik és $y$-ra végződik. Legyen most $A\subseteq Q$, $B=Q\setminus A$, és tegyük fel, hogy $|A|\le 2^{n-1}$. Az iménti megfigyelésünk szerint az olyan monoton sorok száma, amelyek $A$-beli sorozatból indulnak és $B$-beliben érnek véget, pontosan $|A|\cdot |B|$. Világos, hogy minden ilyen $q_1\mathrm{,}{q}_2\mathrm{,}\text{...}$ monoton sorhoz van legalább egy olyan $i$ index, amelyre $q_i\in A$ és $q_{i+1}\in B$. Most tegyük fel, hogy az $a\in A$ és $b\in B$ sorozatok pontosan egy (mondjuk az $i$-edik) tagban térnek el. Az olyan monoton sorok száma, amelyek az $a$ és a $b$ sorozatot is tartalmazzák, pontosan $2^{n-1}$, hiszen minden ilyen monoton sort egyértelműen meghatároznak azok a helyek, amelyeken található tagokban a sorban egymást követő sorozatok eltérnek. Az $i$-dik hely bizonyosan ilyen eltérés (az egymást követő $a$ és $b$ sorozatok miatt), a fennmaradó $n-1$ hely mindegyikéről pedig egymástól függetlenül eldönthetjük, hogy legyen-e a monoton sorban két egymást követő sorozat, amelyek ott térnek el, vagy ne. Ezek szerint a feladatban leírt $\left(a\mathrm{,}b\right)$ párok számának $2^{n-1}$-szerese nem lehet kisebb $|A|\cdot |B|$-nél, azaz az $A$-ból $B$-be vezető monoton sorok számánál. Tehát a keresett $\left(a\mathrm{,}b\right)$ párok száma legalább $\begin{array}{c}{\displaystyle |A|\cdot \frac{|B|}{2^{n-1}}\ge |A|\cdot \frac{2^{n-1}}{2^{n-1}}=|A|\mathrm{.}}\end{array}$ A bizonyítandó állítás innen közvetlenül adódik az $|A|=2^{n-1}$ feltételből.  $\square$   Megjegyzések. 1. A II. megoldás gondolatmenete Molnár-Sáska Zoltán megoldásából származik. Lényegében ugyanez az érvelés rekonstruálható Matolcsi Dávid dolgozatából is. 2. Ahogy a II. megoldásban, tegyük fel ismét, hogy $A\subseteq Q$, $B=Q\setminus A$, valamint $|A|\le 2^{n-1}$. A II. megoldásból könnyen levezethető, hogy az olyan $\left(a\mathrm{,}b\right)$ párok száma, amelyek csak egy tagban térnek el és $a\in A$, illetve $b\in B$, pontosan akkor egyenlő $|A|$-val, ha $A=\varnothing$ vagy ha $|A|=2^{n-1}$ és $A$ mindazon sorozatok halmaza, amelyeknek egy konkrét tagja rögzített, a többit pedig az összes lehetséges módon választjuk. 3. A kitűzött feladat lényegében ekvivalens azzal az ismert ténnyel, hogy a hiperkocka ún. Cheeger-száma $1$-gyel egyenlő.