Feladat: Gy.2249 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1985/október, 312. oldal  PDF file
Témakör(ök): Kombinatorika, Konstruktív megoldási módszer, Számsorozatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1985/február: Gy.2249

Sorbarendezhető-e az első húsz nemnegatív egész szám úgy, hogy ha két ilyen szám utolsó jegye k, akkor köztük éppen k darab szám álljon a sorban?

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.

Belátjuk, hogy a feladat kérdésére a válasz tagadó. Tegyük fel ugyanis, hogy létezik a megfelelő sorozat, és jelöljük ai-vel az i szám sorszámát ebben a sorozatban (i=0, 1, 2, ..., 19). Ekkor az a0, a1, ..., a19 felsorolás az első 20 pozitív egész valamilyen sorrendben, ezért

a0+a1+...+a19=1+2+...+20=210.(1)

A feltétel szerint másfelől
|a0-a10|+|a1-a11|+...+|a9-a19|=1+2+...+10=55.(2)

Ha most P és N jelöli a (2) bal oldalán az abszolút érték jelek felbontása után pozitív, illetve negatív előjellel álló számok összegét, akkor (1) szerint P+N=210, (2)-ből pedig kapjuk, hogy P-N=55. Innen 2P és 2N páratlannak adódik, ami nem lehet, hisz P és N egész számok. Ez azt jelenti, hogy valóban nem létezik a mondott tulajdonságú sorozat.
 

Megjegyzés. A feladat lényegében a következő probléma speciális esete: létezik-e olyan 2n hosszúságú sorozat, amelyben a 0, 1, ..., n-1 számok mindegyike pontosan kétszer fordul elő, és bármelyik k szám két előfordulása között pontosan k darab szám szerepel a sorozatban? A bizonyításból kiolvasható, hogy ilyen sorozat létezéséhez szükséges, hogy az (n+1)-től (2n-1)-ig terjedő egészek összege páros legyen, ami azt jelenti, hogy n-nek 4-gyel osztva 0 vagy 1 maradékot kell adnia. Nem látszik könnyű kérdésnek, hogy a talált feltétel elégséges-e.
Mindenesetre n=1, 4, 5, 8 és 9 esetén ilyen elrendezés létezik: 00, 2132003, 0023421314, 2412174635003765, 141008473625328765.