Kezdőlap


Feladat:	F.3017	Korcsoport: 18-	Nehézségi fok: könnyű
Megoldó(k):	Bánhalmi András , Bánn Richárd , Burcsi Péter , Elek Péter , Fey Dániel , Gilyén Péter , Gyarmati Katalin , György András , Izsák Ferenc , Koblinger Egmont , Nagy Katalin , Németh Ákos , Németh Zoltán , Perényi Márton , Somogyi Balázs , Szádeczky-Kardoss Szabolcs , Szeredi Tibor , Szobonya László , Valkó Benedek , Vörös Zoltán
Füzet:	1995/január, 31 - 32. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Egyenlőtlenségek, Feladat
Hivatkozás(ok):	Feladatok: 1994/május: F.3017

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.

Legyen a klubok száma $k$ .
A feltétel második része azt jelenti, hogy egy ember legfeljebb két klubba járhat.
Rendeljük hozzá minden klub-párhoz valamelyik közös tagjukat. (A feltétel első fele szerint van közös tagjuk.) Mivel egy ember nem járhat kettőnél több klubba, a $(\binom{k}{2})$ kiválasztott ember mind különböző. Mivel a városban $n$ ember lakik, ez azt jelenti, hogy

\begin{matrix} (\binom{k}{2}) \leq n . \end{matrix}

(1)

Megfordítva, ha az (1) feltétel teljesül, akkor lehetséges

k

darab klub megszervezése:

(\binom{k}{2})

embert szétosztunk a klub-párok között, a maradék

n - (\binom{k}{2})

embert pedig például egy klubba sem járatjuk. Ezzel elérjük, hogy bármely két klubnak legyen pontosan egy, de semelyik háromnak ne legyen közös tagja.
A klubok maximális száma tehát az a legnagyobb

k

pozitív egész, amelyre (1) teljesül. (1)-et rendezve:

\begin{matrix} \begin{matrix} \frac{k (k - 1)}{2} & \leq n, \\ k^{2} - k & \leq 2 n, \\ {(k - \frac{1}{2})}^{2} & \leq 2 n + \frac{1}{4}, \\ k & \leq \frac{1}{2} + \sqrt[]{2 n + \frac{1}{4}} . \end{matrix} \end{matrix}

A legnagyobb ilyen

k

[\frac{1}{2} + \sqrt[]{2 n + \frac{1}{4}}]

Gyarmati Katalin (Fazekas M. Főv. Gyak. Gimn., II. o.t.)