 |
A C. 1720. feladat (2022. április) |
C. 1720. Adott egy \(\displaystyle 10\) elemű halmaz, amelynek elemei legfeljebb kétjegyű, pozitív egész számok. Igaz-e, hogy ennek a halmaznak mindig van két olyan diszjunkt részhalmaza, amelyekben az elemek összege egyenlő?
(5 pont)
A beküldési határidő 2022. május 10-én LEJÁRT.
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.
Statisztika:
25 dolgozat érkezett. 5 pontot kapott: Szalanics Tamás. 4 pontot kapott: 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 pontot kapott: 7 versenyző. 2 pontot kapott: 2 versenyző. 1 pontot kapott: 3 versenyző. Nem versenyszerű: 2 dolgozat.
A KöMaL 2022. áprilisi matematika feladatai