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 B. 3950. feladat (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.

(OKTV feladat nyomán)

(5 pont)

A beküldési határidő 2006. december 15-én LEJÁRT.


Megoldás. Vizsgáljuk a feladatot általánosabban. Jelöljön n,k pozitív egész számokat. Legyen H_n=\{1,2,\ldots,n\}, továbbá 0\lei<2k esetén An(k,i) a Hn halmaz azon részhalmazainak száma, amelyekben az elemek összegét 2k-nal osztva a maradék i. Ezek szerint H=H2006, D=A2006(5,7) és S=A2006(4,14). A feladat megoldása azon az általános észrevételen nyugszik, hogy ha n\ge2k-1, akkor minden 0\lei<2k esetén |An(k,i)|=2n-k, vagyis Hn összesen 2n részhalmaza (az üres halmazt is beleértve, ahol az elemek összege 0) teljesen egyenletesen oszlik el aszerint, hogy a benne lévő elemek összege 2k-nal osztva milyen maradékot ad.

Jelölje {\mathcal A}_k(n) azt az állítást, hogy minden 0\lei<2k esetén |An(k,i)|=2n-k. Először azt mutatjuk meg, hogy {\mathcal A}_k(n)-ből következik {\mathcal A}_k(n+1). Hn+1 részhalmazai között szerepel Hn összes részhalmaza, valamint 2n további halmaz, melyeket úgy kapunk, hogy Hn mindegyik részhalmazát kiegészítjük még az n+1 elemmel. Ezért Hn+1 egy X részhalmazában pontosan akkor fog az elemek összege 2k-nal osztva i maradékot adni, ha vagy X a Hn olyan részhalmaza, amelyben az elemek összege i maradékot ad, vagy pedig X=Y\cup{n+1}, ahol az Y a Hn olyan részhalmaza, amelyben az elemek összege j maradékot ad, ahol j+n+1\equiv i\pmod{2^k}. Következésképp

An+1(k,i)=An(k,i)+An(k,j)=2.2n-k=2(n+1)-k.

Mivel {\mathcal A}_1(1) nyilván igaz, kapjuk, hogy {\mathcal A}_1(n) is igaz minden n\ge1 esetén. Tegyük fel, hogy valamilyen k pozitív egész számra már igazoltuk, hogy {\mathcal A}_k(n) teljesül minden n\ge2k-1 esetén. Bebizonyítjuk, hogy ekkor {\mathcal A}_{k+1}(n) is teljesül minden n\ge2k esetén. Az előző paragrafus értelmében ehhez elég az {\mathcal A}_{k+1}(2^k) állítást igazolni. Legyen tehát n=2k és 0\lei<2k+1. Legyen j=i+2k=i-n+2k+1 vagy j=i-2k=i-n aszerint, hogy 0\lei<2k teljesül-e, vagy sem. Az előző paragrafus gondolatmenete szerint

An(k+1,i)=An-1(k+1,i)+An-1(k+1,j)=An-1(k,i*),

ahol i* az i és j számok közül a kisebbiket jelöli, tehát 0\lei*<2k. Az {\mathcal A}_k(n-1) állítás feltevésünk szerint igaz, ezért

An(k+1,i)=An-1(k,i*)=2(n-1)-k=2n-(k+1),

ami igazolja az {\mathcal A}_{k+1}(n) állítást.

Mindezek alapján 2006>24 miatt D=A2006(5,7)=22001 és S=A2006(4,14)=22002, vagyis valóban S=2D.


Statisztika:

44 dolgozat érkezett.
5 pontot kapott: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 243 Réka, Kornis Kristóf, Kovács 915 István, Kunos Ádám, Kunovszki Péter, Mészáros András, Nagy 314 Dániel, Peregi Tamás, Sümegi Károly, Szalkai Balázs, Szalóki Dávid, Szűcs Gergely, Tossenberger Anna, Tóth 666 László Márton, Török Balázs, Trényi Róbert, Varga 171 László, Wolosz János, Zieger Milán.
4 pontot kapott:Somogyi Ákos, Szirmay-Kalos Barnabás, Wagner Zsolt.
3 pontot kapott:3 versenyző.
1 pontot kapott:2 versenyző.
0 pontot kapott:4 versenyző.

A KöMaL 2006. novemberi matematika feladatai