Kezdőlap


Feladat:	N.165	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Bérczi Gergely , Gerbicz Róbert , Gyenes Zoltán , Juhász András , Kun Gábor , Lippner Gábor , Lukács László , Székelyhidi Gábor , Terpai Tamás , Végh A. László
Füzet:	1998/október, 423. oldal		PDF \| MathML
Témakör(ök):	Halmazelmélet, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1998/február: N.165

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.

Legyenek $A_{0}$ , $...$ , $A_{k}$ $2 n$ elemű részei az ${1$ , 2, $...$ , $4 n}$ halmaznak. Mindegyik $A_{i}$ -hez rendeljük hozzá azt az $a_{i}$ vektort, amelynek $j$ -edik koordinátája 0, ill. 1 attól függően, hogy $j \notin A_{i}$ vagy $j \in A_{i}$ . Nyilván $a_{i} a_{j} = | A_{i} \cap A_{j} |$ , így például $a_{i}^{2} = 2 n$ . Tegyük fel, hogy a feladat állítása hamis, azaz $\forall i \neq j$ esetén $a_{i} a_{j} < (1 - \frac{1}{k}) n$ . Ekkor

\begin{matrix} b^{2} = {(a_{0} + ... + a_{k})}^{2} = \sum_{i = 0}^{k} a_{i}^{2} + \sum_{i < j}^{} 2 a_{i} a_{j} < (k + 1) \cdot 2 n + 2 (\binom{k}{2}) (1 - \frac{1}{k}) n \leq n {(k + 1)}^{2} . \end{matrix}

Viszont

b = (b_{1}, ..., b_{4 n})

koordinátáinak összege egyenlő

\sum_{}^{} | A_{i} | = (k + 1) \cdot 2 n

-nel, így

\begin{matrix} b^{2} = b_{1}^{2} + ... + b_{4 n}^{2} \geq \frac{1}{4 n} {(b_{1} + ... + b_{4 n})}^{2} = n {(k + 1)}^{2}, \end{matrix}

a számtani és a négyzetes közepek közötti egyenlőtlenség szerint. Ezt összevetve az utóbbival, ellentmondást kapunk, ami bizonyítja a feladat állítását.

Lukács László (Miskolc, Földes F. Gimn., 11. o.t.)

Lippner Gábor (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)