Keressük a legnagyobb nem felírható számot!

Először az 1982/1983-as tanévben találkozhattunk tanulmányi versenyen is pénzváltási feladattal.

FELADAT 1   (Nemzetközi Matematikai Diákolimpia, Párizs) [25]

Legyenek $a, b, c$ páronként relatív prím pozitív egész számok. Mutassuk meg, hogy

$$abc-ab-bc-ca$$

az a legnagyobb egész szám, amely nem írható fel

$$xbc+yca+zab$$

alakban, ahol $x, y, z$ nemnegatív egész számokat jelölnek.

FELADAT 2   (Műszaki Főiskolások Hajós György Versenye, Budapest) Valaki azt javasolta, hogy verjenek a jelenlegieken kívül háromforintos pénzdarabokat is. Javaslatát azzal indokolta, hogy pusztán 3 és 5 forintosokkal bármekkora pénzösszeg kifizethető visszaadás nélkül, ha az egész számú forintból áll, és 7 Ft-nál több. Igaz-e ez az állítás?

Mindkét feladat speciális esete a számelméleti Frobenius-problémá-nak, amelyet általánosan a következőképpen szokásos megadni: Legyenek $a_1<a_2< \dots < a_n$ pozitív egészek úgy, hogy $(a_1,\dots , a_n)=1.$ Keressük meg azt a legnagyobb $K$ pozitív egész számot, amelyre a $K=\sum _{i=1}^n x_ia_i$ egyenlet nem oldható meg nemnegatív egész $x_i$-kben. Ezt a legnagyobb pozitív egész számot $G(a_1,\dots , a_n)$-nel, míg az ösz-szes olyan $K$ pozitív egészek számát, amelyre a $K=\sum _{i=1}^n x_ia_i$ egyenlet így nem oldható meg, $N(a_1,\dots , a_n)$-nel jelöljük.

Mielőtt további feladatokra térnénk, oldjuk meg a 2. feladatot. Az új jelölésekkel azt kell igazolni, hogy $G(3,5)=7.$ A $3$ többszörösei természetesen kifejezhetők, felírhatók. Ugyanez igaz az $5$-től kezdve azokra a számokra, amelyek hárommal osztva kettőt adnak maradékul. A legkisebb olyan szám, amely hárommal osztva egyet ad maradékul a $10$ lesz. Az egyes maradékosztályokban mod $3$ a legkisebb nem felírható elemek, a fentiek alapján rendre a $-3, 7, 2.$ Ezek közül a legnagyobb a $7.$    $\blacksquare$

Analóg gondolatmenettel igazolható, hogy

FELADAT 3   $G(a_1,a_2)=(a_1-1)(a_2-1)-1,$ ha $(a_1, a_2)=1.$

A megoldáshoz fel kell használni, hogy amennyiben $(a_1, a_2)=1$ és $a_1<a_2,$ akkor $0, a_2, 2a_2, \ldots , (a_1-1)a_2$ mindegyik maradékosztályból pontosan egy elemet tartalmaz mod $a_1.$ Ezt a továbbiakban teljes maradékrendszernek nevezzük.

Nem magától értetődő, hogy több $a_i$ esetén is mindig van legnagyobb nem felírható szám.

FELADAT 4   Amennyiben $(a_1,\dots , a_n)=1,$ mindig van olyan
$G(a_1,\dots , a_n)$ szám, amelyre teljesül, hogy $K>G(a_1,\dots , a_n)$ esetén a $K=\sum _{i=1}^n x_ia_i$ diofantoszi egyenlet megoldható nemnegatív egészekben.

Ez a Frobenius problémakör alaptételének is nyugodtan nevezhető feladat a Középiskolai Matematikai Lapokban 1997-ben VÍZVÁRI BÉLA [32] cikkeihez kapcsolva került kitűzésre. A feladat állítását $n$-re vonatkozó teljes indukcióval igazoljuk. Az $n=2$ esetet az előbb vázoltuk. Ha $n > 2$, akkor tegyük fel, hogy $k$-ig már igaz az állítás és vizsgáljuk meg $k+1$-re. Legyen most az $n=k+1$ esetben az első $k$ darab szám legnagyobb közös osztója $d.$ Ekkor az indukciós feltevés szerint az $\frac {a_1} {d}, \frac{a_2}{d}, \ldots ,\frac {a_k}{d}$ számokkal véges sok kivétellel minden pozitív egész szám felírható a kérdéses alakban. Így létezik olyan $u$, hogy $(u, a_{k+1})=1$ és $u= v_1\frac {a_1} {d}+v_2\frac{a_2}{d} + \ldots + v_k \frac {a_k}{d}$, ahol $v_1, v_2, \ldots, v_k$ nemnegatív egészek. Mivel $d$ és $a_{k+1}$ relatív prímek, ellenkező esetben az $a_1, a_2, \ldots , a_{k+1}$ számoknak lenne $1$-nél nagyobb közös osztója, ezért $ud$ és $a_{k+1}$ is relatív prímek. A fentiek szerint $n=2$ esetén az állítás igaz, azaz véges sok kivétellel minden pozitív egész szám felírható

$$x_1du+x_2a_{k+1}=x_1v_1a_1+x_1v_2a_2+ \ldots +x_1v_ka_k+x_2a_{k+1}$$

alakban, ahol $x_1v_1, x_1v_2, \ldots , x_1v_k, x_2$ nemnegatív egészek.  $\blacksquare$

Annak ellenére, hogy ez az általános eredmény gyakorlatilag az eredeti probléma felvetődése óta ismert, a legtöbb konkrét esetben nehéz feladatnak bizonyult $G(a_1,\dots , a_n)$ pontos meghatározása. Már három különböző címlet esetén sem adható meg általános formula. Az újabb címlet engedélyezése vagy egyáltalán nem befolyásolja a legnagyobb nem felírható számot (mert esetleg valamelyik korábbi címlet több-szöröse vagy nagyobb a többivel nem felírható legnagyobb számnál), vagy az újabb kombinációs lehetőségek miatt lényegesen csökkenti azt. Ebben az esetben az egyes maradékosztályokban a felírható legkisebb reprezentánsok szerkezete szinte áttekinthetetlenné válik.

A publikációk egy jelentős részében éppen ezért különféle speciális feltételeket adnak meg a szerzők, annak érdekében, hogy ez a szerkezet kezelhető legyen. Ez tulajdonképpen a feladatok készítésének lehetősége is. Vizsgáljuk meg most a három szomszédos páratlan szám esetét.

FELADAT 5   Határozzuk meg $G(2k+1, 2k+3, 2k+5)$-öt!

A feladat megoldásához a kulcsot megtaláljuk, amennyiben modulo $2k+1$ tekintjük a másik két szám lehetséges maradékait. Ezek mindegyik lineáris kombináció esetében a $2$ és a $4$ többszörösei lesznek. A $0, 2, 4, \ldots, 4k$ teljes maradékrendszert alkotnak modulo $2k+1.$ A legnagyobb maradék eléréséhez a $2k+5$ elemet pontosan $k$-szor kell vennünk (illetve, ha helyette néhányszor két darab $2k+3$-at ve-szünk, akkor ,,rosszabbul'' járunk). Legfeljebb ugyanennyi elemből a kisebb maradékok is előállíthatók, így a legnagyobb nem felírható elem $G(2k+1, 2k+3, 2k+5)=k(2k+5)-(2k+1)=2k^2+3k-1.$    $\blacksquare$

Hasonló gondolatmenettel ROBERTS [26] 1956-ban igazolta, hogy

FELADAT 6   Alkossanak az $a_i$-k növekvő számtani sorozatot,
$a_1=a, a_2=a+d, \ldots , a_n=a+(n-1)d$, ahol $(a,d)=1.$ Ekkor

$$G(a_1,a_2, \ldots ,a_n)=\left\lfloor\frac{a-2}{n-1}\right\rfloor a + (a-1)d.$$

Az 1960-as évektől kezdődően a matematikusok körében kedvelt lett ez a téma és igen sok speciális esetben kiszámították $G(a_1,\dots , a_n)$ pontos értékét. Két fontos központ is kialakult: az egyik a német HOFMEISTER, a másik a norvég SELMER irányításával. A témakörben megjelent cikkek legfontosabb eredményeiről teljes áttekintést ad RAMÍREZ ALFONSÍN [23] 2000-ben Bonnban megjelent, illetve azóta jelentősen kibővített [24] összefoglaló munkája. E szakasz lezárásaként oldjuk meg az első feladatot, amely nehézségi fokával, a megoldási módszerekkel és harmonikus szerkezetével vélhetően sokat elárul a Frobenius-probléma szépségeiből.

Először azt látjuk be, hogy $T=2abc-ab-bc-ca$ nem írható fel $xab+ybc+zca$ alakban, ahol $x, y$ és $z$ nemnegatív egész számok. Ha ui. felírható lenne;

$$xbc+yca+zab=2abc-ab-bc-ca,$$

akkor

$$(x+1)bc+(y+1)ca+(z+1)ab=2abc$$

teljesülne. Mivel pl. $bc$ és $a$ relatív prímek, így az $a$ osztója $x+1$-nek, ezért $a \le x+1;$ hasonlóan $b \le y+1$ és $c \le z+1,$ amiből

$$2abc=(x+1)bc+(y+1)ca+(z+1)ab \ge 3abc$$

következne, ami nyilvánvalóan ellentmondás.

Megmutatjuk viszont, hogy tetszőleges $t'$ pozitív egész esetén vannak olyan $X, Y$ és $Z$ pozitív egész számok, amelyekre

$$Xbc+Yca+Zab=2abc+t'$$

fennáll, s ez a fentiek alapján elegendő az állítás igazolásához, illetve ez átfogalmazható úgy, hogy minden $t>2abc$ egész felírható
$Xbc+Yca+Zab=t$ alakban, ahol $X, Y$ és $Z$ pozitív egészek.

Induljunk ki abból, hogy a

$$bc, 2bc, 3bc, \ldots , (a-1)bc, abc$$

számok $a$-val való osztási maradéka mind különböző, tehát teljes maradékrendszert alkotnak mod $a$, és így egyikük, pl. $x_1bc$ ugyanabba a maradékosztályba tartozik mod $a$, mint $t,$ tehát

$$x_1bc \equiv t \pmod{a},$$        $$1 \le x_1 \le a.$$

Hasonlóan kapjuk, hogy léteznek olyan $y_1$ és $z_1$ egészek, amelyekre

$$y_1ca \equiv t \pmod{b},$$        $$1 \le y_1 \le b,$$

$$z_1ab \equiv t \pmod{c},$$        $$1 \le z_1 \le c.$$

Ez azt eredményezi, hogy

$$(x_1bc-t)+y_1ca+z_1ab=x_1bc+y_1ca+z_1ab-t$$

osztható $a$-val, és hasonlóan $b$-vel és $c$-vel is, illetve mivel páronként relatív prímek, $abc$-vel is osztható, tehát

$$s=x_1bc+y_1ca+z_1ab \equiv t \pmod{abc}.$$

Ez azt is jelenti, hogy $s$-nek és $t$-nek, tehát $s-1$-nek és $t-1$-nek is ugyanaz az osztási maradéka mod $abc$, azaz

$$t-1=q\cdot abc+r,$$

$$s-1=q'\cdot abc+r$$        $$(0 \le r < abc),$$

ahol $t>2abc$ miatt $q \ge 2$ és az $x_1,y_1,z_1$ számokra tett nagyságrendi kikötések miatt $s \le 3abc,$ és ennek megfelelőn $q' \le 2.$ A két előző egyenlet különbségéből adódik, hogy

$$t-s=(q-q')abc,$$

$$t=s+(q-q')abc=(x_1+(q-q')a)bc+y_1ca+z_1ab,$$

ezzel az állítást igazoltuk, hiszen $X=x_1+(q-q')a, Y=y_1, Z=z_1$ választással éppen három pozitív egészet kapunk.  $\blacksquare$

Egy kis kitérővel maradjunk még ennél a feladatnál. Egy általánosabb eredmény lerövidítheti, megkönnyítheti munkánkat, ugyanakkor kevésbé láthatjuk, érzékelhetjük a valódi problémát.

JOHNSON [14] 1960-ban tette közzé a következő könnyen értelmezhető és belátható állítást:

FELADAT 7   Legyenek az $a_1, a_2, a_3$ relatív prím pozitív egészek és $d=(a_1, a_2)$ az első két szám legnagyobb közös osztója. Ekkor

$$G(a_1, a_2, a_3)=d \cdot G \left (\frac{a_1}{d}, \frac {a_2}{d}, a_3\right) + (d-1)a_3.$$

Maga az állítás első közelítésben nem is tűnik érdekesnek, de egy-részt nagy mértékben általánosítható, másrészt alkalmazásával az 1. feladat gyors megoldásához jutunk. Felhasználjuk még itt azt is, hogy $ab > G(a, b)=ab-a-b$, s emiatt $G(b, a, ab)=G(a, b).$

$$G(bc, ca, ab)=c \cdot G(b, a, ab)+(c-1)ab=$$

$$=c(ab-a-b)+(c-1)ab=2abc-ab-bc-ca.$$