Feladat: F.2139 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Becze I. ,  Blázsik Z. ,  Csikós B. ,  Csordás A. ,  Czifra A. ,  Erdélyi T. ,  Fegyverneki S. ,  Fordán T. ,  Gát Gy. ,  Gömöry Á. ,  Hajnal P. ,  Holup Zsuzsa ,  Horváth M. ,  Kántor S. ,  Karakas J. ,  Lukács 258 Erzsébet ,  Lukács Erzsébet ,  Nagy G. ,  Papp Zs. ,  Pintér F. ,  Pirkó J. ,  Pyber L. ,  Ráth Gy. ,  Sali A. ,  Schwarz P. ,  Seres I. ,  Szabó S. ,  Varga J. ,  Varga Lívia ,  Winkler R. 
Füzet: 1978/szeptember, 10. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorikai leszámolási problémák, Legnagyobb közös osztó, Négyzetrács geometriája, Feladat
Hivatkozás(ok):Feladatok: 1978/március: F.2139

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A kérdéses összeg helyett mindjárt az általánosabb i=1nk(n/i) összeget fogjuk meghatározni.
Definíció szerint k(n/i) azoknak az (x,y) pontoknak a számát adja meg, amelyekre 1xn/i, 1yn/i, és x, y relatív prímek, amit az x'=ix és y'=iy bevezetésével úgy is tekinthetünk, mint azoknak az (x',y') pontoknak a számát, amelyekre 1x'n, 1y'n, és x', y' olyan egész számok, melyek legnagyobb közös osztója i. Így tehát a i=1nk(n/i) összegben az olyan (x',y') pontokat számláljuk össze, amelyeknek mindkét koordinátája 1 és n közé eső egész szám, mégpedig az (x',y') pontot annál az i-nél, amelyik az x' és y' legnagyobb közös osztója.
Másrészt így minden ilyen pontot csak egyszer veszünk számításba, hiszen két pozitív egész szám legnagyobb közös osztója egyértelműen meghatározott. Ezeknek a pontoknak száma nyilván n2, ezért

i=1nk(n/i)=n2.

 Lukács 258 ERzsébet (Budapest, Fazekas M. Gyak. Gimn., Iv. o. t.)