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 $\le$ i<2^k esetén A_n(k,i) a H_n halmaz azon részhalmazainak száma, amelyekben az elemek összegét 2^k-nal osztva a maradék i. Ezek szerint H=H₂₀₀₆, D=A₂₀₀₆(5,7) és S=A₂₀₀₆(4,14). A feladat megoldása azon az általános észrevételen nyugszik, hogy ha n $\ge$ 2^k-1, akkor minden 0 $\le$ i<2^k esetén |A_n(k,i)|=2^n-k, vagyis H_n összesen 2ⁿ 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 2^k-nal osztva milyen maradékot ad.

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

A_n+1(k,i)=A_n(k,i)+A_n(k,j)=2^.2^n-k=2^(n+1)-k.

Mivel ${\mathcal A}_1(1)$ nyilván igaz, kapjuk, hogy ${\mathcal A}_1(n)$ is igaz minden n $\ge$ 1 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 $\ge$ 2^k-1 esetén. Bebizonyítjuk, hogy ekkor ${\mathcal A}_{k+1}(n)$ is teljesül minden n $\ge$ 2^k 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=2^k és 0 $\le$ i<2^k+1. Legyen j=i+2^k=i-n+2^k+1 vagy j=i-2^k=i-n aszerint, hogy 0 $\le$ i<2^k teljesül-e, vagy sem. Az előző paragrafus gondolatmenete szerint

A_n(k+1,i)=A_n-1(k+1,i)+A_n-1(k+1,j)=A_n-1(k,i^*),

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

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

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

Mindezek alapján 2006>2⁴ miatt D=A₂₀₀₆(5,7)=2²⁰⁰¹ és S=A₂₀₀₆(4,14)=2²⁰⁰², 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

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ő.

Már regisztráltál?
Új vendég vagy?