Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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 ele­meiket 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 disz­junktak, 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:

A C. 1720. feladat értékelése még nem fejeződött be.


A KöMaL 2022. áprilisi matematika feladatai