Problem B. 5007. (February 2019)

B. 5007. We have \(\displaystyle 3n+1\) coins, \(\displaystyle n\) of which have 0 on one side and \(\displaystyle 11\) on the other. Another \(\displaystyle n\) coins have 0 on one side and \(\displaystyle 44\) on the other, and the remaining \(\displaystyle n+1\) coins have 0 on one side and \(\displaystyle 99\) on the other. All the coins are tossed at the same time. What is the probability that the sum of the resulting numbers is divisible by 7? (The coins are fair coins.)

(4 pont)

Deadline expired on March 11, 2019.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Mivel az összeg 7-es maradéka érdekes számunkra, ezért áttérhetünk az érméken szereplő számok 7-es maradékára: vehetjük úgy, hogy 11 helyett 4, 44 helyett 2, 99 helyett 1 szerepel az érméken. Az érméket osszuk \(\displaystyle n\) darab hármas csoportba úgy, hogy minden csoportban legyen egy \(\displaystyle 0-1\), egy \(\displaystyle 0-2\) és egy \(\displaystyle 0-4\) típusú érme (az \(\displaystyle i\)-edik csoportot jelöltje \(\displaystyle A_i\)), és ekkor marad még egy \(\displaystyle 0-1\) típusú érme. Megvizsgáljuk, hogy a \(\displaystyle 3^{3n+1}\) féle dobás esetén az összeg 7-es maradéka hogyan alakul. Mivel minden dobás egyforma valószínűségű, innen már a keresett valószínűséget könnyen meg tudjuk majd adni.

Ha az \(\displaystyle A_1\)-beli érmék közül legalább egynek nem a 0-s oldala lesz felül, akkor ezen három szám összege \(\displaystyle 1,2,3,4,5,6,7\) lehet (mindegyik egyféleképpen jöhet ki). Vagyis ez azt jelenti, hogy csak az ilyen dobásokat tekintve minden maradék ugyanannyiszor fordul elő, hiszen bármely \(\displaystyle a\) számra (ami a többi dobás összege) az \(\displaystyle a+1,a+2,\dots,a+7\) számok 7-es maradéka kiadja mind a 7-féle lehetséges maradékot.

A továbbiakban csak azokat a dobásokat vizsgáljuk, amiknél az \(\displaystyle A_1\)-beli eredmény \(\displaystyle 0-0-0\) lett. Ha az \(\displaystyle A_2\)-beli eredmény nem \(\displaystyle 0-0-0\), akkor az előző gondolatmenet megismétlésével kapjuk, hogy minden maradék ugyanannyiszor jön ki.

Ezután azokat az eseteket nézzük, amikor \(\displaystyle A_1\)-ben és \(\displaystyle A_2\)-ben is \(\displaystyle 0-0-0\) eredményt kapunk. A korábbiakhoz hasonlóan kapjuk, hogy ha \(\displaystyle A_3\)-ban nem \(\displaystyle 0-0-0\) az eredmény, akkor minden maradék ugyanannyiszor jön ki.

Ezt folytatva, végül azt kapjuk, hogy a hétféle maradékot ugyanannyiszor kapjuk meg az olyan dobásoknál, amiknél a hármas csoportokba osztott \(\displaystyle 3n\) érme nem mind 0-t adott. Ha ezek mind 0-t adtak, akkor a \(\displaystyle (3n+1)\)-edik érme eredménye adja az összeg maradékot, ami így vagy 0 vagy 1. Ez azt jelenti, hogy a \(\displaystyle 2^{3n+1}\)-féle lehetőség közül a \(\displaystyle 2,3,4,5,6\) maradékok ugyanannyiszor jönnek ki, a \(\displaystyle 0,1\) maradékok pedig 1-gyel többször.

Így annak valószínűsége, hogy az összeg osztható 7-tel \(\displaystyle \frac{\frac{2^{3n+1}-2}{7}+1}{2^{3n+1}}=\frac{2^{3n+1}+5}{7\cdot 2^{3n+1}}\).

2. Megoldás (vázlat). A 2-hatványok 7-es maradéka egy három hosszú ciklus szerint periodikusan ismétlődik: \(\displaystyle 1,2,4,1,2,4,\dots\) (\(\displaystyle 2^0=1\)-gyel kezdve a sorozatot). Mindez azt jelenti, hogy az eredetivel ekvivalens feladatot kapunk ha az \(\displaystyle i\)-edik érme egyik oldalán \(\displaystyle 0\), másik oldalán pedig \(\displaystyle 2^{i-1}\) van (ahol \(\displaystyle 1\leq i \leq 3n+1\)). Ekkor egy dobás eredményére úgy is tekinthetünk, mint egy 2-es számrendszerben felírt számra. Az összes számot 0 és \(\displaystyle 2^{3n+1}-1\) között egyforma eséllyel kapjuk meg, így a kérdés az, hogy köztük hány 7-tel osztható van. A legelső szám (0) osztható 7-tel, és innen minden 7-edik osztható vele, ezek közül az utolsó \(\displaystyle 2^{3n+1}-2\).

Így számuk \(\displaystyle \frac{2^{3n+1}+5}{7}\), így az 1. Megoldásban kapott valószínűséget kapjuk.

Statistics:

48 students sent a solution.
4 points:	Baski Bence, Beke Csongor, Bencsik Ádám, Biczó Benedek, Bokor Endre, Bukva Dávid, Csaplár Viktor, Füredi Erik Benjámin, Győrffi Ádám György, Győrffy Johanna, Hámori Janka, Jánosik Áron, Kerekes Boldizsár, Kocsis Anett, Kovács 129 Tamás, Mátravölgyi Bence, Nagy Nándor, Nguyen Bich Diep, Nyárfádi Patrik, Reimann Kristóf, Sebestyén Pál Botond, Soós 314 Máté, Tálos Zoltán, Terjék András József, Tiderenczl Dániel, Tóth 827 Balázs, Velich Nóra, Weisz Máté.
3 points:	Argay Zsolt, Fleiner Zsigmond, Jánosik Máté, Kerekes Anna, Nagy 551 Levente, Stomfai Gergely, Szabó 991 Kornél, Tóth 057 Bálint, Várkonyi Zsombor, Zsigri Bálint.
2 points:	3 students.
1 point:	4 students.
0 point:	3 students.

Problems in Mathematics of KöMaL, February 2019