Kezdőlap


Feladat:	C.625	Korcsoport: 14-15	Nehézségi fok: könnyű
Füzet:	2001/december, 527. oldal		PDF \| MathML
Témakör(ök):	Partíciós problémák, Természetes számok, C gyakorlat
Hivatkozás(ok):	Feladatok: 2001/április: C.625

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.

A megrendelt csirkék darabszáma helyett ezentúl csak olyan egész számokról beszélünk, amelyek előállíthatók 6, 9 és 20 többszöröseinek összegeként.
A 6 és 9 többszöröseinek összegei a $6 a + 9 b = 3 (2 a + 3 b)$ alakú számok, ezek között minden $3 k$ ( $k \geq 2$ ) alakú szám előfordul, hiszen $2 a + 3 b$ alakban az 1-nél nagyobb $3 r$ , $3 r + 1$ , $3 r + 2$ alakú számok egyaránt felírhatók.
Ezért a $20 + 3 k$ alakú számok $k \geq 2$ esetén előállíthatók a kívánt módon, és ugyanez a $40 + 3 k$ alakú számokra is igaz. A 46-tól kezdve így minden szám előfordul, mert vagy többszöröse 3-nak, vagy ha $20 + 3 k$ alakú, akkor 3-mal osztva 2-t, míg ha $40 + 3 k$ alakú, akkor 3-mal osztva 1-et ad maradékul.
Kérdés, hogy 26 és 46 között sikerül-e minden számot előállítani? Azt állítjuk, hogy nem, a 43 kimarad, s ez egyben a legnagyobb olyan szám, amelyiket nem írhatunk fel 6, 9 és 20 többszöröseinek összegeként. A 45 a 9 többszöröse, a $20 + 3 k$ alakú számok ( $k \geq 2$ ):

\begin{matrix} 26, 29, 32, 35, 38, 41, 44, 47, ..., \end{matrix}

míg a

40 + 3 k

alakúak (

k \geq 2

) 46-tal kezdődnek. A többi (hiányzó) szám vagy többszöröse 3-nak, vagy kisebb 43-nál.
A 43 valóban nem bontható fel a kívánt módon, mert ha 1 db 20-as szerepel benne, akkor

43 = 20 + 23

, de 23 nem szerepel a

20 + 3 k

alakúak között

k \geq 2

miatt. Ha viszont 43-ban 2 db 20-as szerepel, akkor

43 = 20 + 20 + 3

, de 3 darabos csomag nincs.
Tehát a legnagyobb olyan darabszám, amit nem tudunk megrendelni, a 43.