Feladat: 961. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Arató P. ,  Barabás Gy. ,  Bartha L. ,  Baticz Kinga ,  Bencsik I. ,  Biborka T. ,  Bollobás Béla ,  Csibi L. ,  Czékus L. ,  Dániel G. ,  Durst I. ,  Eberhardt Mariann ,  Fejes L. ,  Fekete Ildikó ,  Fritz J. ,  Gaál S. ,  Hahn J. ,  Halász G. ,  Hammer G. ,  Katona Mária ,  Kolonits F. ,  Máté A. ,  Máté Zs. ,  Mezei F. ,  Molnár E. ,  Muszély Gy. ,  Nagy Ákos ,  Náray Miklós (Bp.) ,  Parti Enikő ,  Pósa Lajos ,  Pósch Margit ,  Rátkai Zs. ,  Rozváczy Judit ,  S. Nagy Erzsébet ,  Sikabonyi Gy. ,  Székely J. ,  Tihanyi A. ,  Tomcsányi Béla ,  Tusnády G. 
Füzet: 1959/november, 116 - 118. oldal  PDF  |  MathML 
Témakör(ök): Prímszámok, Feladat
Hivatkozás(ok):Feladatok: 1959/március: 961. matematika feladat

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.

I. megoldás: Tegyük fel ‐ a bizonyítandó állítással ellentétben ‐, hogy egy az N=abc¯ szám jegyeiből felcseréléssel képezett N' szám többszöröse N-nek: N'=kN, ahol k egész szám. Tekintsük a D=N'-N=(k-1)N számot; megmutatjuk, hogy ez osztható 9-cel: D=9M, ahol M egész. Ugyanis N=100a+10b+c=a⋅102+b⋅101+c⋅100, és N'=a⋅10α+b⋅10β+c⋅10γ, ahol α, β, γ a 0, 1, 2 kitevőket jelentik valamely sorrendben, tehát D=a(10α-102)+b(10β-101)+c(10γ-100), és itt mind a három tag osztható 10-1=9-cel, mert a különbség vagy 0, vagy 10 egy alkalmas hatványát kiemelve egy ±(10δ-1), δ≥1 alakú tényező marad, ami osztható 9-cel. Másrészt, a kisebbítendőt növelve, a kivonandót csökkentve D=N'-N<1000-100=900; eszerint M=D/9<100, vagyis M legfeljebb kétjegyű szám.
Most már a (D=)9M=(k-1)N egyenlőség világosan mutatja, hogy ellentmondásra jutottunk: a bal oldalnak legfeljebb kétjegyű törzsszám-osztója lehet, a jobb oldalnak pedig van háromjegyű törzsszám osztója: az N szám. ‐ Ezzel az állítást bebizonyítottuk.

 

Tomcsányi Gyula (Budapest, Toldy F. g. II. o. t.)
 

Megjegyzések: 1. Nem mondtuk ki, de nyilvánvaló, hogy k>1, vagyis azt bizonyítottuk, hogy N a N'-nek valódi (N'-nél kisebb) osztója nem lehet. Számos dolgozat kizárta a vizsgálatból az aac¯, aba¯, abb¯ alakú törzsszámokat, amilyenek pl. 331, 313, 311 (aaa¯ alakú törzsszám nincs, mert 111=3⋅37). Ez nem célszerű, mert az N'>N feltevéssel a tétel az egyenlő jegyeket is tartalmazó törzsszámokra is érvényes; már pedig a háromjegyű törzsszámoknak közel a harmadában két jegy egyenlő.
2. Az is ellentmondás, hogy a bal oldal osztható 9-cel, a jobb oldal pedig nem, mert N törzsszám, k-1 pedig az 1, 2, ..., 8 számok valamelyike, hiszen k<10, mert k=10-zel N'=10N=abc0¯ négyjegyű szám lenne. ‐ Ez mutatja, hogy az állítás minden 3-mal nem osztható összetett számra is érvényes, akárhány jeggyel van is leírva.
 

Pósa Lajos (Budapest XIII., Sziget utcai ált. isk. V. o. t.)
 

3. Az állítás az N'≠N megszorítással a törzsszámoknak bármely számrendszerben felírt alakjára érvényes, hacsak az illető rendszerben többjegyűek (egyjegyű számban viszont nincs értelme a jegyek felcserélésének). Legyen ugyanis az alapszám B (bázis), így a fentiekhez hasonlóan D=(B-1)M=(k-1)N, és itt N több jeggyel van írva az egyjegyű B-1-nél is, M-nél is. Valóban, N jegyeinek számát j-vel jelölve Bj-1≤N, N'<Bj, így D=(B-1)M<Bj-Bj-1=Bj-1(B-1), tehát M<Bj-1 (mert B≠1, és így B-1≠0), már pedig Bj-1 a B-alapú számrendszer legkisebb j-jegyű száma. ‐ Érvényes az állítás minden a B-1-hez relatív prím nem-törzsszám N-re is.
4. Számos dolgozat az N'=acb¯, bac¯, bca¯, cab¯, cba¯ számokról külön-külön mutatta meg, hogy a velük képezett N'-N különbségnek nem lehet háromjegyű törzsszám-osztója. Az ilyen dolgozatok hosszadalmasak, és rendszerint mégis hiányosak.
 

II. megoldás: Az N'=kN feltevés lehetetlenségét az is mutatja, hogy sorravéve a k-ként szóbajövő 2, 3, ..., 9 értékeket, valamennyi ellentmondásra vezet. N prím, tehát nem osztható 3-mal, így jegyeinek összege sem, ez az összeg N'-re ugyanaz, ezért N' sem osztható 3-mal, tehát k nem lehet 3, 6, 9. Lehetetlen k=2, 5, 8 is, mert ha N=3C+1, akkor ezekkel N'=kN a 3E+2 alakban írható, ha pedig N=3C+2, akkor N'=3E+1, így N és N'-ben a jegyek összege ‐ ami 3-mal osztva ugyanannyi maradékot ad, mint maga a szám ‐ nem lehetne egyenlő.
k=4 mellett N' utolsó jegye, vagyis N egyik jegye páros volna, másrészt N<250, így első jegye 1, vagy 2. Az első esetben a=1, páratlan, s mivel c is páratlan, mert N prím, azért N páros jegye b. Eszerint N'=cab¯, és így az N'=4N feltevésből:
100c+10a+b=400a+40b+4c,azaz96c=3⋅13(10a+b),
és ez lehetetlen, mert a bal oldal nem osztható 13-mal. ‐ Ha pedig a=2, akkor b legfeljebb 4, és N' első jegye legalább 8. Ez csak c lehet, c viszont páratlan, tehát c=9. Így 4N=N'-nek utolsó jegye 6, ilyen pedig N-ben nincs.
Végül k=7 mellett N<1000/7<143, így a=1 és b≤4, ezért N' első jegye legalább 7, tehát c=7, vagy 9. Az első esetben N'=7N-nek utolsó jegye 9, ezt a és b korlátozott értékei nem adhatják; c=9 esetén pedig 7N utolsó jegye 3, így N=139 lenne, de 7N=973 nem az N jegyeiből áll.
Ezzel k minden szóbajövő értékét kizártuk, feltevésünk lehetetlennek bizonyult.
 

Bollobás Béla (Budapest, Apáczai Csere J. gyak. g. II. o. t.)