Problem A. 816. (January 2022)
A. 816. Peter has 2022 pieces of magnetic railroad cars, which are of two types: some has the front with north and the rear with south magnetic polarity, and some has the rear with north and the rear with south magnetic polarity (on these railroad cars the front and the rear can be distinguished). Peter wants to decide whether there are the same number of both type of cars. He can try to fit together two cars in one try. What is the least number of tries needed?
Submitted by Dömötör Pálvölgyi, Budapest
(7 pont)
Deadline expired on February 10, 2022.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
15 students sent a solution. 3 points: 9 students. 1 point: 6 students.
Problems in Mathematics of KöMaL, January 2022