Pénzváltási probléma

A pénzváltási probléma egy több, matematikailag lényegesen eltérő változatban is megfogalmazható számelméleti probléma. Alapkérdése, hogy adott számokból mely számokat lehet előállítani szorzatösszeg (avagy lineáris kombináció) segítségével. Precízebben: ha adva van az A={a₁<a₂<a₃<...<a_n} halmaz, akkor az a kérdés, hogy mely számok írhatók fel $\sum _{i=1}^{n}m_{i}a_{i}$ alakban, ahol az m_i számok nem negatív egészek. Az a₂ számokról feltesszük, hogy relatív prímek. A problémát először Sylvester vetette fel 1884-ben.

A problémának vannak más változatai is, amikben a legnagyobb fel nem írható számot keresik, a számok prioritás szerint vannak rendezve, a számok csak korlátozott számban használhatók fel, vagy egy bizonyos számot kell előállítani. Egyes változatokban az érmek számát minimalizálják.

Példák

A nem felírható számok száma

• Két egymáshoz relatív prím számra a nem felírható számok száma (a₁-1)(a₂-1)/2.
• Legyen A=H teljes maradékrendszer modulo a₁, és jelölje r_h a h maradékosztály legkisebb felírható elemét! Ekkor a nem felírható számok száma ${\frac {1}{a_{1}}}\sum _{h\in H}r_{h}-{\frac {a_{1}-1}{2}}$.
• Ha az a_i számok d különbségű számtani sorozatot alkotnak, ahol a_n=a+(n-1)d, és a₁=a=p(n-1)+s, ahol 0≤s<n-1, akkor a nem felírható számok száma:

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

• Ha a₁=ab, a₂=bc, és a₃=ca, ahol a, b és c páronként relatív prímek, akkor a nem felírható számok száma:

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

• Legyenek n és t olyanok, hogy 1<n≤t, és t=q(n-1)+r, ahol 1≤r≤n-1! Ekkor a nem felírható számok száma:

${\frac {(t-n+r-1)q}{2}}$

A legnagyobb nem felírható szám

A legnagyobb nem felírható szám meghatározása nehéz kérdés, csak bizonyos megkötésekkel tudják becsülni, többnyire felülről.

• Erdős és Graham becslése a Kneser-tétel felhasználásával:

2a_n-1⌊a_n/n⌋-a_n.

• Rögzítsük n-et! Ekkor a₁, ..., a_n számok, amik egyike sem halad meg egy előre rögzített t értéket, szintén a Kneser-tétellel adódik, hogy a legnagyobb nem felírható szám legfeljebb (v-1)(t-r-1)-1, ahol t-1=v(n-1)-r, és 0≤r<n-1. Ez Dixmier eredménye.
• Ha n és k természetes számok, amikre k<n, akkor legfeljebb n olyan számot választva, amik nem nagyobbak n+k-nál, a lehető legnagyobb nem felírható szám éppen 2k-1.
• Ha n>2, akkor 2n-ig n számot véve a lehető legnagyobb nem felírható szám 2n+1.
• Ha n>2, akkor 2n+1-ig n számot véve a lehető legnagyobb nem felírható szám

2n+3, ha n+1 osztható 3-mal,

és 2n+5, ha n+1 nem osztható 3-mal.

• Legyenek most k és n olyanok, hogy n≥9k²+15k+2! Ekkor van n, egymáshoz relatív prím 2n+k+1-nél kisebb szám, amikre a legnagyobb fel nem írható szám:

2n+4k+1, ha n-k inkongruens 1-gyel modulo 3

2n+4k-1, ha n-k kongruens 1-gyel modulo 3.

A nem felírható számok összege

Mindezeken kívül még a nem felírható számok összegével is foglalkoznak.

Ha az a₁, ..., a_n számok relatív prímek, akkor a modulo a₁ maradékosztályok segítségével a nem felírható számok összege is meghatározható. Pontosabban, ha az x₂, ..., x_a1 modulo a_n redukált maradékosztályok legkisebb a₂, ..., a_n felhasználásával felírható elemét jelöli, akkor a nem felírható számok összege

$\sum _{j=1}^{a_{1}-1}\left({\frac {x_{j}^{2}}{2a_{1}}}-{\frac {x_{j}}{2}}+{a_{1}^{2}-1}{12}\right).$

Források

• Doktori értekezés a pénzváltási problémáról