Problem C. 1720. (April 2022)
C. 1720. The elements of a given set of \(\displaystyle 10\) elements are all at most two-digit positive integers. Is it true that such a set will always have two disjoint subsets in which the sum of the elements is equal?
(5 pont)
Deadline expired on May 10, 2022.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. Bármely (nemüres) részhalmaz elemeinek összege legalább \(\displaystyle 1\), legfeljebb pedig a lehető legnagyobb kétjegyű számokat tartalmazó \(\displaystyle 10\) elemű halmaz elemeinek összege, azaz \(\displaystyle 99+98+ \ldots + 91+90=945\), így legfeljebb \(\displaystyle 945\)-féle összeg jöhet létre. Ugyanakkor egy \(\displaystyle 10\) elemű halmaz (nemüres) részhalmazainak száma \(\displaystyle 2^{10}-1=1023\), ezért a skatulyaelv szerint van köztük legalább két különböző részhalmaz, amelyekben az elemek összege egyenlő. Tekintsünk közülük pontosan kettőt, ezek biztosan eltérnek legalább egy elemükben, ezért az esetleges közös elemeiket elhagyva olyan részhalmazokat kapunk, amelyek egyike sem üres, hiszen ha valamelyik üres lenne, az azt jelentené, hogy a közös elemek elhagyása előtt az egyik részhalmaza volt a másiknak, akkor pedig az elemeik összege nem lehetett volna egyenlő. Másrészt az így kapott halmazok már diszjunktak, de az elemeik összege továbbra is egyenlő, hiszen csak a közös elemeket hagytuk el. Ezzel a gondolatmenet végére értünk, beláttuk, hogy a feladat állítása igaz.
Statistics:
25 students sent a solution. 5 points: Szalanics Tamás. 4 points: Cynolter Dorottya, Horváth Milán, Hosszu Noel, Mészáros Anna Veronika, Pekk Márton, Radzik Réka, Sipeki Márton, Tóth Gréta. 3 points: 7 students. 2 points: 2 students. 1 point: 3 students. Unfair, not evaluated: 2 solutionss.
Problems in Mathematics of KöMaL, April 2022