next up previous
Next: 4. A nem felírható számok Up: index Previous: 2. A pénzváltási probléma az

3. Az extremális Frobenius-probléma

A 3. fejezetet $ G(A)$ és $ g(n, t)$ vizsgálatának szenteljük. A legnagyobb nem felírható szám, $ G(A)$ meghatározása már $ n=3$ esetén is nagyon nehéz feladat. A pontos értékek csak speciális feltételek mellett adhatók meg, ezek-re több példát is mutatunk a 2. fejezetben. Talán éppen a nehézségek miatt a témakör fejlődése során előtérbe kerültek a különféle becslések. Tulajdonképpen ezen becslések kapcsán vezette be és kezdte vizsgálni 1971-ben ERDŐS az extremális $ g(n, t)$-t. Mivel fő eredményünk is ehhez a függvényhez kötődik, egy szakaszban teljes áttekintést adnuk a $ g(n, t)$-vel kapcsolatos eddigi kutatásokról.

Külön is kiemeljük DIXMIER 1990-es becslését [4]:


3.1.3. TÉTEL

$\displaystyle \left\lfloor\frac{t-2}{n-1}\right\rfloor(t-n+1)-1 \le g(n, t) \le
\left(\left\lceil\frac{t-1}{n-1}\right\rceil-1\right)t-1.
$


DIXMIER a felső becslést még élesebb formában is megadta, ennek számtalan következménye van, s szinte az összes korábban ismert eredményt is maga után vonja.


3.2.5. TÉTEL

$\displaystyle g(n, t) \le (v-1)(t-r-1)-1,$    ahol $\displaystyle t-1=v(n-1)-r$    és $\displaystyle 0 \le r < n-1.
$


A $ g(n, t)$ függvényre vonatkozó pontos eredmények két nagyobb csoportra oszthatók. A kisebb számok közül a régóta ismert $ n=2$ eset után $ n=3$-ra LEWIN adott pontos értéket az 1970-es évek elején. Az $ n=4$ és $ n=5$ eseteket DIXMIER [4] tételeiből kaphatjuk meg, kivéve a $ t=4k+3$ alakú számokat $ n=5$-nél. A nagyobb $ n$-ek esetében csak akkor voltak használható eredmények, ha a $ t$ értéke nem sokkal nagyobb, mint $ n$. A legáltalánosabb ezek közül ERDŐS és GRAHAM 1972-es tétele [6]:


3.2.3. TÉTEL Ha $ n$ és $ k$ pozitív egészek, $ n \ge 9k^2+15k+2,$ akkor

$\displaystyle g(n, 2n+k)= \left\{ \begin{gathered}2n+4k+1,\text{ } \text{ ha } ...
...\\
2n+4k-1, \text{ }\text{ ha } n-k \equiv 1 \pmod{3}. \end{gathered} \right.$


Erre a tételre LEV is adott egy eltérő bizonyítást, amelyben elegendő a
$ k \le {n-2}$ megkötés. Fő eredményünk ennek a tételnek az általánosítása, $ g(n, dn+k)$ pontos értékének meghatározása két maradékosztályra mod $ (d+1)$ [16]:


3.3.1. TÉTEL Legyenek a $ d, n, k$ olyan természetes számok, hogy
$ 2 \le d < n,$    $ 0 \le k \le n-d.$ Ha $ n-k \equiv 0 \pmod {d+1}$    vagy $ n-k\ \equiv -1 \pmod {d+1}$, akkor

$\displaystyle g(n, dn+k)=d(d-1)n+2dk+d^2-d-1.
$


A tétel segíségével néhány további speciális esetben is kiszámítható a $ g(n, t)$. Pl.


3.4.2. KÖVETKEZMÉNY Legyenek $ n$ és $ k$ olyan pozitív egészek, hogy $ n > 3$, $ 0 \le k \le n-3.$ Ha $ n-k \equiv 0 \pmod {4}$$ \text { vagy } n-k \equiv -1 \pmod {4}$, akkor

$\displaystyle g(n, 3n+k)= 6n+6k+5.
$



next up previous
Next: 4. A nem felírható számok Up: index Previous: 2. A pénzváltási probléma az
root 2004-12-04