A B. 4974. feladat (2018. október)

B. 4974. Legalább hány számot kell kiválasztani az \(\displaystyle 1, 2,\ldots, 10\) számok közül, hogy biztosan legyen közöttük néhány szám, melyek összege osztható 11-gyel, bárhogyan is történik a számok kiválasztása?

Javasolta: Róka Sándor (Nyíregyháza)

(3 pont)

A beküldési határidő 2018. november 12-én LEJÁRT.

Megoldás. Négy szám kiválasztása esetén még lehet, hogy nem lesz 11-gyel osztható összeg. Például, ha az \(\displaystyle 1,2,3,4\) számokat választjuk ki, akkor közülük néhánynak az összege mindig legalább 1 és legfeljebb \(\displaystyle 1+2+3+4=10\), vagyis nem jön létre 11-gyel osztható összeg.

Megmutatjuk, hogy öt szám kiválasztása esetén mindig lesz 11-gyel osztható összeg. Tegyük fel indirekten, hogy ki lehet választani 5 számot úgy, hogy nincsen 11-gyel osztható összeg.

Először is, az

\(\displaystyle \{1,10\},\{2,9\},\{3,8\},\{4,7\}, \{5,6\}\)

párok mindegyikénél 11 az összeg, így ha nincs 11-gyel osztható összeg, akkor mind az 5 párból egy-egy elemet választottunk ki. Feltehető, hogy az 1 ki lett választva (és a 10 nem). (Máskülönben hajtsuk végre az \(\displaystyle a\leftrightarrow 11-a\) cserét minden elemre, ekkor 11-gyel osztható összegekből továbbra is 11-gyel osztható összegek lesznek, és megfordítva.) Két esetet különböztetünk meg aszerint, hogy a második pár melyik tagja lett kiválasztva.

1. eset: a 2 is ki lett választva.
Ekkor a 8 nem lehet kiválasztva, mert \(\displaystyle 1+2+8=11\) lenne. Tehát a 3 is ki lett választva. Ekkor viszont a 7 nem lehet kiválasztva \(\displaystyle 1+3+7=11\) miatt. Tehát a 4 is ki lett választva. Mivel \(\displaystyle 1+4+6=11\), ezért az ötödik kiválasztott szám az 5. Ekkor viszont \(\displaystyle 2+4+5=11\), vagyis ellentmondást kaptunk.

2. eset: a 2 nem lett kiválasztva.
Ekkor a 9 ki lett választva. Két alesetet különböztetünk meg aszerint, hogy a harmadik pár melyik tagja lett kiválasztva.

2.1. eset: a 3 ki lett választva.
Mivel \(\displaystyle 1+3+7=11\), ezért a 7 nem lett kiválasztva, így a 4 viszont igen. Hasonlóan, \(\displaystyle 1+4+6=11\) miatt az ötödik kiválasztott szám nem a 6, hanem az 5. Azonban \(\displaystyle 1+3+4+5+9=22\), ami ellentmondás.

2.2 eset: a 3 nem lett kiválasztva.
Tehát az 1 és a 9 mellett a 8 is ki lett választva. Mivel \(\displaystyle 5+8+9=22\), ezért az ötödik párból a 6 lett kiválasztva. Mivel \(\displaystyle 1+4+6=11\), ezért a negyedik párból pedig a 7. Tehát a kiválasztott számok \(\displaystyle 1,9,8,6,7\), azonban \(\displaystyle 1+6+7+8=22\) miatt ismét ellentmondást kaptunk.

Minden esetben ellentmondásra jutottunk, így beláttuk, hogy bármely 5 kiválasztott szám közül néhánynak az összege osztható 11-gyel. Tehát a feladat kérdésére a válasz: legalább öt számot kell kiválasztanunk, hogy mindenképpen legyen 11-gyel osztható összeg.

Statisztika:

200 dolgozat érkezett.
3 pontot kapott:	101 versenyző.
2 pontot kapott:	21 versenyző.
1 pontot kapott:	36 versenyző.
0 pontot kapott:	35 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	7 dolgozat.

A KöMaL 2018. októberi matematika feladatai