Feladat: F.2163 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Laszip Ferenc 
Füzet: 1979/február, 64. oldal  PDF file
Témakör(ök): Számelrendezések, Természetes számok, Feladat
Hivatkozás(ok):Feladatok: 1978/október: F.2163

Van-e olyan nem negatív egészekből álló (n0,n1,...,nk) sorozat, hogy a sorozatban pontosan ni darab i szerepel (i=0,1,...,k) ? Mutassuk meg, hogy k=5 mellett nincs ilyen sorozat !

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.

Mivel a sorozatban pontosan ni darab i szerepel (i=0,1,...,k) és más számok nem fordulhatnak elő, ezért a sorozat elemeinek száma

n0+n1+...+nk=k+1.
A sorozatban kell lennie nullának, hiszen ha nem lenne, akkor n0=0 volna, azaz mégis szerepelne nulla. Tehát n00, így a sorozatban szerepel n0, továbbá pontosan n0 darab nulla és még (k-n0) darab pozitív egész szám. A sorozat tagjainak összege egyenlő az n0-nak és k-n0 darab pozitív egész számnak az összegével. Ez (k+1)-et kell hogy adjon, tehát (k-n0) pozitív egész szám összegének (k-n0+1)-gyel kell egyenlőnek lennie. Ez csak úgy lehetséges, ha (k-n0-1) darab egyest és 1 darab kettest adunk össze. Tehát a sorozat elemei csak a 0, 1, 2 és n0 közül kerülhetnek ki. A k=3, illetve k=4 esetben vannak ilyen sorozatok: (1,2,1,0), (2,0,2,0), illetve (2,1,2,0,0).
Ha k=5, akkor n0 nem lehet 1 vagy 2, mivel ekkor n3, n4, n5 közül valamelyik biztosan nem volna 0 (nincs három nullánk), így 3, 4 és 5 közül valamelyiknek szerepelnie kellene a sorozatban, ami ekkor nem lehetséges. n03 esetén a sorozatban van 1 darab n0-ás, így legalább 1 darab 1-es. De n1=1 nem lehet, hiszen akkor már két 1-esünk is volna. Ezért n1=2 és n21. Így n3, n4 és n5 közül csak kettő lehetne 0, de ez ellentmond n03-nak. k=5 mellett tehát nincs ilyen sorozat.
A k>5 esetben már tetszőleges k-ra létezik, mégpedig egyetlen megfelelő sorozat: n0=k-3, n1=2, n2=1, nn-3=1, egyébként ni=0.
 

 Laszip Ferenc (Cegléd, Kossuth L. Gimn., III. o. t.)