Az A. 816. feladat (2022. január)

A. 816. Petinek 2022 darab látszólag egyforma mágneses vasúti kocsija van, melyek kétféle típusúak: bizonyosoknak az eleje északi és a hátulja déli, másoknak pedig a hátulja északi és az eleje déli mágneses polaritású (ezek olyan játékkocsik, melyek eleje és hátulja megkülönböztethető). Peti szeretné eldönteni, hogy egyforma számú van-e a kétféle típusú kocsiból. Egy próba során össze lehet illeszteni két vasúti kocsit. Legkevesebb hány próbára van ehhez szükség?

Javasolta: Pálvölgyi Dömötör (Budapest)

(7 pont)

A beküldési határidő 2022. február 10-én LEJÁRT.

Megoldás. Válasz: 2014, vagy általánosan \(\displaystyle 2n\) esetén a megoldás \(\displaystyle 2n-f(n)\), ahol \(\displaystyle f(k)\) a \(\displaystyle k\) szám kettes számrendszerben felírt alakjában az \(\displaystyle 1\)-es jegyek száma. Ezt az általános állítást fogjuk bizonyítani.

Felső becslés: Indukcióval bizonyítjuk, hogy \(\displaystyle 2n-f(n)\)-re mindig adható konstrukció. \(\displaystyle n=1,2\) esetén triviális. Tegyük fel, hogy már az összes \(\displaystyle 2n\)-nél kisebb páros számra beláttuk az állítást (\(\displaystyle n \geq 3\)), igazoljuk \(\displaystyle 2n\)-re is.

Először rendezzük párokba a vasúti kocsikat, és csináljunk \(\displaystyle n\) darab próbát, minden párhoz egyet. Legyen \(\displaystyle k\) azon próbák száma ezek közül, melyekre különböző típusú a két vasúti kocsi. Az ezekhez a próbákhoz tartozó \(\displaystyle 2k\) kocsit hagyjuk el, és ekkor azt kell eldönteni, hogy a többi \(\displaystyle 2n-2k\) kocsi között ugyanannyi van-e a kétféle típusból. Tudjuk, hogy az egy párban szereplő kocsik ugyanolyanok. Így innentől a kérdés az, hogy \(\displaystyle n-k\) kocsiból hány kérdéssel tudjuk eldönteni a feladat kérdését.

Ha \(\displaystyle n-k\) páratlan, akkor nincs szükség több kérdésre, mivel egyből tudjuk, hogy nem lehet ugyanannyi a kétféle típusból. Tehát ekkor \(\displaystyle n\) kérdés kellett, és \(\displaystyle n \leq 2n-f(n)\) nyilvánvaló \(\displaystyle f(n)\le n\) miatt. Az az érdekes eset, amikor \(\displaystyle n-k\) páros: indukció miatt ehhez legrosszabb esetben \(\displaystyle n-k-f(n-k)\) próba kell, mivel \(\displaystyle f(n-k)=f\left(\frac{n-k}{2}\right)\). Tehát azt kell igazolnunk, hogy minden \(\displaystyle k\) esetén, melyre \(\displaystyle n-k\) páros igaz, hogy \(\displaystyle n+n-k-f(n-k) \leq 2n-f(n)\), mivel ebből következik, hogy legrosszabb esetben is elég a \(\displaystyle 2n-f(n)\) próba. Átrendezve az \(\displaystyle f(n)-k \leq f(n-k)\) egyenlőtlenséget kell igazolnunk. Egyszerű látni, hogy \(\displaystyle f(l)-1 \leq f(l-1)\) minden \(\displaystyle l\) esetén, amiből \(\displaystyle k\) szerinti indukcióval következik a bizonyítandó állítás.

Alsó becslés: Először igazolunk egy látszólag nem ide tartozó lemmát:

Lemma: \(\displaystyle \nu_2\left(\binom{2n}{n}\right)=f(n)\), ahol \(\displaystyle \nu_2(k)\) a \(\displaystyle 2\) kitevőjét jelöli \(\displaystyle k\) prímtényezős felbontásában.

Bizonyítás: A Kummer-tétel azt mondja, hogy tetszőleges \(\displaystyle p\) prímszámra \(\displaystyle \nu_p\left(\binom{a+b}{a}\right)\) megegyezik az átvitelek számával amikor \(\displaystyle a\)-t és \(\displaystyle b\)-t összeadjuk írásban \(\displaystyle p\)-s számrendszerben. Ebből a lemma állítása azonnal adódik, mivel amikor kettes számrendszerben \(\displaystyle n\)-t és \(\displaystyle n\)-t összeadjuk, akkor pontosan akkor lesznek átvitelek, amikor a bináris alakban \(\displaystyle 1\)-es számjegyhez érünk. Egyébként a Legendre-formula segítségével is egyszerűen igazolható a lemma (és a Kummer-tétel is).

Térjünk rá az alsó becslés bizonyítására. Tekintsük a vasúti kocsik összes lehetséges kombinációját: ez \(\displaystyle 2^{2n}\)-féle lehetőség, mert mindegyiknek vagy az eleje, vagy a hátulja északi pólusú. Nevezzük ezeket állapotoknak. Tegyük fel, hogy Peti valamilyen stratégiát követve \(\displaystyle k\) lépés után meg tudta mondani, hogy ugyanannyi van-e a kétféle típusú kocsiból. Ekkor minden lépésénél (ha nem olyan információra kérdezett rá, amit már ki tud következtetni a korábbi kérdéseiből) feleződik a lehetséges állapotok száma. Miután Peti megcsinálta a \(\displaystyle k\) próbát, utána maradtak állapotok, melyeket még nem zárt ki, és vannak állapotok, melyeket valamelyik próbájával kizárt. Legyen \(\displaystyle t\) azon állapotok száma, melyeket még nem zárt ki. Mivel minden lépésben vagy feleződött vagy nem változott a lehetséges állapotok száma, így \(\displaystyle 2^{2n-k} \mid t\).

Tegyük fel, hogy \(\displaystyle 2n\) esetén \(\displaystyle m\) a megoldás, azaz minden lefutás esetén legfeljebb \(\displaystyle m\) próba elég. Tekintsük az összes lehetséges lejátszást. Minden esetben, amikor Peti azt mondja a végén, hogy ugyanannyi van a kétféle vasúti kocsiból, akkor a korábbiak alapján a megmaradt állapotok száma \(\displaystyle 2^{2n-m}\)-mel osztható, és nyilván a különböző lefutásoknál a lehetséges állapotok halmazai diszjunktak. Így összesen is \(\displaystyle 2^{2n-m}\)-mel osztható állapot van, amikor Peti azt mondja, hogy ugyanannyi van a két típusból. Összesen \(\displaystyle \binom{2n}{n}\) eset van, amikor ugyanannyi van a kétféle vasúti kocsiból, így \(\displaystyle 2^{2n-m} \mid \binom{2n}{n}\), azaz a lemma alapján \(\displaystyle 2n-m \leq f(n)\), tehát \(\displaystyle m \geq 2n-f(n)\), és pont ezt akartuk bizonyítani.

Statisztika:

15 dolgozat érkezett.
3 pontot kapott:	9 versenyző.
1 pontot kapott:	6 versenyző.

A KöMaL 2022. januári matematika feladatai