Feladat: B.4237 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Ágoston Tamás ,  Cséke Balázs ,  Damásdi Gábor ,  Dolgos Tamás ,  Éles András ,  Énekes Péter ,  Janzer Olivér ,  Karl Erik Holter ,  Kiss Melinda Flóra ,  Kovács Áron ,  Márkus Bence ,  Mester Márton ,  Mészáros András ,  Perjési Gábor ,  Szabó Attila ,  Weimann Richárd ,  Weisz Gellért ,  Weisz Ágoston 
Füzet: 2010/december, 537 - 538. oldal  PDF file
Témakör(ök): Feladat, Számsorozatok, Teljes indukció módszere
Hivatkozás(ok):Feladatok: 2010/január: B.4237

Legyen n pozitív egész szám. Határozzuk meg az összes olyan 1xy törtnek az összegét, amelyre az n-nél nem nagyobb x és y számok relatív prímek és összegük nagyobb, mint n.

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.

Megoldás. Vizsgáljuk meg néhány n számra a 1xy összeget. n=1-re csak egy számpár van: 111=1. Ha n=2, akkor két számpár van (1;2) és (2;1), az összeg 112+121=1. Ha n=3, akkor 4 számpár van, (1;3), (3;1), (2;3) és (3;2), az összeg

113+131+123+132=1.

Azt sejtjük, hogy tetszőleges n-re a 1xy összeg 1. Az állítást teljes indukcióval bizonyítjuk. Tegyük fel, hogy n=k-ra igaz az indukciós feltétel. Azt kell belátnunk, hogy n=(k+1)-re is igaz az állítás. Az összeg olyan 1xy törtek összegével csökken, amelyekre x+y=k+1, ugyanis ezekre még teljesül az x+y>k, de nem teljesül az x+y>k+1 feltétel. Ugyanakkor nő az összeg az olyan 1xy törtek összegével, amelyekre x=k+1 és y relatív prímek, illetve azokkal, amelyekre y=k+1 és x relatív prímek. Ezek a párok eddig nem szerepeltek, hiszen mindegyik szám kisebb volt, mint k+1.
Ismert, hogy ha x és y relatív prímek, akkor (x+y;x)=1 és (x+y;y)=1. Ha ugyanis lenne (x+y)-nak és x-nek egynél nagyobb közös osztója, akkor az osztaná a két szám különbségét, vagyis y-t is, ez viszont ellentmondana annak a ténynek, hogy x és y relatív prímek. Ennek ismeretében fogjuk belátni, hogy az összeg pontosan annyival csökken, mint amennyivel nő. Az előbb láttuk, hogy minden x, y számpárhoz hozzárendelhető két számpár, (x+y;x) és (x+y;y), melyekre
1(x+y)x+1(x+y)y=1x+y(1x+1y)=1x+yx+yxy=1xy.

Azt is látjuk, hogy az összeget növelő tagok mindegyikének megadható az (x;y) párja: ha x+y=k+1 és x relatív prímek, akkor x és y is relatív prímek. A fenti megfeleltetés tehát kölcsönösen egyértelmű. Ezzel beláttuk, hogy ha k-ról (k+1)-re változik az n, akkor az összeg 1 marad.
Tehát a feladatban szereplő törtek összege minden pozitív egész n esetén 1.