Problem A. 469. (December 2008)
A. 469. Let 0k
n and m
2 be integers. Consider the k-element subsets of
; in every such subset, compute the residue of the sum of elements, modulo m. Prove that if the m residues are distributed uniformly - i.e. every residue occurs exactly
times - then n
m.
(5 pont)
Deadline expired on February 16, 2009.
Sorry, the solution is available only in Hungarian. Google translation
Megoldásvázlat. Legyen
Az tag értéke attól függ, hogy
hány maradékot ad m-mel osztva. Ha m>1 és mindegyik maradék ugyanannyiszor, pontosan
-szer fordul elő, akkor
Az állítás igazolásához tehát elegendő megmutatni, hogy 0k
n<m esetén Sm(n,k)
0.
Az Sm(n,k) függvényről bebizonyítjuk a következőket:
(a) Ha k=0 vagy k=n, akkor |Sm(n,k)|=1;
(b) Tetszőleges 0<k<n esetén
(c) Az Sm(n,k) komplex szám párhuzamos (azonos vagy ellentétes irányú) az számmal, azaz
.
Az (a) tulajdonság triviális, mert az Sm(n,k) egyetlen --- egységnyi hosszúságú --- tagból áll.
A (b) bizonyításához adjuk össze külön azokat a tagokat, amikor xk=n, illetve azokat, amikor xk<n:
A (c) tulajdonság bizonyításához rendezzük párokba a szám k-asokat; legyen párja (n+1-xk,n+1-xk-1,...,n+1-x1). Tetszőleges k-asra az
és
komplex számok szimetrikusak
irányára. Előfordulhat, hogy egy k-as a saját párja, ilyenkor
.
Az Sm(n,k) összegben szereplő tagokat tehát úgy rendezhetjük párokba és különálló tagokra, hogy ezekben az összeg mind valamilyen valós számszorosa az számnak. A (c) tujadonság tehát igaz.
Ezek után n szerinti idukcióval igazoljuk, hogy Sm(n,k)0, ha n<m. Az n=0 és n=1 esetekben ez következik az (a) tulajdonságból. Tegyük fel tehát, hogy 2
n<m és kisebb n-ekre az állítást már igazoltuk. Az (a) miatt elég a 0<k<n esetet vizsgálni.
Tekintsük ismét a (b) összefüggést:
Az indukciós feltevés szerint a jobboldalon álló két tag egyike sem 0. Mivel pedig
nem többszöröse -nek, a két tag nem párhuzamos.
A (b) tulajdonság tehát két olyan, 0-tól különböző komplex szám összegeként állítja elő Sm(n,k)-t, amelyek nem párhumazosak.
Megjegyzés. Az Sm(n,k), Sm(n-1,k) és komplex számok egy olyan háromszöget alkotnak, amelynek ismerjük a szögeit. Ha a háromszögre felírjuk a szinusztételt, kiszámíthatjuk az oldalak hosszát is; például
Ezek után könnyen kiszámítható Sm(n,k) hossza.
A fenti módszerrel belátható, hogy
(*) |
Természetesen a (*) képletet közvetlenül a (b) tulajdonságból is igazolhatjuk indukcióval --- legalábbis ha a képletet előtte egy kismadár megsúgja nekünk.
Statistics:
3 students sent a solution. 5 points: Nagy 235 János, Tomon István. 1 point: 1 student.
Problems in Mathematics of KöMaL, December 2008