KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 15 December 2006.


Google Translation (Sorry, the solution is published in Hungarian only.)

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.


Statistics on problem B. 3950.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley