Feladat: 2011. évi Kürschák matematikaverseny 1. feladata Korcsoport: - Nehézségi fok: -
Füzet: 2012/február, 68. oldal  PDF  |  MathML 
Témakör(ök): Kürschák József (korábban Eötvös Loránd), Matematika, Oszthatóság, Legnagyobb közös osztó, Számsorozatok
Hivatkozás(ok):Feladatok: 2012/február: 2011. évi Kürschák matematikaverseny 1. feladata

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 binomiális együtthatók mintájára legyen

B(n,0)=1,ésB(n,k)=anan-1⋅...⋅an-k+1akak-1⋅...⋅a1,ha1≤k≤n.(1)
Az n szerinti indukcióval bizonyítjuk, hogy B(n,k) egész szám.
A k=0 és k=n esetekben az állításunk triviális, hisz B(n,0)=B(n,n)=1. Ez a megfigyelés egyúttal az n=1 esetet is bizonyítja. Tegyük fel tehát, hogy 0<k<n, és B(n',k')∈Z teljesül minden 1≤k'≤n'<n értékre.
Az (1) definícióból láthatjuk, hogy
B(n,k)=anak⋅B(n-1,k-1)=anan-k⋅B(n-1,k).(2)

A feladat feltétele szerint az an szám osztható ak és an-k legnagyobb közös osztójával. Ezért vannak olyan x, y egész számok, amelyekre akx+an-ky=an. Ezt beírva (2)-be,
B(n,k)=akx+an-kyan⋅B(n,k)=x⋅akanB(n,k)+y⋅an-kanB(n,k)==x⋅B(n-1,k-1)+y⋅B(n-1,k).
Az indukciós feltevés szerint a jobb oldalon álló számok egészek, így B(n,k) is egész.  □
 
Megjegyzések. 1. Az 1,2,3,... sorozatra triviálisan fennáll a kívánt feltétel. A feladat erre a konkrét sorozatra éppen a a binomiális együtthatók egész tulajdonságát állítja. A kitűzött feladat tehát arra mutat rá, hogy a szorzatok hányadosának egész tulajdonsága már egy, az a1,a2,... sorozatról kikötött jóval gyengébb feltételből is következik.
2. Több versenyző próbálkozott annak becslésével, hogy egy p prím milyen kitevőn osztja a számlálót, illetve a nevezőt. Nem nagyon nehéz megmutatni, hogy tetszőleges q prímhatványnak legalább annyi többszöröse van az an,an-1,...,an-k+1 számok között, mint az a1,a2,...,ak-1⋯ak számok között. Ebből a megfigyelésből pedig könnyen adódik a feladat megoldása.