Kezdőlap


Feladat:	F.2550	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Batternay Anita , Benczúr A. , Benya Zsuzsanna , Bereczky Á. , Bereznai Cs. , Blahota I. , Bóna Miklós , Bozó A. , Csott R. , Deák Csaba , Deák T. , Domokos M. , Harmath L. , Hartmann Klára , Héjj T. , Illés A. , Janszky J. , Jedlovszky P. , Juhász A. , Kádár L. , Kintli L. , Kocsis Z. , Kovács 538 A. , Montágh B. , Olasz-Szabó M. , Ribényi Á. , Sziklay L. , Sziklay T. , Tóth Anikó , Vindics P. , Weszelovszky Éva
Füzet:	1986/május, 200 - 202. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Kombinációk, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1985/november: F.2550

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. $n = 1$ , 2-re az állítás nyilvánvalóan igaz, ám $n = 3$ , 4-re könnyű ellenpéldát készíteni: az 1, 2, 4, 5 számok közül semelyik három különbözőnek az összege nem osztható 3-mal. A feladat szövege azonban $n = 3$ -ra és $n = 4$ -re is azt követeli, hogy pozitív legyen az ilyen számhármasok száma.
Bebizonyítjuk, hogy $n ≧ 5$ -re a feladat állítása igaz.
Először is megmutatjuk, hogy öt különböző egész között van három különböző, amelyek összege osztható hárommal. Ha ugyanis az öt között van három olyan, amelyek ugyanazt a maradékot adják 3-mal osztva, akkor ezek összege nyilván osztható 3-mal.
Ha viszont a $3 k, 3 l + 1$ és $3 m + 2$ számalakok mindegyikéből legföljebb kettő van, akkor mindhárom fajtának elő kell fordulnia az öt szám között. Van tehát egy-egy $3 k, 3 l + 1$ és $3 m + 2$ alakú szám ( $k, l, m$ egész), ezek összege pedig szintén osztható 3-mal.
Legyen most $n ≧ 6$ . Válasszunk ki minden lehetséges módon öt különböző számot az $n$ darab szám közül. Ezt $(\binom{n}{5})$ -féleképpen tehetjük meg. A fentiek szerint minden ilyen számötösből kiválasztható három, amelyben a számok összege osztható 3-mal. Kaptunk $(\binom{n}{5})$ megfelelő hármast, ezek között azonban lehetnek azonosak is. Egy $(a_{1}, a_{2}, a_{3})$ hármast viszont legföljebb annyiszor választhatunk ki, ahány ötösben egyáltalán előfordul, vagyis ahányféleképpen a maradó $n - 3$ számból kettőt mellétehetünk. Ez tehát legföljebb $(\binom{n - 3}{2})$ előfordulást jelent minden egyes kiválasztott számhármasra nézve. Kaptunk tehát $(\binom{n}{5})$ megfelelő hármast, s ezek között minden egyes hármas legföljebb $(\binom{n - 3}{2})$ -ször fordul elő. Összesen tehát legalább $(\binom{n}{5}) / (\binom{n - 3}{5}) = \frac{n (n - 1) (n - 2)}{60}$ különböző olyan számhármasnak kell lennie, amelyben a három szám összege osztható 3-mal.
A feladat állítását tehát $n ≧ 5$ -re (és $n = 1$ , 2-re) bebizonyítottuk.

II. megoldás, az

n ≧ 6

esetre teljes indukcióval.
Láttuk, hogy

n = 5

-re igaz az állítás. Tegyük fel, hogy

n

-re igaz és legyen adott

n + 1

különböző egész,

a_{1}, a_{1}, ..., a_{n}, a_{n + 1}

. Az indukciós feltevés szerint az

n + 1

darab

\begin{matrix} a_{2}, & a_{3}, ..., a_{i - 1}, a_{i}, a_{i + 1}, ..., a_{n}, a_{n + 1}, \\ a_{1}, & a_{3}, ..., a_{i - 1}, a_{i}, a_{i + 1}, ..., a_{n}, a_{n + 1} \\ ⋮ \\ a_{1}, a_{2}, & a_{3}, ..., a_{i - 1}, a_{i + 1}, ..., a_{n}, a_{n + 1} \\ ⋮ \\ a_{1}, a_{2}, & a_{3}, ..., a_{n} \end{matrix}

szám

n

-es mindegyikéből kiválasztható

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

megfelelő szám hármas. Így összesen

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

megfelelő számhármast kaptunk. Az

a_{i}, a_{j}, a_{k}

számhármast az

i ., j .

és

k .

sorban biztosan nem választottuk ki, tehát bármely számhármas legföljebb

n + 1 - 3 = n - 2

-szer fordul elő. Így a megfelelő számhármasok között legalább

\begin{matrix} \frac{(n + 1) n (n - 2)}{60} / (n - 2) = \frac{(n + 1) n (n - 1)}{60} \end{matrix}

különböző van, a feladat állítása tehát

n + 1

-re is igaz. Ezzel az indukciós lépést, s így az állítást is bebizonyítottuk.