Problem B. 3950. (November 2006)

B. 3950. Let H be the set of integers not greater than 2006: H={1,2,...,2006}. Let D denote the number of those subsets of the set H in which the number of elements divided by 32 leaves a remainder of 7, and let S denote the number of those subsets of the set H in which the number of elements divided by 16 leaves a remainder of 14. Prove that S=2D.

(Based on an OKTV (National Competition) problem)

(5 pont)

Deadline expired on December 15, 2006.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

44 students sent a solution.

5 points: 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 points: Somogyi Ákos, Szirmay-Kalos Barnabás, Wagner Zsolt.

3 points: 3 students.

1 point: 2 students.

0 point: 4 students.

Problems in Mathematics of KöMaL, November 2006

44 students sent a solution.
5 points:	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 points:	Somogyi Ákos, Szirmay-Kalos Barnabás, Wagner Zsolt.
3 points:	3 students.
1 point:	2 students.
0 point:	4 students.

Already signed up?
New to KöMaL?