A nem felírható számok számáról

SYLVESTER [30] 1884-ben megjelent problémái között szerepelt az előző fejezet 3. feladatához kapcsolódó kérdés felvetése és megoldása.

FELADAT 8   Legyen két különböző címletű érménk és ezekből elegendően sok. Határozzuk meg azoknak a pozitív egészeknek a számát, amelyek nem ,,fizethetők ki'' ezen kétféle érme segítségével maradék nélkül.

A korábbi jelölésekkel $N(a_1,a_2)$ pontos értékét keressük. A meg-oldáshoz felhasználjuk, hogy

$$a_2, 2a_2, \ldots , (a_1-1)a_2$$

minden nullától különböző maradékot tartalmazó maradékrendszert alkot mod $a_1.$ Az egyes maradékosztályokban ezek a felsorolt elemek lesznek a legkisebb felírhatók, továbbá tudjuk, hogy ezek a számok éppen az $1, 2, \ldots , (a_1-1)$ egy permutációjának elemeivel lesznek rendre kongruensek mod $a_1.$ Legyen ez a permutáció $k_1, k_2, \ldots ,k_{a_1-1}.$ Ekkor a $t \cdot a_2$ maradékosztályban a nem felírható elemek száma pontosan

$$\left\lfloor \frac {t \cdot a_2} {a_1}\right \rfloor = \frac {t \cdot a_2 -k_t} {a_1}.$$

Ezeket a számokat összegezve az összes nemnulla maradékosztályra megkapjuk a nem felírható elemeket:

$$\frac {a_2-t_1}{a_1}+ \frac {2a_2-t_2}{a_1} + \ldots + \frac {(a_1-1)a_2-t_{a_1-1}}{a_1}=$$

$$=\frac {(1+2+\ldots+(a_1-1))a_2 -(t_1+t_2+\ldots+t_{a_1-1})}{a_1}=$$

$$=\frac {(1+2+\ldots+(a_1-1))(a_2-1)}{a_1}=\frac {(a_1-1)(a_2-1)}{2}.$$    $$\blacksquare$$

SELMER [28] az előbbi módszert általánosan alkalmazta. Legyen $H$ egy teljes maradékrendszer mod $a_1.$ Minden $h \in H$-hoz van olyan $r_h \equiv h \pmod {a_1}$, amely felírható $r_h=a_2y_2 + a_3y_3 + \ldots + a_ny_n$ alakban és a legkisebb. Ezekkel a jelölésekkel

$$N(a_1, a_2, \ldots ,a_n)=\frac {1}{a_1} \sum_{h \in H} {r_h} -\frac {a_1-1}{2}.$$

Alkalmazzuk ezt az interpretációt további feladatokban is.

FELADAT 9   Alkossanak az $a_i$-k számtani sorozatot, azaz $a_1=a$, $a_2=a+d, \ldots , a_n=a+(n-1)d.$ Legyen továbbá $a-1=p(n-1)+s$, ahol $0 \le s < n-1.$ Ekkor

$$N(a_1, a_2, \ldots ,a_n)=\frac {1}{2}((a-1)(p+d)+s(p+1)).$$

Először az egyes osztályokba tartozó legkisebb $r_h$ maradékokat kell megadnunk. $0, d, 2d, \ldots ,(a-1)d$ teljes maradékrendszert alkot $\mod$    $a$. A célunk az, hogy a legnagyobb maradékot is a legkevesebb $a_i$ felhasználásával állítsuk elő. Ennek érdekében az $a_n$-et, amelynek maradéka $(n-1)d,$ a lehetséges legnagyobb szorzóval vesszük:

$$p(n-1) \le a-1 < (p+1)(n-1).$$

Ez alapján

$$(a-1)=p(n-1)+s;$$  $$0 \le s <n-1.$$

Ennek megfelelően $pa_n+a_{s+1}$ maradéka megegyezik $(a-1)d$ maradékával mod $a.$ Az $r_h$ rendszer táblázatba rendezhető:

$$\begin{matrix}a_2 & a_3 & \ldots & a_{n-1} & a_n \\ a_2+a_n & a_... ... a_{n-1} +(p-1)a_n & pa_n \\ a_2+pa_n & \ldots & a_{s+1}+pa_n. \end{matrix}$$

Az utolsó sor csak akkor szükséges, ha $s > 0.$
A táblázatban a $d$ többszöröseinek összege az eredeti felírás alapján:

$$d+2d+ \ldots +(a-1)d=d\frac{a(a-1)}{2}.$$

Az $a$ többszöröseinek összegére:

$$(n-1)a+2(n-1)a+ \ldots +p(n-1)a+(p+1)sa=$$

$$=a \left( \frac {(n-1)p(p+1)}{2}+(p+1)s\right).$$

$$N(a_1, a_2, \ldots ,a_n)=\frac {1}{a} \sum_{h \in H} r_h-\frac {a-1}{2}=$$

$$=\frac {(n-1)p(p+1)}{2}+(p+1)s+\frac{(a-1)}{2}(d-1)=$$

$$=\frac{1}{2}\left((p+1)(p(n-1)+2s)+(d-1)(a-1)\right)=$$

$$=\frac{1}{2}\left((a-1)(p+d)+s(p+1)\right).$$    $$\blacksquare$$

Ezzel az állítást igazoltuk, sőt a táblázatból kiolvasható, hogy a legnagyobb nem felírható szám $s>0$ esetén

$$a_{s+1}+pa_n-a=a+sd+pa+p(n-1)d-a=pa+(a-1)d.$$

Amennyiben $s=0$, a legnagyobb nem felírható számra azt kapjuk, hogy

$$pa_n-a=pa+p(n-1)d-a=(p-1)a+(a-1)d.$$

A két formula írható azonos alakban, mivel $s>0$-ra

$$\left\lfloor\frac {a-1}{n-1}\right\rfloor=\left\lfloor\frac {a-2}{n-1}\right\rfloor=p,$$$$\text { illetve } s=0 \text { esetén} \left\lfloor\frac {a-2}{n-1}\right\rfloor=p-1.$$

Ezzel a 6. feladat állítását is beláttuk.  $\blacksquare$

Következő, kevésbé ismert eredményünk az 1. feladathoz kapcsolódik.

FELADAT 10   Legyenek $a, b, c$ páronként relatív prím pozitív egész számok. Mutassuk meg, hogy azoknak a számoknak a száma, amelyek nem írhatók fel $xbc+yca+zab$ alakban, ahol $x, y, z$ nemnegatív egész számok,

$$N(bc, ca, ab)= \frac {2abc-bc-ca-ab+1}{2}.$$

Ebben az esetben is áttekinthetően megadhatjuk mod $ab$ az egyes maradékosztályokban a $bc$ és $ca$ segítségével felírható legkisebb elemeket:

$$\begin{matrix}0 & bc & 2bc & \ldots & (a-1)bc \\ ca & bc+ca & 2b... ...\ (b-1)ca & bc+(b-1)ca & 2bc +(b-1)ca & \ldots & (a-1)bc+(b-1)ca. \end{matrix}$$

A táblázatban pontosan $ab$ darab szám szerepel. Elegendő tehát belátnunk, hogy páronként inkongruensek mod $ab.$ Ellenkező esetben

$$x_1bc+y_1ca \equiv x_2bc+y_2ca \pmod {ab}.$$

Ez pontosan azt jelenti, hogy

$$x_1bc+y_1ca- x_2bc+y_2ca=(x_1-x_2)bc+(y_1-y_2)ca$$

osztható $ab$-vel.

Azonnal látható, hogy az oszthatósági tulajdonságok miatt $x_1-x_2$ osztható lesz $a$-val, $y_1-y_2$ pedig $b$-vel. Mivel $0 \le x_1, x_2 \le a-1$ és $0 \le y_1, y_2 \le b-1$, az oszthatóság csak $x_1=x_2$, valamint $y_1=y_2$ esetében lehet igaz.

Adjuk most össze a reprezentánsokat:

$$\sum_{i=0}^{a-1} \sum_{j=0}^{b-1} (ibc+jca)=\frac {a(a-1)b^2c}{2} +\frac {b(b-1)a^2c}{2}=$$

$$=\frac{abc}{2}\left[b(a-1)+a(b-1)\right].$$

Alkalmazzuk a Selmer-féle formulát:

$$N(ab, bc, ca)=\frac{1}{ab}\cdot \frac{abc}{2}\left[a(b-1)+b(a-1)\right]- \frac {ab-1}{2}=$$

$$=\frac{2abc-ab-bc-ca+1}{2}.$$    $$\blacksquare$$

A nem felírható számok meghatározása során tulajdonképpen egy harmadik megoldást nyertünk az 1. feladatra, mivel láthatóan a legnagyobb $r_h$ $\mod$    $ab$ pontosan $(a-1)bc+(b-1)ca$ lesz. Innen rögtön felírhatjuk, hogy

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

Az $N(a_1, a_2, \ldots ,a_n)$-et a $G(a_1, a_2, \ldots ,a_n)$-hez viszonyítva érdekes
megfigyelést tehetünk. Összehasonlítva az 1. és 10. feladat, továbbá a 3. és 8. feladat formuláit, azt látjuk, hogy

$$N(a_1, a_2, \ldots ,a_n)=\frac {G(a_1, a_2, \ldots ,a_n)+1}{2}.$$

Fontos határeseteit kaptuk NIJENHUIS és WILF [22] tételének, akik annak az egyszerű ténynek a felismerése alapján, hogy tetszőleges olyan $x$ és $y$ pozitív egészek közül, amelyek összege $G(a_1, a_2, \ldots ,a_n)$, legfeljebb az egyik lehet felírható az $a_1, a_2, \ldots , a_n$ segítségével, kapták, hogy

$$N(a_1, a_2, \ldots ,a_n) \ge \frac {G(a_1, a_2, \ldots ,a_n)+1}{2}.$$

Felső becslésként azonnal adódik, hogy

$$N(a_1, a_2, \ldots ,a_n) \le G(a_1, a_2, \ldots ,a_n).$$

Ez a becslés nem is javítható, hiszen

$$a_1=k,$$     $$a_2=k+1,$$     $$a_3=k+2, \ldots ,a_k=2k-1$$

választással pontosan $N(a_1, a_2, \ldots ,a_n)=G(a_1, a_2, \ldots ,a_n)=k-1.$