Vrijeme: 02:08

Primjer 7.

Neka su n,k prirodni brojevi i neka je S skup od n točaka takvih da za svaku točku P iz skupa S postoji barem k točaka iz skupa S koje su jednako udaljene od točke P. Dokažite da vrijedi k<\frac{1}{2}+\sqrt{2n}.

Dokaz. Najprije ćemo danu nejednakost prevesti u ekvivalentnu koja će nam biti korisnija. Imamo \begin{aligned}
k&<\frac{1}{2}+\sqrt{2n}\\
k-\frac{1}{2}&<\sqrt{2n}\\
k^2+k+\frac{1}{4}&<2n\\
n-\frac{1}{8}&>\frac{k(k-1)}{2}\\
n-\frac{1}{8}&>\binom{k}{2}.
\end{aligned} Budući da su n i \binom{k}{2} prirodni brojevi, gornja nejednakost vrijedi ako i samo ako vrijedi nejednakost: n-1\geq\binom{k}{2}, koju ćemo i dokazati. Spojimo svaku točku skupa S sa svakom drugom točkom. Prebrojat ćemo tako nastale bridove na dva načina.

Kako skup S ima n različitih točaka ukupno ima \binom{n}{2} brida (odaberemo dvije točke i spojimo ih bridom).

S druge strane, po pretpostavci svaka točka skupa S ima barem k točaka jednako udaljenih od nje. Uzmimo proizvoljnu točku x skupa S i nacrtajmo kružnicu sa središtem u x i polumjerom takvim da siječe skup S u barem k točaka x_1,\ldots x_k. Tada je svaka dužina \overline{xx_i} ujedno i polumjer te kružnice i brid koji želimo prebrojati. Ponovimo li ovaj postupak za svaku točku dobivamo da tako konstruiranih bridova, brojeći kratnost (nismo orijentirali dužinu), ima barem n\cdot\binom{k}{2}. Uzmimo proizvoljne dvije točke skupa S i pripadne konstruirane kružnice. Neka je x središte prve kružnice i neka je \overline{xy} neki njen polumjer. Ako druga kružnica ima isti polumjer \overline{xy} tada je središte druge kružnice ili x ili y. Ukoliko bi to bio x tada bi se kružnice poklapale pa bi bile iste. Dakle, središte je y a polumjer \overline{yx}. Ovo pokazuje da dvije različite kružnice dijele najviše jedan polumjer. Stoga smo najviše \binom{n}{2} brojali dvaput, pa različitih bridova dobivenih ovom konstrukcijom ima barem n\binom{k}{2}-\binom{n}{2}. Taj broj nije veći od ukupnog broja bridova, što daje nejednakost n\binom{k}{2}-\binom{n}{2}\leq \binom{n}{2}. Iz ovoga lako slijedi nejednakost koju trebamo pokazati \begin{aligned}
n\binom{k}{2}-\binom{n}{2}&\leq \binom{n}{2}\\
\binom{k}{2}&\leq \frac{2}{n}\cdot\frac{n(n-1)}{2}\\
\binom{k}{2}&\leq n-1.
\end{aligned}

Kao rješenje upišite 0.