Feladat: 1250. matematika feladat Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bálint L. ,  Bóta Károly ,  Folly Gábor ,  Gyárfás András ,  Lénárt Zoltán ,  Lovász László ,  Lux I. ,  Makai Endre ,  Minárik László ,  Nagy Klára ,  Pelikán József ,  Simonovits András ,  Székely Gábor ,  Szidarovszky Ferenc ,  Szilágyi Tivadar ,  Tamás Endre 
Füzet: 1964/május, 203 - 205. oldal  PDF  |  MathML 
Témakör(ök): Számsorozatok, Végtelen leszállás módszere, Feladat
Hivatkozás(ok):Feladatok: 1963/május: 1250. 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. Jelöljük az ai, bi, ci, di számnégyest Qi-vel, a benne előforduló legnagyobb értéket mi-vel (i=0,1,2,...). A képezési szabály szerint világos, hogy ha i legalább 1, akkor Qi egyik száma sem negatív, és ennek folytán mi+1mi, ugyanis Qi+1 számai két-két Qi-beli, tehát nem negatív szám különbségének abszolút értékeként adódnak, tehát nem nagyobbak a két szám nagyobbikánál. Bebizonyítjuk, hogy ha a legnagyobb szám nem 0, akkor a negyedik lépésig legkésőbb határozottan csökken a négyes legnagyobb száma: ha mi>0, akkor mi+4<mi. Ebből nyilvánvaló, hogy a nem negatív egész számokból álló m1,m2,... számsorozatban véges számú lépés után fellép egy 0 tag, ez pedig azt jelenti, hogy a megfelelő számnégyes minden tagja 0.
Bizonyításunk egyszerűbb lesz a következő két észrevétel felhasználásával. d1 képezése mutatja, hogy d0-t és a0-t az eredeti számnégyesben ugyanúgy szomszédos tagoknak tekinthetjük, mint pl. a0-t és b0-t. Ezért a b0, c0, d0, a0 számnégyesből kiindulva a számnégyeseknek lényegében ugyanarra a sorozatára jutunk, mint az eredeti négyesből. Ugyanaz áll a d0, c0, b0, a0 négyesből képezett sorozatra. Ezek alapján bármely i(0) index esetén Qi tetszés szerinti tagját tekinthetjük ai-nek, szomszédai egyikét bi-nek, a szomszéd másik szomszédját ci-nek, így a hátra levő tag di gyanánt szomszédja lesz az először kiválasztott tagnak, amint az eredeti elrendezésben is az volt.
Ha Qi-ben nem szerepel mi értékű elem szomszédjaként 0, akkor már mi+1<mi, s így biztosan mi+4<mi. Elég tehát azt az esetet vizsgálni, ha van Qi-ben egy mi értékű elem mellett 0. Az előrebocsátott megjegyzések szerint feltehetjük, hogy Qi ilyen alakú:

v,mi,0,w,
ahol v és w nem negatív egészek és nem nagyobbak mi-nél. Ekkor Qi+1 az
mi-v,mi,w,|v-w|
számnégyes lesz. Qi+2-ben csak akkor nem lesz minden szám kisebb, mint mi, ha Qi+1-ben előfordul egymás mellett az mi és 0 érték, tehát vagy v=mi vagy w=0, vagy pedig v-w=0 és e mellett w és mi-v egyike mi-vel egyenlő, vagyis v=w=mi vagy w=v=0. Ez azt jelenti, hogy a harmadik lehetőség mindkét változata az első két lehetőség valamelyikének speciális esete, így elég azokkal foglalkozni.
Ezekben az esetekben Qi+1 a 0, mi, w, mi-w, vagy az mi-v, mi, 0, v négyes, és a kettő nem különbözik lényegesen (w és mi-v játszik azonos szerepet a két négyesben). Elég tehát az első négyessel foglalkozni. Ekkor Qi+2 az
mi,mi-w,|mi-2w|,mi-w
négyes. Itt mi és 0 érték egymás mellett csak úgy szerepelhet, ha w=mi, minden más esetben Qi+3 számai kisebbek mi-nél. Ha pedig w=mi akkor Qi+2 az
mi,0,mi,0
négyes, így Qi+3 és Qi+4 az
mi,mimi,miill. a0,0,0,0
négyes. Az állításnál valamivel élesebben azt kaptuk tehát, hogy vagy Qi+4 már csupa 0-ból áll, vagy már mi+3<mi. Mint láttuk, ebből a feladat állítása következik.
 
 Szilágyi Tivadar (Budapest, Rákóczi F. g. III. o. t.)
 

II. megoldás. Ha egy Q számnégyes mindegyik száma osztható egy D számmal, akkor a számok különbségei is oszthatók D-vel: a megfelelő két szám D-ed része különbségének a D-szeresei. Így, ha a Q négyes számainak a D-ed részéből alkotott négyes Q', akkor Q-ból és Q'-ből képezve a feladat előírása szerint újabb négyeseket, ezekben két egymásnak megfelelő szám közül vagy mindkettő 0, vagy egyik sem. Így egy négyest úgy is helyettesíthetünk kisebb számokból állóval, ha a négy szám nem relatív prím, hogy mindegyiket osztjuk ugyanazzal a közös osztóval.
Megmutatjuk, hogy bármely számnégyesből kiindulva legkésőbben a negyedik lépésben minden elem páros szám, tehát D=2-vel egyszerűsíthetünk. Elég lesz evégett a páros számok helyére P-t, a páratlanok helyére U-t írni. Ebből megállapíthatjuk a továbbképezéssel adódó számok párosságát is, figyelembe véve, hogy két megegyező párosságú szám különbsége páros, két ellentétes párosságúé pedig páratlan.
Vizsgáljuk először azt az esetet, amikor a négyes három eleme páratlan, egy páros; feltehetjük ekkor az I. megoldásban tett megállapítások szerint, hogy az utolsó elem páros. Ekkor a további négyesek így alakulnak:
Q0   U,  U,  U,  P,Q1   P,  P,  U,  U,Q2   P,  U,  P,  U,Q3   U,  U,  U,  U,Q4   P,  P,  P,  P,  
állításunknak megfelelően.
Már csak a P, P, P, U esetet kell megvizsgálnunk, mert a fenti sorozatban előfordul négy páratlan számból álló négyes is (Q3) és két-két páros és páratlan számból állónak a két lényegesen különböző típusa is (Q1, ill. Q2). Ezekből 4-nél kevesebb lépésben jutunk Q4-höz. A hátra lévő P, P, P, U típus 1 lépésben a fenti Q1-re vezet, tehát 4 lépésben Q4-re.
Ezek szerint valóban legkésőbben minden 4. lépésben egyszerűsíthetünk D=2-vel, és így m is felére csökken. Ha előbb nem érjük el a 0, 0, 0, 0 számnégyest, akkor eljutunk egy olyan négyesre, mely már csak a 0 és 1 elemekből áll. Minden ilyen számnégyes megkapható a fent vizsgált típusokból, ha P helyére 0-t, U helyére 1-et írunk, és ekkor legkésőbben a 4. lépésben 0, 0, 0, 0-ra jutunk.
 
 Bóta Károly (Budapest, Steinmetz M. g. I. o. t.)