Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem C. 1548. (May 2019)

C. 1548. Ann selects a few fields of a \(\displaystyle 3\times 3\) table. Then row by row and column by column, she tells Bill how many selected fields there are in that row or column. In how many different ways may Ann select her fields so that Bill cannot find out from the given information which fields she selected?

(5 pont)

Deadline expired on June 11, 2019.


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

Megoldás. Az Anna által kiválasztott mezők száma 0 és 9 között lehet (és ezt a számot Bálint könnyedén meg tudja határozni, csak össze kell adnia a 3 sorra, hogy melyikben hány gondolt mező van). Szimmetriai okokból elég azokat az esetek vizsgálni, amikor ezen mezők száma kisebb vagy egyenlő, mint 4. (Hiszen különben áttérhetünk a nem gondolt mezőkre, és ezek száma lesz legfeljebb 4.)

1. eset: A kiválasztott mezők száma 0.

Ekkor Bálint ki tudja találni, Anna mely mezőkre gondolt.

2. eset: A kiválasztott mezők száma 1.

Bálint ekkor is ki tudja találni, Anna mely mezőre gondolt, hiszen egy mezőt az oszlopa (az egyetlen oszlop, amiben 1, és nem 0 gondolt mező van) és a sora (az egyetlen sor, amiben 1, és nem 0 gondolt mező van) egyértelműen meghatároz.

3. eset: A kiválasztott mezők száma 2.

A soroknál és az oszlopoknál is \(\displaystyle 2-0-0\) vagy \(\displaystyle 1-1-0\) lehet a kiválasztott mezők száma (valamilyen sorrendben).

a) Ha az oszlopoknál \(\displaystyle 2-0-0\) a kiválasztott mezők száma, akkor a soroknál csak \(\displaystyle 1-1-0\) lehet, és Bálint ki tudja találni a kiválasztott mezőket. Nevezetesen, a két 0-s oszlop, és a 0-s sor elhagyása után maradó két mezőre gondolt Anna.

b) Ugyanígy megy fordítva, ha a soroknál \(\displaystyle 2-0-0\) a minta (az oszlopoknál pedig \(\displaystyle 1-1-0\)).

c) Az az eset maradt hátra, ha a soroknál és az oszlopoknál is \(\displaystyle 1-1-0\) a minta. Az egyszerűség kedvéért vegyük úgy, hogy az első két sorban, és az első két oszlopban van egy-egy gondolt mező.

Ez kétféleképpen is lehet: ez a két mező lehet az első sor első és a második sor második vagy az első sor második és a második sor első mezője. Tehát ilyenkor Bálint nem tudja kitalálni, melyik mezőkre gondolt Anna.

Az, hogy a soroknál az \(\displaystyle 1-1-0\) leosztás hogyan alakul, háromféleképpen lehet, ugyanígy az oszlopoknál is.

Tehát ebben az esetben összesen \(\displaystyle 3 \cdot 3 \cdot 2= 18\) olyan lehetőség van, aminél nem tudja Bálint kitalálni a gondolt mezőket.

4. eset: A kiválasztott mezők száma 3.

A soroknál és az oszlopoknál is a következő leosztások lehetségesek: \(\displaystyle 3-0-0\), \(\displaystyle 2-1-0\), \(\displaystyle 1-1-1\).

a) Ha az oszlopoknál \(\displaystyle 3-0-0\) a minta, akkor a soroknál csak \(\displaystyle 1-1-1\) lehet, és Bálint ki tudja találni, hogy mik a gondolt mezők: a 3-as oszlop 3 mezője.

b) Ugyanígy, ha valamelyik sornál \(\displaystyle 3-0-0\) a minta, akkor az oszlopoknál \(\displaystyle 1-1-1\), és Bálint egyértelműen ki tudja találni a gondolt mezőket.

c) Az oszlopoknál \(\displaystyle 2-1-0\) a minta. Ekkor a sorokra két lehetőség van:

I. \(\displaystyle 2-1-0\). Ekkor Bálint ki tudja találni: a 0-s sorban és a 0-s oszlopban nincs gondolt szám, a maradék 4 mező közül, pedig mindenütt van, kivéve az 1-es oszlop és 1-sor közös mezőjét.

II. \(\displaystyle 1-1-1\). Ekkor Bálint nem tudhatja egyértelműen Anna mire gondolt, 3 lehetőségre tippelhet: az 1-es oszlopban bárhol lehet a gondolt mező, a 2-es oszlopban pedig ekkor a két másik sorba eső mezőre gondolhatott Anna.

Annának 6 lehetősége van arra, hogy ilyen leosztásban gondoljon mezőkre, hiszen az oszlopoknál a \(\displaystyle 2-1-0\) leosztás \(\displaystyle 3!=6\)-féle sorrendben lehet. Így itt \(\displaystyle 6 \cdot 3 =18\) esetben nem tudja Bálint kitalálni a mezőket.

d) Ugyanígy megy mikor az oszlopoknál \(\displaystyle 1-1-1\), a soroknál \(\displaystyle 2-1-0\) a leosztás. Azaz itt is 18 esetben nem fogja tudni Bálint, hogy Anna miket választott.

e) Végül, ha a soroknál és az oszlopoknál is \(\displaystyle 1-1-1\) a leosztás, akkor Bálint szintén nem tudhatja biztosan, hiszen \(\displaystyle 3!=6\) féle ilyen kiválasztás is van.

Tehát ebben az esetben összesen \(\displaystyle 18+18+6=42\) olyan kiválasztás van, amikor Bálint nem tudja kitalálni a gondolt mezőket.

5. eset: A kiválasztott mezők száma 4.

A soroknál és az oszlopoknál is \(\displaystyle 3-1-0\), \(\displaystyle 2-2-0\), \(\displaystyle 2-1-1\) lehet a leosztás.

a) Ha az oszlopoknál \(\displaystyle 3-1-0\) a minta, akkor soroknál biztosan \(\displaystyle 2-1-1\). Ezekből Bálint egyértelműen kitalálja a gondolt mezőket: a 3-as oszlop mezői, és az 1-es oszlop azon mezője, ami a 2-es sorba esik.

b) Ugyanez a helyzet szimmetriai okokból, ha a soroknál \(\displaystyle 3-1-0\) a minta (és így az oszlopoknál \(\displaystyle 2-1-1\))

c) Az oszlopoknál \(\displaystyle 2-2-0\).

Ekkor két lehetőség van:

I. Soroknál is \(\displaystyle 2-2-0\). Ekkor Bálint ki tudja találni, hiszen a 0-s sor és 0-s oszlop elhagyása után maradó 4 mezőre gondolt Anna.

II. Soroknál \(\displaystyle 2-1-1\).

Ezekből az információkból Bálint kétfélét tud tippelni, azaz nem tudja egyértelműen, Anna mire gondolt. A 0-s oszlopban persze nincsen gondolt mező, így a 2-es sor két másik mezője mindenképpen a gondolt mezők között van. A két 1-es sornak a 2-es oszlopokba eső négy mezője közül kétféleképpen is választható két mező megfelelően: azok a leosztások jók, amikor ez a két mező két külön sorban (és oszlopban) van.

Az oszlopoknál a \(\displaystyle 2-2-0\) leosztás 3-féleképpen lehet, a soroknál a \(\displaystyle 2-1-1\) szintén 3-féleképpen, így itt összesen \(\displaystyle 3 \cdot 3 \cdot 2=18\) lehetőség lehet a gondolt mezőkre, ezeknél tehát Bálint nem tudja kitalálni a gondolt mezőket.

d) Oszlopoknál \(\displaystyle 2-1-1\).

I. Soroknál \(\displaystyle 2-2-0\). Ekkor c)/II.-höz hasonlóan 18 lehetőség van, ezeknél Bálint nem tudja kitalálni a mezőket.

II. Soroknál is \(\displaystyle 2-1-1\).

Tegyük fel először, hogy az első sorból és első oszlopból gondolt 2-re. Ekkor az első sorban és első oszlopban összesen 3 vagy 4 kiválasztott mező van. Akkor van 4, ha az 1. sor első mezője nincs kiválasztva, hanem az 1. sor és az 1. oszlop másik két-két mezője, ez 1 darab eset.

Ha az első sor első mezője ki van választva, akkor tehát az első sor és az első oszlop összesen 3 kiválasztott mezőt tartalmaz, az első sorból és az első oszlopból is 2-2-féleképppen választható ki a másik mező. Ezután a 2-3. sorok 2-3. mezője közül egyértelműen kiderül, melyik mezőjét kell még választani, hogy a megfelelő mintát kapjuk: azt, aminek a sorában és az oszlopában nincs az eddigi három kiválaszott mező közül egy sem. Ez 4 darab eset.

Így összesen \(\displaystyle 3 \cdot 3 \cdot (1+4)= 45\) eset van, ezeknél Bálint nem tudja kitalálni a gondolt mezőket.

Az 5. esetben tehát összesen \(\displaystyle 18+18+45=81\) esetben nem tudja kitalálni Bálint a gondolt számokat.

Ez így összesen az 1-5. esetekben \(\displaystyle 0+0+18+42+81=141\) lehetőség, ezt kell 2-vel szorozni, mivel szimmetriai okokból csak azokat az eseteket néztük végig, ahol a kiválasztott mezők száma kisebb vagy egyenlő 4-nél.

Azaz 282 esetben nem tudja Bálint egyértelműen kitalálni, hogy Anna mely mezőkre gondolt.


Statistics:

68 students sent a solution.
5 points:Ajtai Boglárka, Csilling Katalin, Csonka Illés, Debreczeni Dorina, Hajdú Bálint, Izsa Regina Mária, Kadem Aziz, Kerekes Boldizsár, Kis 194 Károly, Kovács Gábor Benedek, Mácsai Dániel, Mészáros 916 Márton, Molnár 410 István, Molnár Réka, Nagy 551 Levente, Nyitrai Boglárka, Riba Dániel, Somogyi Dalma, Szakács Ábel, Szalanics Tamás, Ungár Éva, Zempléni Lilla.
4 points:Andó Viola, Bognár 171 András Károly, Buzás Bence István, Domján Olivér, Farkas Jázmin, Gombos Gergely , Görcs András, Hordós Adél Zita, Jankovits András, Koleszár Domonkos, Kovács Alex, Majerusz Ádám, Nagy 009 Dávid, Sebe Anna, Székelyhidi Klára, Trombitás Karolina Sarolta, Veres Dorottya.
3 points:13 students.
2 points:10 students.
1 point:1 student.
0 point:4 students.
Not shown because of missing birth date or parental permission:1 solutions.

Problems in Mathematics of KöMaL, May 2019