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 file
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

Bizonyítsuk be, hogy minden pozitív egész szám egyértelműen írható föl "faktoriális alapú számrendszerben'', azaz tetszőleges pozitív egész A esetén egyértelműen léteznek olyan a1,a2,...,ak egész számok, amelyekre
0aii(i=1,2,...,k),(1)
másrészt
A=a11!+a22!+...+akk!.(2)

(k! az első k pozitív egész szorzatát jelöli, azaz k!=12...k.)

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=a11!+a22!+...+akk!=b11!+b22!+...+bkk!(3)
előállítása ( ak vagy bk esetleg 0), akkor legyen j a legnagyobb index, melyre ajbj. (3) átrendezéséből
|aj-bj|j!|a1-b1|1!+...+|aj-1-bj-1|(j-1)!.
A0aii,0bii feltételek miatt |ai-bi|i(i=1,2,1...), tehát
j!|aj-bj|j!11!+22!+...+(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={a11!+a22!+...+ak-1(k-1)!;0ai,i=1,2,...,k-1}
halmazt. Ennek minden eleme 0 és  11!+22!+...+(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 12...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=akk!+Ak,
ahol k választása szerint
0akk,másrészt0Ak<k!.
Most Ak-t osszuk el (k-1)!-sal s í. t.
Ak=ak-1(k-1)!+Ak-1,0ak-1k-1,0Ak-1<(k-1)!
Így valóban megkapjuk az a1,a2,...,ak "számjegyeket''.
Sokan nem utaltak azonban arra, hogy aii. 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,0a1<2,H1=3H2+a2,0a2<3,...Hk-1=kHk+ak,0ak<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+...+kak)...)és0aii
miatt a1 szükségképpen A-nak 2-vel való osztási maradéka (hiszen 2(a2+3(a3+...+kak)...) 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+c2a1+c3a1a2+...+cka1a2...ak
alakban, ahol 0ci<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, 0bkk.
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).