Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A C. 1548. feladat (2019. május)

C. 1548. Anna gondol egy \(\displaystyle 3\times 3\)-as négyzet néhány mezőjére. Ezután megmondja Bálintnak minden sorról és oszlopról, hogy hány mező szerepel benne az általa gondoltak közül. Hányféleképpen tud Anna úgy gondolni, hogy az általa adott információkból Bálint ne találhassa ki egyértelműen, melyek voltak a gondolt mezők?

(5 pont)

A beküldési határidő 2019. június 11-én LEJÁRT.


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.


Statisztika:

A C. 1548. feladat értékelése még nem fejeződött be.


A KöMaL 2019. májusi matematika feladatai