Feladat: Gy.2417 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Balogh 171 J. ,  Beke T. ,  Benkő D. ,  Benkő P. ,  Bukszár J. ,  Buttyán L. ,  Csirik J. ,  Csordás Z. ,  Farkas J. ,  Hajnal Z. ,  Károlyi A. ,  Károlyi Gy. ,  Kecskés K. ,  Keleti T. ,  Kondacs A. ,  Lois L. ,  Macskási Zs. ,  Máté N. ,  Mekis A. ,  Mezei J. ,  Németh G. ,  Peller Z. ,  Péter I. ,  Pór A. ,  Rockenbauer E. ,  Sustik M. ,  Szabó T. ,  Tavaszi G. 
Füzet: 1987/december, 453 - 455. oldal  PDF  |  MathML 
Témakör(ök): Indirekt bizonyítási mód, "a" alapú számrendszer (a >1, egész szám), Gyakorlat
Hivatkozás(ok):Feladatok: 1987/május: Gy.2417

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.

Először megmutatjuk, hogy minden pozitív egész szám legfeljebb egyféleképpen állhat elő a kívánt alakban. Ha egy A számnak volna két különböző

A=a1⋅1!+a2⋅2!+...+ak⋅k!=b1⋅1!+b2⋅2!+...+bk⋅k!(3)
előállítása ( ak vagy bk esetleg 0), akkor legyen j a legnagyobb index, melyre aj≠bj. (3) átrendezéséből
|aj-bj|j!≦|a1-b1|1!+...+|aj-1-bj-1|⋅(j-1)!.
A0≦ai≦i,0≦bi≦i feltételek miatt |ai-bi|≦i(i=1,2,1...), tehát
j!≦|aj-bj|j!≦1⋅1!+2⋅2!+...+(j-1)(j-1)!==(2!-1!)+(3!-2!)+...+(j!-(j-1)!)=j!-1,


ami ellentmondás.
A továbbiakban bebizonyítjuk, hogy minden pozitív szám elő is áll a keresett alakban, amihez elegendő megmutatni, hogy tetszőleges k-ra minden k!-nál kisebb szám előállítható.
Tekintsük a
H={a1⋅1!+a2⋅2!+...+ak-1⋅(k-1)!;0≦ai,i=1,2,...,k-1}
halmazt. Ennek minden eleme 0 és  1⋅1!+2⋅2!+...+(k-1)(k-1)!=k!-1  között van. Minden egyes ai egymástól függetlenül (i+1) különböző értéket vehet fel, így H-nak 1⋅2⋅...⋅k=k! eleme van, s az előbb igazolt egyértelműség miatt ezek mind különbözők. Mivel 0-tól k!-1-ig éppen k! darab szám van, tehát H={0,1,2,...,k!-1.}, s ezzel az állítást beláttuk.
 

Megjegyzések: 1. Az egyértelműség természetesen úgy értendő a feladatban, ahogyan azt számrendszerek esetében megszoktuk, tehát a felesleges "vezető'' 0 számjegyektől eltekintünk. Egész szigorúan véve (3)-ban nem lett volna szabad a két különböző felírást azonos hosszúságúnak tekinteni, de nullákkal kiegészítve ez nyilván mindig feltehető.
2. Természetesen konstruktív úton is elő lehet állítani egy adott A szám  a1,a2,...,ak "számjegyeit'':
Legyen k a legnagyobb olyan szám, melyre k!≦A. Osszuk el A-t k!-sal maradékosan, azaz legyen
A=ak⋅k!+Ak,
ahol k választása szerint
0≦ak≦k,másrészt0≦Ak<k!.
Most Ak-t osszuk el (k-1)!-sal s í. t.
Ak=ak-1(k-1)!+Ak-1,0≦ak-1≦k-1,0≦Ak-1<(k-1)!⋮
Így valóban megkapjuk az a1,a2,...,ak "számjegyeket''.
Sokan nem utaltak azonban arra, hogy ai≦i. Mások pedig a maradékos osztás egyértelműségére hivatkoztak az előállítás egyértelműségének "bizonyításakor'', ami pedig nem elegendő.
3. El lehet kezdeni az ai-k meghatározását a másik irányból is: A-t osszuk el maradékosan 2-vel, majd a hányadost 3-mal, s í. t.:
A=2H1+a1,0≦a1<2,H1=3H2+a2,0≦a2<3,...Hk-1=kHk+ak,0≦ak<k.

Nyilván A>H1>H2..., és legyen Hk=0.
Könnyen igazolható, hogy az így kapott a1,a2,...,ak számok megfelelnek. Itt sem elegendő azonban a maradékos osztás egyértelműségére hivatkozni; ki kell egészíteni azzal, hogy
A=a1+2(a2+3(a3+...+k⋅ak)...)és0≦ai≦i
miatt a1 szükségképpen A-nak 2-vel való osztási maradéka (hiszen 2(a2+3(a3+...+k⋅ak)...) páros), a2 szükségképpen H1-nek 3-mal vett osztási maradéka, s í. t.
4. A feladatban kimondott tétel tovább általánosítható a következő formában:
Adott a1,a2,... egynél nagyobb egészek mellett minden A pozitív egész szám egyértelműen áll elő
A=c1+c2⋅a1+c3⋅a1⋅a2+...+ck⋅a1⋅a2⋅...⋅ak
alakban, ahol 0≦ci<ai(i=1,2,...).
 

5. Igaz az is, hogy minden 0 és 1 közötti r racionális szám egyértelműen áll elő
r=b12!+b23!+...+bn(n+1)!
alakban, ahol bk egész, 0≦bk≦k.
Ez azt is mutatja, hogy a faktoriális alapú számrendszerben pontosan azok a számok racionálisak, amelyek véges sok "jeggyel'' felírhatók (szemben a végtelen tizedestört alakú racionális számokkal a tízes számrendszerben).