Kombinatorikai versenyfeladatok megoldási módszerei

Bevezető gondolatok

A magyarországi matematikaversenyeken a tanulók nagyon gyakran találkozhatnak kombinatorikus gondolkodást igénylő feladatokkal. Ezek a példák általában megmozgatják a fiatalok fantáziáját, hiszen a játék, a különféle esetek elemzése, az esélylatolgatás mindenki számára érdekes kihívást jelent. A tankönyvekben, példatárakban a kombinatorikai feladatok általában az alapján vannak csoportosítva, hogy milyen leszámolási képlettel lehet megkapni a felvetett kérdésre a választ. Ennek szellemében ismerkednek meg a diákok a permutációkkal, variációkkal, kombinációkkal, a skatulyaelvvel és általában a kombinatorikus gondolkodással.

Gyakran hallani olyan véleményt a tanulóktól, hogy a kombinatorikai feladatok azért nehezek, mert szinte mindegyik probléma más, nincsenek olyan általános módszerek, irányelvek, amelyek segítségével eredményesek lehetnek ezen a területen. Természetesen ez az álláspont nem felel meg a valóságnak, hiszen ha nagyon sok kombinatorikai versenyfeladat megoldását tekintjük át, akkor világossá válik számunkra, hogy a kombinatorikában is megvannak azok az eszközök, amelyek segítségével nagy eséllyel lehetünk sikeresek a feladatok megoldásában.

Ebben a cikkben a sikerhez vezető módszerek közül szeretnénk bemutatni néhányat.

1. Osztályozás módszere

Ha a feladat feltételeinek megfelelő kombinatorikai szerkezet sokféle helyzet szerint megvalósulhat, akkor célszerű ezeket külön megvizsgálni.

Az osztályok kialakításának szempontjai:

– Az eredeti probléma minden helyzetét bele kell foglalni valamelyik osztályba.

– A kialakított osztályok páronként idegenek legyenek.

– Az osztályozás egyetlen kritérium szerint történjen.

– A részproblémák megoldása könnyebb legyen, mint a teljes problémáé.

Példa. Egy körön kijelölünk $n$ ( $n\ge 6$ ) darab pontot, és közülük bármely kettőt összekötjük egy egyenes szakasszal. Tudjuk, hogy a megadott szakaszok közül semelyik három nem halad át a kör ugyanazon belső pontján. Így bármely három szakasz, amelyik páronként metszi egymást, meghatároz egy háromszöget. Adjuk meg a szakaszok által meghatározott háromszögek számát!

(Kína, IMO csapat tréning)

Megoldás. Nevezzük a körön felvett pontokat külső pontoknak, a körön belül képződő metszéspontokat belső pontoknak! A keletkező háromszögeket csoportosítsuk aszerint, hogy a csúcsok között milyen arányban fordulnak elő külső és belső pontok.

1. osztály: A háromszögek mindhárom csúcsa külső pont:

3 külső pont $\mapsto 1$ háromszög.

Az első csoportba tartozó háromszögek száma: $\binom{n}{3}$ .

2. osztály: A háromszögek két csúcsa külső, egy csúcsa belső pont:

A keletkező háromszögek: $K_1B_1K_2$ , $K_2B_1K_3$ , $K_3B_1K_4$ , $K_4B_1K_1$ .

4 külső pont $\mapsto$ 4 háromszög.

A második csoportba tartozó háromszögek száma: $4\cdot \binom{n}{4}$ .

3. osztály: A háromszögek egy csúcsa külső, két csúcsa belső pont:

A keletkező háromszögek: $B_1K_1B_2$ , $B_2K_2B_3$ , $B_3K_3B_4$ , $B_4K_4B_5$ , $B_5K_5B_1$ .

5 külső pont $\mapsto 5$ háromszög.

A harmadik csoportba tartozó háromszögek száma: $5\cdot \binom{n}{5}$ .

4. osztály: A háromszögek mindhárom csúcsa belső pont:

6 külső pont $\mapsto 1$ háromszög

A negyedik csoportba tartozó háromszögek száma: $\binom{n}{6}$ .

Így a keletkező összes háromszögek száma:

$\displaystyle \binom{n}{3}+4\cdot\binom{n}{4}+5\cdot\binom{n}{5}+\binom{n}{6}.$

2. Frakcionált lépések módszere

– Az eredeti komplex, nehéz problémát részproblémákra bontjuk.

– Megoldjuk a részproblémákat.

– Amikor az utolsó részprobléma is megoldódik, megkapjuk az eredeti feladat megoldását is.

Példa. A 0, $1$ számok segítségével felírunk $2^{n-1}$ $n$ -jegyű különböző számsorozatot. Ha a felírt sorozatok közül bármelyik hármat összehasonlítjuk, akkor azokra teljesül, hogy létezik olyan $1\le p\le n$ pozitív egész szám, amelyre a vizsgált sorozatok $p$ -edik jegye $1$ -es. Mutassuk meg, hogy ekkor létezik olyan $1\le k\le n$ pozitív egész szám is, amelyre az összes sorozat $k$ -adik jegye $1$ -es!

(Moszkvai Matematikai Olimpia, 1969)

Megoldás. Legyen $S=\{X\mid X=(x_1;x_2;\ldots ;x_n), x_i=0,$ vagy $1,i=1,2,\ldots,n\}$ és $S_0$ a felírt számsorozatok halmaza! Definiáljuk az $S$ halmazon az alábbi két műveletet:

Bármely $X=\{x_1;x_2;\ldots ;x_n\}$ , $Y=\{y_1;y_2;\ldots ;y_n\}$ esetén

$\displaystyle \overline{X}=\{\overline{x_1};\overline{x_2};\ldots ;\overline{x_n}\},$

ahol $\overline{x_i}=\begin{cases}0, & \text{ha }x_i=1\\ [5pt] 1, & \text{ha }x_i=0\end{cases}$ , $i=1,2,\ldots,n$ és

$\displaystyle X\cdot Y=(x_1y_1;x_2y_2;\ldots;x_ny_n).$

Ekkor $XY\in S$ esetén $\overline{X}\in S$ , $X\cdot Y\in S$ , és a feladat feltétele szerint tetszőleges $X,Y,Z\in S_0\subset S$ esetén $X\cdot Y\cdot Z\neq (0;0;\ldots;0)$ .

Vizsgáljuk meg $S_0$ tulajdonságait! (Megjegyzés: ezek a részproblémák)

(1) Bármely $X\in S$ esetén az $X\in S_0$ , $\overline{X}\in S_0$ relációk közül pontosan az egyik teljesül.

Indirekt bizonyítást alkalmazva $\large X,\overline{X},Y\in S_0$ esetén $X\cdot \overline{X}\cdot Y=\left( 0;0;\ldots ;0 \right)$ , ami ellentmond a feladat egyik feltételének.

Mivel $S$ elemeiből $2^{n-1}$ -féle $(X;\overline{X})$ pár képezhető és $\vert S_0\vert=2^{n-1}$ , így $X$ és $\overline{X}$ közül pontosan az egyik tartozik hozzá $S_0$ -hoz.

(2) Bármely $XY\in S_0$ esetén $X\cdot Y\in S_0$ .

Ismét indirekt bizonyítást alkalmazva, tegyük fel, hogy $Z=X\cdot Y\notin S_0$ . Ekkor az (1)-es tulajdonság alapján $\overline{Z}=\overline{XY}=\overline{X}\cdot \overline{Y}\in S_0$ és $X\cdot Y\cdot \overline{Z}=X\cdot Y\cdot (\overline{X}\cdot \overline{Y})=(X\cdot \overline{X})\cdot (Y\cdot \overline{Y})=(0;0;\ldots;0)$ , ami ellentmondás. Tehát $X\cdot Y\in S_0$ .

(3) Ha $S_0=\{X_1;X_2;\ldots ;X_{2^{n-1}}\}$ , akkor $X=X_1\cdot X_2\cdot \ldots \cdot X_{2^{n-1}}$ esetén $X$ jegyei között 1 db 1-es van, a többi jegy 0. Ennek igazolása az alábbi megfontolások alapján történhet:

– Az (1)-es és (2)-es tulajdonságok alapján $X\in S_0$ és $X\ne(0;0;\ldots ;0)$ .

– Ha $X$ -nek legalább két jegye 1-es, akkor $S_0$ minden elemének legalább két rögzített pozíciójú jegye is 1-es, ami alapján $\vert S_0\vert\le 2^{n-2}<2^{n-1}$ .

A kapott ellentmondás igazolja a (3)-as tulajdonság teljesülését.

A részproblémák megoldása után visszatérhetünk az eredeti feladat megoldásához.

Mivel $X$ $k$ -adik jegye 1-es, a többi 0, ezért létezik olyan egyértelmű $1\le k\le n$ pozitív egész, amelyre minden $S_0$ -beli sorozat $k$ -adik jegye 1-es.

3. Párosítási módszer

A megoldás során bizonyos szabályok szerint párosítjuk a kombinatorikai elemeket, és így sok számítás egyszerűbbé válik.

Példa. Legyen $M$ az $I=\{1;2;\ldots ;n\}$ halmaznak egy $k$ elemű részhalmaza ( $n\in \mathbb{N}^+$ , $k\in \mathbb{N}$ , $k\le n$ ). Tegyük fel, hogy az $M=\{i_1;i_2;\ldots;i_k\}$ elemei növekvő sorrendbe vannak rendezve, azaz $i_1<i_2<\ldots<i_k$ . Az $i_k-i_{k-1}+\ldots+(-1)^{k-1}i_1$ kifejezést nevezzük az $M$ halmaz alternáló összegének. (Például az $\{1;2; 4; 6; 9\}$ halmaz alternáló összege $9-6+4-2+1=6$ , az $\{5\}$ halmazé 5, az üres halmazé legyen 0.) Milyen értéket kapunk, ha $I$ összes részhalmazának alternáló összegét összeadjuk?

Megoldás. Soroljuk $I$ részhalmazait két osztályba aszerint, hogy tartalmazzák, vagy nem tartalmazzák az $n$ számot! Párosítsuk egymáshoz a két osztályból az $A=\{a_1;a_2;\ldots ;a_k,n\}$ , $a_1<a_2<\ldots <a_k<n$ és $B=\{a_1;a_2;\ldots;a_k\}$ halmazokat! Az alternáló összegeket összeadva:

$\displaystyle n-a_k+a_{k-1}+\ldots +(-1)^ka_1+a_k-a_{k-1}+\ldots+(-1)^{k-1}a_1=n.$

Mivel az $I$ -ből kialakítható halmazpárok száma $2^{n-1}$ , ezért a keresett összeg $S=n\cdot 2^{n-1}$ .

4. Leképezési módszer

A módszer elméleti háttere:

Legyen $f\colon M\to N$ egy leképezés két véges halmaz között.

a) Ha $f$ injektív, azaz bármely $x_1,x_2\in M$ , $x_1\ne x_2$ esetén $f(x_1)\ne f(x_2)$ , akkor $\vert M\vert\le\vert N\vert$ .

b) Ha $f$ szürjektív, azaz bármely $y\in N$ -hez létezik olyan $x\in M$ , hogy $f(x)=y$ , akkor $\vert M\vert\ge\vert N\vert$ .

c) Ha $f$ bijektív, azaz kölcsönösen egyértelmű, akkor $\vert M\vert=\vert N\vert$ .

Ezt a módszert akkor alkalmazzuk, ha az $M$ halmaz elemszáma nehezen állapítható meg, és ezért helyette a vele bijektív leképezésben álló $N$ halmaz elemszámát határozzuk meg.

Egyenlőtlenségek bizonyításakor gyakran hozunk létre szürjektív vagy injektív leképezést két kombinatorikai objektumrendszer között.

Példa. Egy $n$ oldalú szabályos háromszöget az ábra szerint felosztunk egység oldalú kis háromszögekre. Határozzuk meg az ábrán látható egység oldalú rombuszok számát!

Megoldás. Először azokat a rombuszokat fogjuk összeszámolni, amelyek oldalai $BC$ -vel nem párhuzamosak.

Egészítsük ki az eredeti $ABC$ szabályos háromszöget az ábrán látható módon egy $n+1$ oldalú $AB'C'$ szabályos háromszöggé! Ekkor a rombuszok oldalegyenesei a $B'C'$ szakaszt 4 különböző pontban metszik. A metszéspontokat $B'$ -től számozva azonosítsuk a $0, 1, 2, \ldots, n+1$ számokkal, és hozzunk létre egy $f_1\colon$ rombuszok $\to(i;i+1;j;j+1)$ , $0\le i<i+1<j<j+1\le n+1$ bijektív leképezést!

Mivel az $(i,i+1,j,j+1)$ rendezett számnégyes tagjai nem függetlenek egymástól, ezért megadhatunk egy praktikusabb, $f_2\colon (i;i+1;j;j+1)\to (i+1;j)$ , $1\le i+1<j\le n$ bijektív leképezést is.

$f_1$ és $f_2$ alapján a $BC$ -vel nem párhuzamos oldalú rombuszok száma pontosan annyi mint a $H=\{1; 2; \ldots; n\}$ halmaz kételemű részhalmazainak száma, azaz $\binom{n}{2}$ .

Így az összes egység oldalú rombuszok száma $3\cdot\binom{n}{2}$ .

5. Kettős összeszámlálás módszere

Gyakran kínálkozik lehetőség arra, hogy egy kombinatorikus mennyiséget két egymástól különböző gondolatmenettel, kétféle úton is meg tudunk határozni. Ekkor a kapott összefüggések összehasonlításával értékes azonosságokat és fontos egyenlőtlenségeket kaphatunk.

Példa. Igazoljuk az alábbi azonosságot:

$\displaystyle 1\cdot\binom{n}{1}+2\cdot\binom{n}{2}+3\cdot\binom{n}{3}+\ldots+n\cdot\binom{n}{n}=n\cdot 2^{n-1}$ .

Megoldás. A bizonyítást az alábbi kombinatorikai probléma kettős összeszámlálásával végezzük el:

Egy $n$ személyből álló csoport tagjaiból létrehozunk egy $k$ tagú bizottságot, amelynek vezetője a bizottsági elnök. Hányféleképpen szerveződhet meg a bizottság?

Ekkor a bizottság kialakításának egyik módja:

– meghatározzuk, hogy hány fős legyen a bizottság ( $k$ , $k=1,2,\ldots,n$ ),

– kiválasztjuk a bizottsági tagokat ( $\binom{n}{k}$ lehetőség),

– a bizottsági tagok maguk közül kiválasztják az elnököt ( $k$ lehetőség).

Ezek alapján a lehetőségek száma összesen:

$\displaystyle \sum\limits_{k=1}^n k\cdot \binom{n}{k}=1\cdot \binom{n}{1}+2\cdot\binom{n}{2} +3\cdot \binom{n}{3} +\ldots +n\cdot \binom{n}{n}.$

A bizottság kialakításának egy másik módja:

– a csapat tagjai közül kiválasztjuk az elnököt ( $n$ lehetőség),

– a további $n-1$ személyről külön-külön döntünk, hogy bekerüljön-e a bizottságba (személyenként egymástól függetlenül 2-2 döntési lehetőség).

Ebben az esetben a lehetőségek száma összesen: $n\cdot 2^{n-1}$ .

A kettős számolás és az összehasonlítás alapján:

$\displaystyle 1\cdot \binom{n}{1}+2\cdot \binom{n}{2}+3\cdot \binom{n}{3}+\ldots +n\cdot \binom{n}{n}=n\cdot 2^{n-1}.$

6. Rekurziós módszer

A megoldás lépései:

– Konkrét esetek vizsgálatával meghatározzuk a kezdőértékeket.

– Megállapítjuk a rekurziós összefüggést.

– Szükség esetén megadjuk az explicit képletet.

– Végül megadjuk a konkrét probléma megoldását.

Példa. Egy körlemezt felosztunk $n$ ( $n\ge 2$ , $n\in\mathbb{N}^+)$ egybevágó körcikkre és az $S_1,S_2,\ldots,S_n$ szektorokat kiszínezzük $k$ színnel úgy, hogy bármely két szomszédos rész színe különböző legyen. Hányféle különböző kiszínezési lehetőség van?

Megoldás. Legyen a megfelelő színezések száma $a_n(k)$ !

a) Keressük meg először a kezdőértéket!

$n=2$ esetén $S_1$ -et $k$ -féle színnel színezhetjük ki, míg $S_2$ -t a felhasznált szín kivételével, a többivel.

Így a szorzási szabály alapján $a_2(k)=k\cdot (k-1)$ .

b) Ezután határozzuk meg a rekurziós összefüggést!

Színezzük ki a tartományokat az $S_1,S_2,\ldots,S_n$ sorrendben, és csak arra figyeljünk, hogy az éppen színezett tartomány az előzőtől eltérő színű legyen! Ekkor $k\cdot (k-1)^{n-1}$ különböző lehetőség adódik a szektorok kiszínezésére.

$S_n$ és $S_1$ egymáshoz viszonyított színe alapján kétféle helyzet állhat elő.

I. eset: $S_n$ és $S_1$ színe különböző

Az ilyen esetek száma: $a_n(k)$ .

II. eset: $S_n$ és $S_1$ színe azonos

Ekkor $S_n$ és $S_1$ egy szektorrá egyesülnek, és olyan helyzet áll elő, mintha $n-1$ tartomány lenne jól színezve. Így az ilyen esetek száma $a_{n-1}(k)$ , és a rekurziós összefüggés:

$\displaystyle a_n(k)+a_{n-1}(k)=k\cdot (k-1)^{n-1}\qquad (n\ge 3)$

c) A továbbiakban az explicit képlet megadására törekszünk.

A rekurziós összefüggés alapján:

$\displaystyle \frac{a_n(k)}{(k-1)^n}+\frac{1}{k-1}\frac{a_{n-1}(k)}{(k-1)^{n-1}}=\frac{k}{k-1}.$

Vezessük be a $b_n(k)=\frac{a_n(k)}{(k-1 )^n}$ sorozatot! Ekkor

$\displaystyle b_n(k)+\frac{1}{k-1}b_{n-1}(k)=\frac{k}{k-1},$

$\displaystyle b_n(k)-1=-\frac{1}{k-1}[b_{n-1}(k)-1].$

Az index-léptetés módszerével alakítsuk tovább $n\ge 3$ esetén:

$\displaystyle b_n(k)-1=-\frac{1}{k-1}(b_{n-1}(k)-1)=\frac{1}{(k-1)^2}(b_{n-2}(k)-1)=\ldots$

$\displaystyle \ldots=(-1)^{n-2}\frac{1}{(k-1)^{n-2}}(b_2(k)-1)$

Felhasználjuk, hogy $b_2(k)=\frac{a_2(k)}{(k-1)^2}=\frac{k(k-1)}{(k-1)^2}=\frac{k}{k-1}$ , és tudjuk, hogy $(-1)^{n-2}=(-1)^n$ :

$\displaystyle b_n(k)-1=( -1 )^n\frac{1}{(k-1)^{n-2}}\left(\frac{k}{k-1}-1\right)=(-1)^n\frac{1}{(k-1)^{n-1}}.$

Innen meghatározhatjuk $a_n(k)$ értékét:

$\displaystyle \frac{a_n(k)}{(k-1)^n}-1=(-1)^n\frac{1}{(k-1)^{n-1}},$

$\displaystyle a_n(k)=(k-1)^n+(-1)^n(k-1).$

A levezetés $n\ge 3$ esetében alkalmazható, de korábbi megállapításaink alapján az $a_n(k)$ -ra kapott képlet $n=2$ esetben is helyes eredményt ad.

7. Kiértékelés színekkel

A kombinatorikai elemekhez, kapcsolatokhoz pontokat, szakaszokat, tartományokat társítunk, és a megfelelő geometriai objektumokhoz színeket rendelünk.

Ezután megszámoljuk

– az azonos vagy különböző színű pontpárokat,

– az egyszínű vagy nem egyszínű háromszögeket,

– az azonos vagy különböző színű szárakkal rendelkező szögeket,

– az egyes tartományokhoz tartozó azonos színű mezőket.

Az adatokat ezután elemezzük, összehasonlítjuk, majd a megoldáshoz elvezető megállapításokat teszünk.

Példa. Egy parlament munkájában 30 személy vesz részt, és bármely két személy szövetségben áll vagy politikai ellenfele a másiknak. Tudjuk, hogy minden személynek pontosan 6 politikai ellenfele van. 3 személyt nevezzünk egységes triónak, ha közülük bármely két politikus szövetségben áll vagy ellenfele a másiknak. Határozzuk meg az egységes triók számát!

(Orosz Matematikai Olimpia)

Megoldás. Az egyes személyekhez rendeljünk hozzá egy-egy térbeli pontot úgy, hogy semelyik 4 ne essen egy síkra! A szövetségeseket és a politikai ellenfeleket szemléltessük az alábbi módon:

A keletkező gráfban az egyszínű háromszögeket számoljuk össze.

Ha egy háromszögben egy szög két szára különböző színű, akkor a szöget nevezzük tarka szögnek.

Vizsgáljuk a különböző típusú háromszögeket!

Ekkor az alábbi megállapításokat tehetjük:

– Egyszínű háromszögben nincs tarka szög.

– Nem egyszínű háromszögben 2 tarka szög van.

– Minden pontból 23 piros és 6 kék él indul ki.

– Egy csúcsban találkozó tarka szögek száma: $23\cdot 6=138$ .

– Az összes tarka szögek száma: $30\cdot 138=4140$ .

– A nem egyszínű háromszögek száma: $\frac{4140}{2}=2070$ .

– Az összes háromszögek száma: $\binom{30}{3}=4060$ .

– Így az egyszínű háromszögek és az egységes triók száma: $4060-2070=1990$ .

8. Kiértékelés számokkal

A megoldás során az egyes kombinatorikai elemekhez számokat rendelünk. A számokat elemezzük, összehasonlítjuk, és az invariáns tulajdonságaikat megállapítjuk.

Így a vizsgált probléma könnyen megoldhatóvá válik.

Példa. Egy szabályos hatszöget oldalaival párhuzamos egyenesek segítségével felosztunk 24 egybevágó szabályos háromszögre. A kis háromszögek csúcsaihoz 19 különböző valós számot rendelünk. Igazoljuk, hogy van legalább 7 olyan háromszög, amelynek csúcsaihoz rendelt számok az óramutató járása szerint haladva csökkenő sorozatot alkotnak!

Megoldás. Osszuk be a háromszögeket két csoportba aszerint, hogy a csúcsaikhoz rendelt számok az óramutató járása szerint csökkenő vagy növekvő sorozatot alkotnak-e!

Tegyük fel, hogy az első csoportba $N$ háromszög tartozik, míg a második csoportba $24-N$ háromszög jut! Irányítsuk a háromszög éleit úgy, hogy a nyíl mindig a kisebb szám felé mutasson! Írjunk a nyilak bal oldalára $(-1)$ -et, a jobb oldalára $(+1)$ -et!

Ekkor az első csoportba tartozó háromszögekbe eső számok összege $+1$ , a második csoportba tartozóké pedig $-1$ . Emiatt a háromszögekbe írt számok összege:

$\displaystyle N\cdot(+1)+(24-N)\cdot(-1)=2N-24.$

Másrészt a hatszög belsejében levő élek két oldalára írt számok összege:

$\displaystyle (+1)+(-1)=0.$

A hatszög oldalain elhelyezkedő 12 háromszögoldal kört alkot, így a melléjük írt számok közül legalább az egyik $+1$ . Emiatt ezen 12 élre írt számok összege legalább

$\displaystyle (+1)+11\cdot ( -1 )=-10.$

Így

$\displaystyle 2N-24$	$\displaystyle \ge-10,$
$\displaystyle N$	$\displaystyle \ge7.$

Ezzel az állítást igazoltuk.

9. A lehetetlenre visszavezetés módszere

– A megoldás során feltesszük a direkt úton nehezen bizonyítható állítás tagadását.

– Ebből logikailag helyes következtetésekkel ellentmondásra jutunk.

– Ez pedig azt jelenti, hogy a bizonyítandó állítás igaz.

Példa. Az $ABC$ háromszög csúcsait ebben a sorrendben pirosra, kékre és zöldre színezzük. Ezután a háromszögben felveszünk néhány belső pontot, és ezeket összekötjük egymással, illetve az $ABC$ háromszög csúcsaival, és így a háromszöget felosztjuk kisebb háromszögekre. Ezután a belső pontokat is kiszínezzük az említett három szín valamelyikével. Bizonyítsuk be, hogy tetszőleges színezés mellett keletkezik olyan kis háromszög, melynek mindhárom csúcsa különböző színű!

Megoldás. Tegyük fel, hogy nem keletkezik olyan háromszög, amelynek mindhárom csúcsa különböző színű!

A továbbiakban használjuk a piros és kék pontot összekötő szakasz elnevezésére a piros-kék oldal megnevezést, és legyen a részháromszögek összes ilyen típusú oldalainak száma $S$ !

Határozzuk meg $S$ értékét kétféleképpen!

Mivel a belső piros-kék szakaszokra két-két háromszög illeszkedik, az $AB$ oldalra pedig csak egy, ezért, ha a belső piros-kék szakaszok száma $k$ , akkor $S=2k+1$ , azaz $S$ páratlan szám.

Másrészt, ha az ábrán nem keletkezik háromszínű háromszög, akkor piros-kék oldal csak piros-piros-kék, piros-kék-kék csúcsú háromszögekben található. Ezek mindegyike 2 piros-kék oldalt tartalmaz, ezért ha számuk p, akkor $S=2p$ , azaz $S$ páros szám.

$S$ nem lehet egyszerre páros, illetve páratlan szám, így ellentmondásra jutottunk. Ez azt jelenti, hogy a színezés során mindenképpen keletkezik piros-kék-zöld háromszög.

10. Kiindulás a szélső helyzetből

– A megoldás során a vizsgált kombinatorikai elem maximális vagy minimális értékéből indulunk ki.

– Az ezen értékhez tartozó vizsgálat alapján az állítást elutasítjuk vagy elfogadjuk.

– Szükség esetén a kezdőértéket a céloknak megfelelően módosítjuk, és a problémát egy jó konstrukció megadásával megoldjuk.

Példa. Egy futballtornán minden csapat pontosan egy mérkőzést játszott a többi csapat mindegyikével. Minden mérkőzésen a győztes $2$ , a vesztes 0 pontot kapott, míg döntetlen eredmény esetén mindkét csapat $1$ – $1$ pontot kapott. A tornát az $A$ csapat nyerte meg úgy, hogy egyedüliként a legtöbb pontot szerezte, és a legkevesebb győzelmet érte el. Határozzuk meg a tornán résztvevő csapatok számának minimumát!

(16. Oroszországi Matematikai Olimpia)

Megoldás. Legyen az $A$ csapat eredménylistája:

$n$ győzelem,

$m$ döntetlen,

$2n+m$ pont.

Ekkor a feltétel szerint a többi csapat mindegyike legalább $n+1$ győzelmet szerzett, és

$\displaystyle 2n+m$	$\displaystyle >2(n+1),$
$\displaystyle m$	$\displaystyle >2,$
$\displaystyle \Rightarrow m$	$\displaystyle \ge 3.$

Tegyük fel, hogy az $A$ csapat egyik döntetlenjét a $B$ csapat ellen szerezte. Ekkor a $B$ csapat legalább $2(n+1)+1$ pontot ért el, és

$\displaystyle 2n+m$	$\displaystyle >2(n+1)+1,$
$\displaystyle m$	$\displaystyle >3,$
$\displaystyle \Rightarrow m$	$\displaystyle \ge 4.$

Vizsgáljuk ezután az $A$ csapat győzelmeinek számát! Tegyük fel, hogy $n=0$ ! Legyen a résztvevő csapatok száma $s$ ! Ekkor az $A$ csapat pontszáma legfeljebb $s-1$ , a többieké ( $s-1$ )-nél kevesebb lehetett csak, és a csapatok együttesen $s(s-1)$ -nél kevesebb pontot gyűjthettek.

Viszont a mérkőzéseken összesen

$\displaystyle 2\binom{s}{2}=s(s-1)$

pont került kiosztásra. Így a kapott ellentmondás alapján $n\ge 1$ .

$n=1$ és $m=4$ esetén egy lehetséges eredménylista:

	$A$	$B$	$C$	$D$	$E$	$F$	Pontszám
$A$	–	1	1	1	1	2	6
$B$	1	–	2	0	0	2	5
$C$	1	0	–	0	2	2	5
$D$	1	2	2	–	0	0	5
$E$	1	2	0	2	–	0	5
$F$	0	0	0	2	2	–	4

Tehát a tornán résztvevő csapatok minimális száma 6.

11. Helyi kiigazítások módszere

A megoldás során a kezdeti állapotból helyi kiigazításokkal lépésről lépésre közelítünk a cél felé.

A módszer felhasználható:

– kombinatorikus objektumok tulajdonságainak igazolására,

– kombinatorikai szélsőértékproblémák megoldására,

– adott tulajdonságú kombinatorikus szerkezetek kialakítására.

Példa. Írjuk fel a $2008$ -at különböző pozitív egész számok összegeként úgy, hogy a számok szorzata maximális legyen! Mekkora ez a maximális érték?

Megoldás. Vezessük be a kiválasztott számok halmazára, összegére és szorzatára az alábbi jelöléseket:

$S=\{a_1;a_2;\ldots ;a_k\}$ , $a_1<a_2<\ldots <a_k$ ( $a_i\in \mathbb{N}^+$ , $i=1,2,\ldots,k$ )

$\sum S =a_1+a_2+\ldots +a_k=2008$

$\prod S =a_1\cdot a_2\cdot \ldots \cdot a_k$

Mivel a 2008 véges sokféleképpen írható fel különböző egész számok összegeként, ezért a $\prod S$ -nek létezik maximuma.

Vizsgáljuk az $S$ tulajdonságait.

(1) Ha $a_1<a<b<a_k$ , $a,b\notin S$ , de $a-1,b+1\in S$ , akkor alkalmazzuk az alábbi helyi kiigazítást:

Legyen $\large S'=S\setminus \{a-1,b+1\}\cup\{a,b\}$ . Ekkor $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S}=\frac{ab}{(a-1)(b+1)}=\frac{ab}{ab-(b-a )-1}>1\Rightarrow\prod S'>\prod S.$

Tehát $a_1$ és $a_k$ között legfeljebb egy pozitív egész szám nem szerepel $S$ -ben.

(2) Ha $a_1=1$ , akkor alkalmazzuk az alábbi helyi kiigazítást:

Legyen $\large S'=S\setminus\{1;a_k\}\cup\{a_k+1\}$ . Ekkor $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S}=\frac{a_k+1}{1\cdot a_k}>1\Rightarrow \prod S'>\prod S.$

Tehát $1\notin S$ .

(3) a) Ha $a_1=4$ és $a_2=5$ , akkor alkalmazzuk az alábbi helyi kiigazítást:

Legyen $\large S'=S\setminus\{5\}\cup\{2;3\}$ . Ekkor $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S}=\frac{2\cdot 3}{5}>1\Rightarrow \prod S'>\prod S.$

b) Ha $a_1=4$ , $j\notin S$ ( $j=5,\ldots,t-1$ ), $t\in S$ ( $t\ge 6$ ), akkor alkalmazzuk az alábbi helyi kiigazítást:

Legyen $S'=(S\setminus\{4,t\})\cup\{2;3;t-1\}$ . Ekkor $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S}=\frac{2\cdot 3\cdot(t-1)}{4t}=\frac{4t+2(t-3)}{4t}>1 \Rightarrow \prod S'>\prod S.$

c) Ha $a_1\ge 5$ , akkor alkalmazzuk az alábbi helyi kiigazítást:

Legyen $\large S'=S\setminus\{a_1\}\cup\{2;a_1-2\}$ . Ekkor $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S }=\frac{2(a_1-2)}{a_1}=\frac{a_1+(a_1-4)}{a_1}>1 \Rightarrow \prod S'>\prod S.$

Tehát (3) a), b), c) alapján $a_1=2$ vagy $a_1=3$ .

Az (1), (2), (3) feltételek alapján, ha $a_1=3$ , $a_k=n$ és $h\notin S$ ( $3<h<n$ ), akkor

$\displaystyle 3+4+\ldots+n-h$	$\displaystyle =2008,$
$\displaystyle (n-2)(n+3)$	$\displaystyle =4016+2h,$
$\displaystyle n$	$\displaystyle =63,$
$\displaystyle h$	$\displaystyle =5,$
$\displaystyle S$	$\displaystyle =\{ 3, 4, 6, 7, \ldots , 63\}.$

Az $S'=(S\setminus \{7\})\cup \{2;5\}$ helyi kiigazítást alkalmazva: $\sum S'=\sum S$ és

$\displaystyle \frac{\prod S'}{\prod S}=\frac{2\cdot 5}{7}>1 \Rightarrow\prod S'>\prod S.$

Tehát $a_1=2$ .

Az (1), (2), (3) feltételek alapján, ha $a_1=2$ , $a_k=n$ és $h\notin S$ ( $2<h<n$ ), akkor

$\displaystyle 2+3+\ldots +n-h$	$\displaystyle =2008,$
$\displaystyle (n-1)(n+2)$	$\displaystyle =4016+2h,$
$\displaystyle n$	$\displaystyle =63,$
$\displaystyle h$	$\displaystyle =7,$
$\displaystyle S$	$\displaystyle =\{ 2, 3, 4, 5, 6, 8, \ldots, 63\}.$

Tehát $\prod S$ maximális értéke $\frac{63!}{7}$ .

12. Konstrukciós módszer

A direkt konstrukciós módszer alkalmazása során:

– Elemezzük a célként kitűzött kombinatorikai szerkezetet.

– Részleges feltételeket teljesítő részeket hozunk létre.

– A szükséges korrekciók végrehajtásával olyan szerkezetet alakítunk ki, amely minden feltételnek megfelel.

Az induktív konstrukciós módszer alkalmazása során:

– $n$ -től függő kombinatorikai szerkezetet hozunk létre.

– Először $n$ kezdőértékére megadjuk a megfelelő struktúrát.

– Majd megadjuk, hogy $n$ értékének 1-gyel történő változtatása esetén milyen módosításokat kell végezni.

Példa. Van-e olyan véges $M$ ponthalmaz a síkon, amelynek bármely $P$ pontjára teljesül, hogy három $M$ -beli ponthoz van a legközelebb?

Megoldás. Részfeltételeket teljesítő konstrukció:

A konstrukció javítása történhet $m$ darab rombusz összeépítésével.

$\displaystyle 90^{\circ}<\alpha \le 120^{\circ}$

(1)

A külső konvex sokszög szögeit kétféleképpen felírva:

$\displaystyle m\cdot 120^{\circ}+2m\cdot(\alpha +60^{\circ})$	$\displaystyle =(3m-2)\cdot 180^{\circ},$
$\displaystyle \alpha$	$\displaystyle =150^{\circ}-\frac{180^{\circ}}{m}.$	(2)

Az (1), (2) feltételek alapján adódó megoldások:

$m$	4	5	6
$\alpha$	$105^{\circ}$	$114^{\circ}$	$120^{\circ}$

13. Valószínűségi módszer

A valószínűségszámítás eszközeivel:

– meghatározott tulajdonságú kombinatorikus modell létezését igazolhatjuk

a) $P($ jó modell $)>0$ .

b) $\large P($ rossz modell $\large )<1$ .

– adott tulajdonságú kombinatorikai elemek számát megbecsülhetjük egy valószínűségi változó várható értékének meghatározásával. Ez utóbbira mutatunk példát.

Példa. Egy asztalitenisz bajnokságban $40$ játékos vesz részt. Eddig összesen $80$ mérkőzés fejeződött be, és bármely két játékos legfeljebb egyszer játszott egymással. Adjunk becslést $n$ legnagyobb értékére, ha tudjuk, hogy biztosan van a résztvevők között $n$ játékos, akik közül semelyik kettő nem játszott egymással!

1. megoldás. A hagyományos leszámolási módszerrel az $n=4$ becslés adható.

Indirekt bizonyítási módszert alkalmazva tegyük fel, hogy bármely 4-tagú csoportra jut mérkőzés.

– Ekkor a 4-tagú csoportok száma: $\binom{40}{4}$ .

– Minden lejátszott mérkőzés $\binom{38}{2}$ 4-tagú csoportban szerepel.

– Így a lejátszott mérkőzések száma legalább: $\binom{40}{4}:\binom{38}{4}=130>80$ .

A kapott ellentmondás alapján garantált a mérkőzés nélküli 4 fős csoport létezése.

$n=5$ esetén hasonló gondolatmenetet alkalmazva:

– Az 5-tagú csoportok száma: $\binom{40}{5}$ .

– Minden lejátszott mérkőzés $\binom{38}{3}$ 5-tagú csoportban szerepel.

– Így a lejátszott mérkőzések száma legalább: $\binom{40}{5}:\binom{38}{3}=78<80$ .

Tehát az alkalmazott módszer már nem garantálja a mérkőzés nélküli 5 fős csoport létezését.

2. megoldás. Valószínűségi módszerrel igazoljuk az $n=5$ becslés helyességét.

Véletlenszerűen alakítsunk ki egy játékosokból álló csoportot úgy, hogy minden résztvevőt $0{,}25$ valószínűséggel választunk be az adott társaságba.

Ezután távolítsuk el a csoportból azokat a személyeket, akik vesztettek egy másik kiválasztott játékossal szemben. Így a megmaradó játékosok közül már semelyik kettő nem játszott egymás ellen.

Vizsgáljuk meg a megmaradó játékosok számának várható értékét! Ekkor

– Átlagosan $40\cdot 0{,}25=10$ játékos kerül kiválasztásra.

– Minden lejátszott mérkőzés esetén ${0{,}25}^2$ a valószínűsége annak, hogy az kiválasztott játékosok között zajlott le.

– Tehát a kiválasztott játékosok között lejátszott mérkőzések átlagos száma $80\cdot 0{,}25^2=5$ .

– Az 5 vesztes legfeljebb 5 személy lehet, így őket a csoportból eltávolítva legalább 5 olyan ember marad, akik nem játszottak egymás között mérkőzést.

3. megoldás. Egy másik valószínűségi módszerrel igazoljuk az $n=8$ becslés helyességét.

Rendeljünk a versenyzőkhöz 1-től 40-ig sorszámot és legyen az $i$ -edik játékos által lejátszott mérkőzések száma: $d_i$ ! Ekkor

$\displaystyle d_1+d_2+\ldots +d_{40}=80\cdot 2=160.$

Ezután válasszuk ki azokat a játékosokat, akik legfeljebb csak alacsonyabb sorszámú társaikkal játszottak mérkőzést. Az $i$ -edik játékos pontosan akkor lett kiválasztva, ha ő kapta a legnagyobb sorszámot maga és a $d_i$ számú ellenfele közül. Tehát

$\displaystyle P($ az $\displaystyle i$ -edik játékos kiválasztott $\displaystyle )=\frac{1}{d_i+1}\qquad (i=1,2,\ldots,40),$

és így semelyik két kiválasztott játékos között nem volt mérkőzés.

Ekkor a kiválasztott játékosok számának várható értéke a számtani-harmonikus közép közti egyenlőtlenség alapján:

$\displaystyle \frac{1}{d_1+1}+\ldots+\frac{1}{d_{40}+1}\ge\frac{40^2}{(d_1+1)+\ldots+(d_{40}+1)}=\frac{1600}{160+40}=8.$

Megjegyzés. Az $n=8$ eredmény tovább már nem javítható. Az ábrán a pontok jelzik a játékosokat, a szakaszok pedig a közöttük lejátszott mérkőzéseket.

A gráf alapján jól látható, hogy minden csoportból legfeljebb 1 versenyző választható ki.

Ez az írás 2019-ben a gödöllői Rátz László Vándorgyűlésen elhangzott szemináriumi foglalkozás alapján készült. A bemutatott módszerek segítségével szinte bármilyen nehézségű leszámolási, létezési és szélsőértékfeladat, illetve kombinatorikus egyenlőtlenség megoldható. A cikkben közölt feladatokkal és megoldásaikkal jól használható anyagot próbáltunk biztosítani a középiskolában tanító tanároknak az iskolai szakköri munkához.

Fonyó Lajos – Fonyóné Németh Ildikó

Keszthely, Vajda János Gimnázium