Cím:	A 2015. évi Kürschák József Matematikai Tanulóverseny feladatainak megoldása
Szerző(k):	Fleiner Tamás
Füzet:	2016/február, 68 - 71. oldal	PDF  |  MathML
Témakör(ök):	Matematika, Kürschák József (korábban Eötvös Loránd), Szakmai cikkek

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.   1. Vívásban az nyer egy asszót, aki hamarabb ér el $15$ találatot. Tegyük fel, hogy $A$ és $B$ küzdelmében (az asszón belül bármikor) $p$ valószínűséggel $A$, $q=1-p$ valószínűséggel pedig $B$ szerzi meg a következő találatot. (Ketten egyszerre sosem érnek el találatot.) Tegyük fel, hogy egy asszóban $A$ már $14-k$, $B$ pedig $14-\ell$ találatot szerzett (ahol $k$ és $\ell$ nemnegatív, $15$-nél kisebb egészek), és $A$ újabb találatot ér el. Mennyivel növekedett ezáltal annak a valószínűsége, hogy $A$ nyeri végül az asszót?   Megoldás. Jelölje $P_{k\mathrm{,}\ell }$ az $A$ vívó győzelmének valószínűségét a feladatban leírt állásnál, $p_{k\mathrm{,}\ell }$ pedig a kérdezett növekményt. A teljes valószínűség tétele miatt $P_{k\mathrm{,}\ell }=p\cdot P_{k-\mathrm{1,}\ell }+q\cdot P_{k\mathrm{,}\ell -1}$, amit átrendezve $p_{k\mathrm{,}\ell }=P_{k-\mathrm{1,}\ell }-P_{k\mathrm{,}\ell }=q\left(P_{k-\mathrm{1,}\ell }-P_{k\mathrm{,}\ell -1}\right)$ adódik. Feltételezhetjük, hogy $A$ és $B$ $29$ találatig vívják az asszót, hisz ez a győztes kilétét nem változtatja meg. Így $P_{k-\mathrm{1,}\ell }$ annak a valószínűsége, hogy a hátralévő $k+\ell$ találat közül $A$ legalább $k$ találatot szerez, míg $P_{k\mathrm{,}\ell -1}$ annak a valószínűsége, hogy a hátralévő $k+\ell$ találat közül $A$ legalább $k+1$ találatot szerez. Ezért a $p_{k\mathrm{,}\ell }=P_{k-\mathrm{1,}\ell }-P_{k\mathrm{,}\ell -1}$ különbség annak a valószínűsége, hogy $A$ a hátralevő $k+\ell$ lehetőségből pontosan $k$ találatot szerez, azaz $p_{k\mathrm{,}\ell }=\left(\genfrac{}{}{0ex}{}{k+\ell }{k}\right)p^k{q}^{\ell +1}$.  $\square$   2. A $D$ pont az $ABC$ háromszög $AB$ oldalán, az $I$ pont pedig az $ACB$ szög felezőjének a háromszög belsejébe eső szakaszán helyezkedik el. Az $AI$ és a $CI$ egyenesek az $ACD$ kört másodszor rendre a $P$ és $Q$ pontokban metszik. Hasonlóan, a $BI$ és a $CI$ egyenesek a $BCD$ kört másodszor rendre az $R$ és $S$ pontokban metszik. Mutassuk meg, hogy ha $P\ne Q$ és $R\ne S$, akkor az $AB$, $PQ$ és $RS$ egyenesek vagy egy ponton mennek át, vagy párhuzamosak egymással.   Megoldás. Legyen $\begin{array}{c}{\displaystyle {\alpha }_1=IAC\sphericalangle \mathrm{,}{\alpha }_2=BAI\sphericalangle \mathrm{,}{\beta }_1=IBA\sphericalangle \mathrm{,}{\beta }_2=CBI\sphericalangle \mathrm{,}\gamma =ICB\sphericalangle =ACI\sphericalangle \mathrm{.}}\end{array}$ Írjuk fel a Ceva-tétel trigonometrikus alakját az $ABC$ háromszögre és az $I$ pontra: $\begin{array}{c}{\displaystyle \frac{\text{sin}IAC\sphericalangle }{\text{sin}BAI\sphericalangle }\cdot \frac{\text{sin}IBA\sphericalangle }{\text{sin}CBI\sphericalangle }\cdot \frac{\text{sin}ICB\sphericalangle }{\text{sin}ACI\sphericalangle }=\frac{\text{sin}{\alpha }_1}{\text{sin}{\alpha }_2}\cdot \frac{\text{sin}{\beta }_1}{\text{sin}{\beta }_2}\cdot \frac{\text{sin}\gamma }{\text{sin}\gamma }=1.}\end{array}$     A kerületi szögek tételéből (irányított, azaz modulo ${180}^{\circ }$ szögekkel): ${\displaystyle \begin{array}{cc}\hfill {\displaystyle PQS\sphericalangle }& {\displaystyle =PQC\sphericalangle =PAC\sphericalangle =IAC\sphericalangle ={\alpha }_1\mathrm{,}}\hfill \\ \hfill {\displaystyle DQP\sphericalangle }& {\displaystyle =DAP\sphericalangle =BAI\sphericalangle ={\alpha }_2\mathrm{,}}\hfill \\ \hfill {\displaystyle RSD\sphericalangle }& {\displaystyle =RBD\sphericalangle =IBA\sphericalangle ={\beta }_1\mathrm{,}}\hfill \\ \hfill {\displaystyle QSR\sphericalangle }& {\displaystyle =CSR\sphericalangle =CBR\sphericalangle =CBI\sphericalangle ={\beta }_2\mathrm{,}}\hfill \\ \hfill {\displaystyle ADQ\sphericalangle }& {\displaystyle =ACQ\sphericalangle =ACI\sphericalangle =\gamma \mathrm{,}}\hfill \\ \hfill {\displaystyle SDA\sphericalangle }& {\displaystyle =SDB\sphericalangle =SCB\sphericalangle =ICB\sphericalangle =\gamma \mathrm{.}}\hfill \end{array}}$ Végül alkalmazzuk a Ceva-tétel (trigonometrikus alakjának) megfordítását a  $DSQ$ háromszögre. Mivel $\begin{array}{c}{\displaystyle \frac{\text{sin}ADQ\sphericalangle }{\text{sin}SDA\sphericalangle }\cdot \frac{\text{sin}RSD\sphericalangle }{\text{sin}QSR\sphericalangle }\cdot \frac{\text{sin}PQS\sphericalangle }{\text{sin}DQP\sphericalangle }=\frac{\text{sin}\gamma }{\text{sin}\gamma }\cdot \frac{\text{sin}{\beta }_1}{\text{sin}{\beta }_2}\cdot \frac{\text{sin}{\alpha }_1}{\text{sin}{\alpha }_2}=\mathrm{1,}}\end{array}$ a $DA=AB$, $RS$ és $PQ$ egyenesek egy ponton mennek át, vagy párhuzamosak egymással. $\square$   Megjegyzés. Láttuk, hogy az $ABC$ háromszög hasonló a $QSD$ háromszöghöz. Legyen $I\text{'}$ az $ABC$ háromszög $I$ pontjának megfelelője a $QSD$ háromszögben. A fenti bizonyítás kulcsa az, hogy a $QSD$ háromszögben az $I\text{'}$ izogonális konjugáltja éppen az $AB$, $PQ$ és $RS$ egyenesek közös pontja.   3. Legyen $Q$ az olyan $n$ tagú sorozatok halmaza, amelyeknek minden tagja $0$ vagy $1$. Legyen $A$ a $Q$-nak egy $2^{n-1}$ elemű részhalmaza. Mutassuk meg, hogy legalább $2^{n-1}$ olyan $\left(a\mathrm{,}b\right)$ pár van, amelyre $a\in A$, $b\in Q\setminus A$, továbbá az $a$ és $b$ sorozatok csak egyetlen tagban térnek el egymástól.   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ő.