Kezdőlap


Feladat:	C.895	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Õsz Edina , Szakács Enikõ
Füzet:	2007/december, 529 - 531. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Teljes indukció módszere, Négyzetszámok összege, C gyakorlat
Hivatkozás(ok):	Feladatok: 2007/április: C.895

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.

I. megoldás. Legyen $s$ a sötét háromszögek száma.
Ha $n = 1$ , akkor $s = 1 = (\binom{3}{0})$ .
Ha $n = 2$ , akkor $s = 4 = (\binom{4}{1})$ .
Ha $n = 3$ , akkor $s = 10 = (\binom{5}{2})$ .
Ha $n = 4$ , akkor $s = 20 = (\binom{6}{3})$ .
Ha $n = 5$ , akkor $s = 35 = (\binom{7}{4})$ .
Úgy tűnik, igaz az $s (n) = (\binom{n + 2}{n - 1})$ összefüggés. Felhasználva, hogy $(\binom{n + 2}{n - 1}) = (\binom{n + 2}{3})$ , teljes indukcióval belátjuk, hogy $s (n) = (\binom{n + 2}{3})$ .
$n = 1$ -re igaz, ezt már láttuk. Tegyük fel, hogy $n = k$ -ra is igaz: $s (k) = (\binom{k + 2}{3})$ . Tudjuk, hogy

\begin{matrix} s (k + 1) = s (k) + [1 + 2 + ... + k + (k + 1)] és s (k) = (\binom{k + 2}{3}) = \frac{k (k + 1) (k + 2)}{6} . \end{matrix}

Ezért

\begin{matrix} s (k + 1) = \frac{k (k + 1) (k + 2)}{6} + \frac{(k + 1) (k + 2)}{2} = \frac{(k + 1) (k + 2) (k + 3)}{6} = (\binom{k + 3}{3}) . \end{matrix}

Ezzel az állítást bizonyítottuk. Az

n

-edik háromszögig összesen felhasznált kis sötét háromszögek száma:

\begin{matrix} (\binom{n + 2}{3}), azaz \frac{n (n + 1) (n + 2)}{6} . \end{matrix}

II. megoldás. Az

n

-edik ábrán

1 + 2 + ... + n = \frac{n (n + 1)}{2}

db sötét és

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

db fehér háromszög van. Vagyis a háromszögek száma az

n

-edik ábrán összesen:

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

A négyzetszámok összegének képlete szerint:

\begin{matrix} 1 + 4 + 9 + ... + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}, \end{matrix}

tehát az

n

-edik ábráig ennyi háromszöget használtunk fel összesen. A

(k - 1)

-edik ábrán pontosan annyi sötét háromszög van, mint amennyi fehér háromszög a

k

-adikon. Tehát annyival van több a sötét háromszögekből, mint amennyi sötét háromszög van az

n

-edik ábrán. Az

n

-edik ábrán pedig

\frac{n (n + 1)}{2}

sötét háromszög van.
Az

n

-edik ábráig felhasználtunk

m

db fehér háromszöget és

m + \frac{n (n + 1)}{2}

db sötét háromszöget. Tehát:

\begin{matrix} \frac{n (n + 1) (2 n + 1)}{6} & = m + m + \frac{n (n + 1)}{2}, \\ (n^{2} + n) (2 n + 1) & = 12 m + 3 n^{2} + 3 n, \\ 2 n^{3} + n^{2} + 2 n^{2} + n & = 12 m + 3 n^{2} + 3 n, \\ 2 n^{3} & = 12 m + 2 n, \\ amiből m & = \frac{n^{3} - n}{6} . \end{matrix}

Tehát az

n

-edik ábráig felhasznált sötét háromszögek száma:

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