Problem C. 1602. (April 2020)

C. 1602. Two tenth-grade students and two eleventh-grade students sat down to solve the exercises of type C in the April issue of KöMaL. (There are seven exercises each month. Exercises 1–5 are for students in grade 10 at most, while exercises 3–7 may be solved by 11th and 12th grade students.) After an hour, they observed that each exercise was solved by exactly one of them, and that everyone solved at least one exercise. In how many different arrangements may they have solved the exercises? (Two arrangements are considered different if there is at least one exercise that is solved by a different student.)

(5 pont)

Deadline expired on May 11, 2020.

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

Megoldás. Jelölje a két tizedikes diákot \(\displaystyle A,B\), a két tizenegyedikeset pedig \(\displaystyle C,D\). Minden feladathoz rendeljük hozzá azt a diákot (betűt), ,,aki'' megoldotta. Ekkor azon 7 hosszú, különböző \(\displaystyle A,B,C,D\) sorozatok számát kell meghatároznunk, amelyekben minden betű szerepel, az első két helyen \(\displaystyle A\) vagy \(\displaystyle B\), az utolsó két helyen pedig \(\displaystyle C\) vagy \(\displaystyle D\) áll. Ehhez a szita-módszert használjuk, eközben végig csak azokkal az \(\displaystyle A,B,C,D\) sorozatokkal dolgozunk, melyekben az első két helyen \(\displaystyle A\) vagy \(\displaystyle B\), az utolsó két helyen pedig \(\displaystyle C\) vagy \(\displaystyle D\) áll, legyen ezen sorozatok halmaza \(\displaystyle S\). Jelölje \(\displaystyle N_{ABCD}\) azon \(\displaystyle S\)-beli sorozatok számát, amiben \(\displaystyle A, B, C, D\) szerepelhet.

Az összes ilyen hét hosszú \(\displaystyle A,B,C,D\) sorozatok száma

\(\displaystyle N_{ABCD}= 2 \cdot 2 \cdot 4 \cdot 4 \cdot 4 \cdot 2 \cdot 2=1024,\)

hiszen az első és utolsó két feladatot 2-2, míg a középső hármat 4 ember oldhatta meg.

Azonban az \(\displaystyle S\)-beli sorozatok közül nem mindegyikben szerepel mind a négyféle betű. Így ebből ki kell vonni azoknak az \(\displaystyle S\)-beli sorozatoknak a számát, amiben 3 betű szerepelhet, ezek száma legyen értelmszerűen: \(\displaystyle N_{ABC},N_{ABD},N_{ACD}\), illetve \(\displaystyle N_{BCD}\). Ezekben az esetekben vagy az első kettőt vagy az utolsó kettőt csak 1 ember oldhatta meg, míg a középső hármat 3, így ezeknek a száma egyenlő, méghozzá:

\(\displaystyle N_{ABC}=N_{ABD}=N_{ACD}=N_{BCD}= 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 1 \cdot 1= 108.\)

Ezáltal viszont az olyan sorozatokat, melyekben csak két betű szerepel 2-szer vontuk le (például, ha csak \(\displaystyle A\) és \(\displaystyle C\) szerepel, akkor ezt \(\displaystyle N_{ABC}\)-ben és \(\displaystyle N_{ACD}\)-ben is számoltuk).

Így végül az eddigiekhez hozzáadjuk azokat az \(\displaystyle S\)-beli sorozatok számát, amelyekben csak két betű (\(\displaystyle AC, AD, BC, BD\)) szerepelhet, mert ezeket duplán vontuk le. (Olyan \(\displaystyle S\)-beli sorozat, amiben csak \(\displaystyle A\) és \(\displaystyle B\), vagy csak \(\displaystyle C\) és \(\displaystyle D\) van, nincsen a feltételek miatt.) Ekkor az első és az utolsó kettőt csak 1-1 ember oldhatta meg, míg a középső hármat 2-2, így ezek száma is egyenlő, méghozzá:

\(\displaystyle N_{AC}=N_{AD}=N_{BC}=N_{BD}=1 \cdot 1 \cdot 2 \cdot 2 \cdot 2 \cdot 1 \cdot 1= 8.\)

Olyan \(\displaystyle S\)-beli sorozat, amiben csak egyféle betű szerepel nincsen, így ezzel már a helyes elemszámot kapjuk.

Tehát a kérdéses darabszám:

\(\displaystyle N_{ABCD}-N_{ABC}-N_{ABD}-N_{ACD}-N_{BCD}+N_{AC}+N_{AD}+N_{BC}+N_{BD}= 1024 - 4 \cdot 108 + 4 \cdot 8 =624.\)

Tehát 624-féle felosztásban dolgozhattak a feladatokon.

Statistics:

88 students sent a solution.
5 points:	Balogh Adrián, Barát Benedek, Barczikay Ákos, Cseke Balázs, Cserkuti Sándor, Csilling Dániel, Csonka Illés, Deák Gergely, Dékány Csaba, Domján Olivér, Egyházi Hanna, Feczkó Nóra, Fekete Patrik, Foris Dávid, Gombos Gergely , Halász Henrik, Horváth Milán, Kalocsai Zoltán, Kocsis 827 Péter, Koleszár Domonkos, Kovács Benedek Noel, Lőw László, Metzger Ábris András, Nagy 429 Leila, Németh Máté Előd, Perényi Lídia , Ruszkai Dániel, Sebestyén József Tas, Somogyi Dalma, Szabó 423 Ágnes, Szabó Zóra, Szalanics Tamás, Szamkó Szabolcs, Székely Milán, Varga Boldizsár, Veres Dorottya, Zádori Petra.
4 points:	Balla Álmos András, Hajós Balázs, Klepáček László, Reviczki Roland, Schäffer Donát, Schiller Bence, Szabó Réka, Szakács Domonkos, Szittyai Anna, Tarján Teréz, Varga 928 Péter, Xu Yiling.
3 points:	18 students.
2 points:	9 students.
1 point:	3 students.
0 point:	9 students.

Problems in Mathematics of KöMaL, April 2020