Kezdőlap


Feladat:	C.449	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Babos Attila , Ballók István , Barabás Zsolt , Fehér Ágnes , Fehér Lajos Károly , Gyimesi Andrea , Hegedűs Ákos , Hegedűs Miklós , Horváth Gábor , Horváth György , Jáger Márta , Joó Dániel , Krenedits Sándor , Kunszenti-Kovács Dávid , Lisznyai Erika , Monos András , Pomozi Olivér , Pozsonyi Tamás , Sarlós Ferenc , Szöllősi Loránd , Taraza Busra , Terpai Tamás , Tirpák Miklós , Végh László
Füzet:	1997/május, 274 - 276. oldal		PDF \| MathML
Témakör(ök):	Természetes számok, Partíciós problémák, Oszthatósági feladatok, C gyakorlat
Hivatkozás(ok):	Feladatok: 1996/december: C.449

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 feladat a matematika nyelvére átfogalmazva azt jelenti, hogy az $n$ természetes számot 3 különböző természetes szám összegére kell felbontani. Milyen $n$ esetén lesz a felbontások száma $n$ -nél 1-gyel nagyobb?
Írjuk fel pl. $n = 6$ esetére az összes lehetséges felbontást:

\begin{matrix} 1  1  4 & 2  1  3 & 3  1  2 & 4  1  1 \\ 1  2  3 & 2  2  2 & 3  2  1 \\ 1  3  2 & 2  3  1 \\ 1  4  1 \end{matrix}

Láthatjuk, hogy a felsoroltak között némelyik többször is előfordul, pl. 1 2 3 és 2 1 3 csak a sorrendben különbözik, amit mi nem tudunk megkülönböztetni, mert csak azonos fajtájú szaloncukrunk van. Az

n = 6

esetén csak háromféle különböző halomba osztás létezik, és közülük csak egy elégíti ki azt a feltételt, hogy minden halomban más-más számú cukor legyen,

n < 6

esetén pedig egy sem tudja kielégíteni a feladat feltételét.
Legyen

n

elemünk (

n

darab szaloncukor), ezt 3 nem üres halmazba

(\binom{n - 1}{2}) = \frac{(n - 1) (n - 2)}{2}

-féleképpen oszthatjuk szét. (Képzeljük el ugyanis, hogy a szaloncukrokat sorban lerakjuk, és három kupacra bontjuk két osztóvonallal. Az osztóvonalakat pedig

n - 1

közre helyezhetjük.) Ez az összes lehetséges felosztás; ebből le kell vonnunk azok számát, amelyek többször fordulnak elő, illetve nem tesznek eleget a feladat követelményének.
Legyen

k < n

, és számoljuk meg azokat a felosztásokat, amelyekben

k

(

k

darab szaloncukor) elemű halmaz kétszer fordul elő. Ezek:

\begin{matrix} k, k, n - 2 k; k, n - 2 k, k; n - 2 k, k, k; \end{matrix}

ez 3 lehetőség, és ha

n - 2 k = k

, azaz

n = 3 k

(

n

osztható 3-mal), akkor még egy lehetőség az, amikor a 3 halom mindegyikében ugyanannyi elem (cukor) van.
Eszerint 4 esetet kell megkülönböztetnünk:
1. Ha

n

páros, de 3-mal nem osztható, akkor

n \geq 2 k

k \leq \frac{n}{2}

, s mivel

k

egész,

\frac{n}{2} - 1

olyan eset van, amikor két halom ugyanannyi elemből áll, s ezek mindegyike 3-szor szerepel. Ekkor a nekünk megfelelő esetek száma:

\begin{matrix} \frac{(n - 1) (n - 2)}{2} - 3 (\frac{n}{2} - 1) . \end{matrix}

Ezt ‐ mivel a sorrendet nem kívánjuk figyelembe venne ‐ el kell osztanunk a 3 elem lehetséges sorrendjeinek számával,

3! = 1 \cdot 2 \cdot 3 = 6

-tal.
Írjuk fel a feltételeket kielégítő egyenletet:

\begin{matrix} \frac{\frac{(n - 1) (n - 2)}{2} - 3 (\frac{n}{2} - 1)}{6} = n + 1. \end{matrix}

Rendezve a következő egyenlethez jutunk:

n^{2} - 18 n - 4 = 0

, s ennek nincs egész megoldása.
2. Ha

n

páros és 3-mal is osztható, akkor

\begin{matrix} \frac{\frac{(n - 1) (n - 2)}{2} - 3 (\frac{n}{2} - 2) - 1}{6} = n + 1. \end{matrix}

Innen

n^{2} - 18 n = 0

, azaz

n = 0

vagy

n = 18

.
3. Ha

n

páratlan és nem osztható 3-mal, akkor

\frac{n - 1}{2}

olyan felosztás van, amiben két halom elemszáma megegyezik. Az egyenlet:

\begin{matrix} \frac{\frac{(n - 1) (n - 2)}{2} - 3 (\frac{n - 1}{2})}{6} = n + 1, \end{matrix}

n^{2} - 18 n - 7 = 0

. Nincs egész megoldása.
4. Ha

n

páratlan és osztható 3-mal, az egyenlet:

\begin{matrix} \frac{\frac{(n - 1) (n - 2)}{2} - 3 (\frac{n - 1}{2} - 1) - 1}{6} = n + 1, \end{matrix}

n^{2} - 18 n - 3 = 0

. Ekkor sincs egész megoldás.
Látjuk, hogy

n = 18

megoldás, azaz 18 darab szaloncukrot 19-féleképpen tudunk 3 halomba osztani úgy, hogy a cukrok száma minden halomban más legyen. Más megoldása nincs a feladatnak, mivel az összes lehetséges esetet megvizsgáltuk.

Gyimesi Andrea (Miskolc, Földes F. Gimn., 8. o.t.) dolgozata alapján

Megjegyzés. A megoldók többsége (legtöbbjük 3 pontot kapott) csak azt látta be, hogy a 18 jó megoldás, de azt nem, hogy más megoldás nem lehetséges.