Problem B. 4974. (October 2018)

B. 4974. At least how many numbers should be selected out of \(\displaystyle 1, 2,\ldots, 10\) so that we can be certain that every such selection will contain a set of numbers whose sum is divisible by 11?

Proposed by S. Róka, Nyíregyháza

(3 pont)

Deadline expired on November 12, 2018.

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

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.

Statistics:

200 students sent a solution.
3 points:	101 students.
2 points:	21 students.
1 point:	36 students.
0 point:	35 students.
Not shown because of missing birth date or parental permission:	7 solutions.

Problems in Mathematics of KöMaL, October 2018