Kezdőlap


Feladat:	1989. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Pataki János
Füzet:	1989/november, 351. oldal		PDF \| MathML
Témakör(ök):	Kombinációk, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1989/szeptember: 1989. évi Nemzetközi Matematika Diákolimpia 13. feladata

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.

Sajnos a feladatra a magyar versenyzők egyike sem talált megoldást ‐ utólag ez bizonyult a verseny legnehezebb feladatának.
A megoldás első lépése a bizonyítandó egyenlőtlenség valamivel megfoghatóbb, beszédesebb alakban történő felírása. Rendezés után négyzetre emelve

\begin{matrix} k^{2} - k + \frac{1}{4} < 2 n, \end{matrix}

azaz

\begin{matrix} \frac{k^{2} - k}{2} + \frac{1}{8} < n \end{matrix}

adódik. A bal oldal első tagja egész, így elegendő igazolnunk, hogy

\begin{matrix} \frac{k^{2} - k}{2} ≦ n - 1 . \end{matrix}

A bal oldalon éppen

(\binom{k}{2})

, a

k

elem közül választható párok száma áll.
A halmaz minden

P

pontjához tekintsük tehát a tőle egyenlő távolságra lévő

k

darab

S

-beli pontból készíthető pontpárokat. Így összesen

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

pontpárt kapunk. Ha most egy

S

-beli

(A, B)

pontpárt számba veszünk egy

P

pontnál, akkor a

P

rajta van az

A B

felezőmerőlegesén. Mivel az

S

-ben nincs három egy egyenesre eső pont, a fenti leszámolás során tetszőleges

S

-beli pontpárt legfeljebb kétszer kaphatunk meg, azaz

\begin{matrix} n \cdot (\binom{k}{2}) ≦ 2 \cdot (\binom{n}{2}) = n \cdot (n - 1), \end{matrix}

ahonnan

n

-nel osztva éppen a bizonyítandó állítást kapjuk.

Megjegyzés. A feladat állítása úgy is teljesül, ha elhagyjuk azt a feltételt, hogy nincs három egy egyenesre eső

S

-beli pont, ennek bizonyítására most nem térünk ki.