Feladat: B.3950 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Aczél Gergely ,  Árvay Anna ,  Aujeszky Tamás ,  Berecz Dénes ,  Bodor Bertalan ,  Cseh Ágnes ,  Cserép Máté ,  Éles András ,  Fonyó Dávid ,  Gőgös Balázs ,  Grósz Dániel ,  Honner Balázs ,  Keresztfalvi Tibor ,  Kiss Réka ,  Kornis Kristóf ,  Kovács István ,  Kunos Ádám ,  Kunovszki Péter ,  Mészáros András ,  Nagy Dániel ,  Peregi Tamás ,  Sümegi Károly ,  Szalkai Balázs ,  Szalóki Dávid ,  Szűcs Gergely ,  Tossenberger Anna ,  Tóth László Márton ,  Trényi Róbert ,  Török Balázs ,  Varga László ,  Wolosz János ,  Zieger Milán 
Füzet: 2008/március, 147. oldal  PDF file
Témakör(ök): Maradékos osztás, Részhalmazok, Feladat
Hivatkozás(ok):Feladatok: 2006/november: B.3950

Legyen a H a 2006-nál nem nagyobb pozitív egészek halmaza: H={1,2,...,2006}. Jelölje D a H halmaz azon részhalmazainak a számát, amelyekben az elemek összegét 32-vel osztva 7-et kapunk maradékul, és jelölje S a H halmaz olyan részhalmazainak a számát, amelyekben az elemek összegét 16-tal osztva 14-et kapunk maradékul. Igazoljuk, hogy S=2D.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Jelölje K az {1;2;4;8;16} halmazt. Mivel a 2-es számrendszerben a 0-tól 31-ig terjedő természetes számok mindegyike felírható egyértelműen egy legfeljebb ötjegyű számként, a K összesen öt elemének felhasználásával képezett (legfeljebb öttagú) összegként éppen a 32-vel való osztási maradékok állnak elő, mégpedig egyértelműen.
Legyen M a H halmaz K-ba nem tartozó elemeinek a halmaza. Az M minden X részhalmazához a fentiek szerint létezik pontosan egy olyan Y részhalmaza K-nak, hogy az X és Y halmazok egyesítésének elemeit összeadva az összeg 32-vel való osztási maradéka előre megadott, esetünkben 7 legyen: ha ugyanis az X elemeinek összege t, akkor az az Y lesz megfelelő, amelynek elemeit összeadva éppen (7-t)-nek a 32-vel való (nemnegatív) osztási maradékát kapjuk. A D tehát megegyezik az M összes részhalmazainak a számával, 2|M|=22001-nel. Az S meghatározása hasonló D kiszámításához: az iménti K helyett itt a K*={1;2;4;8} halmaz elemeiből képezett összegekkel tudunk tetszőleges, 16-tal való osztási maradékot egyértelműen előállítani; ezért S értéke az M*={1x2006x1,2,4,8} részhalmazainak száma, 2|M*|=22002=2D.