MetaMath '22 - Školjka

Vrijeme: 11:25

Primjer 7.

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$ .

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}.$$ \textbf{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$.