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 , , , számnégyest -vel, a benne előforduló legnagyobb értéket -vel . A képezési szabály szerint világos, hogy ha legalább , akkor egyik száma sem negatív, és ennek folytán , ugyanis számai két-két -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 , akkor a negyedik lépésig legkésőbb határozottan csökken a négyes legnagyobb száma: ha , akkor . Ebből nyilvánvaló, hogy a nem negatív egész számokból álló számsorozatban véges számú lépés után fellép egy tag, ez pedig azt jelenti, hogy a megfelelő számnégyes minden tagja . Bizonyításunk egyszerűbb lesz a következő két észrevétel felhasználásával. képezése mutatja, hogy -t és -t az eredeti számnégyesben ugyanúgy szomszédos tagoknak tekinthetjük, mint pl. -t és -t. Ezért a , , , 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 , , , négyesből képezett sorozatra. Ezek alapján bármely index esetén tetszés szerinti tagját tekinthetjük -nek, szomszédai egyikét -nek, a szomszéd másik szomszédját -nek, így a hátra levő tag gyanánt szomszédja lesz az először kiválasztott tagnak, amint az eredeti elrendezésben is az volt. Ha -ben nem szerepel értékű elem szomszédjaként , akkor már , s így biztosan . Elég tehát azt az esetet vizsgálni, ha van -ben egy értékű elem mellett . Az előrebocsátott megjegyzések szerint feltehetjük, hogy ilyen alakú: ahol és nem negatív egészek és nem nagyobbak -nél. Ekkor az számnégyes lesz. -ben csak akkor nem lesz minden szám kisebb, mint , ha -ben előfordul egymás mellett az és érték, tehát vagy vagy , vagy pedig és e mellett és egyike -vel egyenlő, vagyis vagy . 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 a , , , , vagy az , , , négyes, és a kettő nem különbözik lényegesen ( és játszik azonos szerepet a két négyesben). Elég tehát az első négyessel foglalkozni. Ekkor az négyes. Itt és érték egymás mellett csak úgy szerepelhet, ha , minden más esetben számai kisebbek -nél. Ha pedig akkor az négyes, így és az négyes. Az állításnál valamivel élesebben azt kaptuk tehát, hogy vagy már csupa -ból áll, vagy már . 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 számnégyes mindegyik száma osztható egy számmal, akkor a számok különbségei is oszthatók -vel: a megfelelő két szám -ed része különbségének a -szeresei. Így, ha a négyes számainak a -ed részéből alkotott négyes , akkor -ból és -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ő , 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 -vel egyszerűsíthetünk. Elég lesz evégett a páros számok helyére -t, a páratlanok helyére -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: | | á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.) |