Kezdőlap


Feladat:	F.2760	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Benczúr Péter
Füzet:	1990/május, 206. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Számsorozatok, Feladat
Hivatkozás(ok):	Feladatok: 1989/október: F.2760

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.

Jelöljük a versenyzők maximális számát $a_{4}$ -gyel, és általában $n$ kérdés esetén a versenyzők maximális száma legyen $a_{n}$ . Nyilvánvaló, hogy $a_{1} = 3$ . Megmutatjuk, hogy $a_{n + 1} ≦ \frac{3}{2} a_{n}$ , ha $n ≧ 1$ . Tekintsük az $(n + 1)$ -edik kérdést, erre három lehetséges válasz volt, az 1. választ adók száma legyen $A$ , a 2. választ adóké $B$ , a 3. választ adóké $C$ . Bebizonyítjuk, hogy $A + B ≦ a_{n}$ . Ha ugyanis $A + B$ versenyzőből kiválasztunk hármat, akkor van egy kérdés, amelyikre mindhárman különböző választ adtak. De ez a kérdés nem lehet az $(n + 1)$ -edik, mert arra egyikük sem adta a 3. választ. Így az $A + B$ versenyzőhöz mindig van ilyen kérdés az első $n$ között. Ezért $A + B ≦ a_{n}$ . Ugyanígy látható, hogy $B + C ≦ a_{n}$ és $A + C ≦ a_{n}$ , ezeket összeadva $2 (A + B + C) ≦ 3 a_{n}$ azaz

\begin{matrix} a_{n + 1} = A + B + C ≦ \frac{3}{2} a_{n} . \end{matrix}

a_{1} = 3

miatt

a_{2} ≦ 1,5

a_{1} = 4

, 5, és

a_{2}

egész, tehát

a_{2} ≦ 4

a_{3} ≦ 1,5

a_{2} = 6

, s így

a_{4} ≦ 1,5 \cdot 6 = 9

.
Végül egy példával igazoljuk, hogy

a_{4} = 9

, azaz 9 versenyző tud úgy válaszolni a négy kérdésre, hogy teljesítse a feladat feltételét. Az egyes válaszokat

a

b

c

-vel jelölve a következő táblázat adja ezt meg:

\begin{matrix} 1. & 2. & 3. & 4. & kérdés \\ I. & a & a & b & c \\ II. & a & b & c & a \\ III. & a & c & a & b \\ IV. & b & a & c & b \\ V. & b & b & a & c \\ VI. & b & c & b & a \\ VII. & c & a & a & a \\ VIII. & c & b & b & b \\ IX. & c & c & c & c \end{matrix}

Benczúr Péter (Bp., Fazekas M. Gyak. Gimn., IV. o. t.)