MetaMath '24 - Školjka

Vrijeme: 11:10

Kombinatorika u drugim područjima - Primjer 3

Zadatak: U ravnini je dano $2n$ točaka – $n$ plavih i $n$ crvenih, pri čemu nikoje tri ne leže na istom pravcu. Dokažite da se može postaviti $n$ dužina koje će kao krajeve imati plavu i crvenu točku, i to tako da se nikoje dvije dužine ne sijeku.

Rješenje:
Kako bi rješili ovaj zadatak korstit ćemo nekoliko metoda: $\begin{enumerate} \item prebrojavanjem utvridmo da imamo konačno uparivanja (ne nužno takva da se ne sijeku) \\\\ Ukupno imamo $n!$ različitih spajanja. Naime, ako plave točke označimo brojevima $1,2\dots,n$ i crvene također označimo istim brojevima, onda svako spajanje tih točaka možemo shvatiti kao preslikavanje koje svakom broju iz skupa ${1,2\dots,n}$ pridružuje točno jedan broj iz tog istog skupa (i različitim brojevima pridružuje različite brojeve). No, svako takvo preslikavanje možemo shvatiti kao da elemente skupa ${1,2\dots,n}$ redamo u niz (u nekom poretku), a to možemo napraviti na $n!$ načina: prvi član niza biramo na n načina, drugi na $n-1$ način i tako do zadnjeg koji biramo na 1 način. Zato to možemo napraviti na ukupno $n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1 = n!$ načina. Ono što nam je zapravo bilo bitno jest da postoji konačno mnogo načina na koje to možemo napraviti.\\\\ \item zatim promatramo ektremni element tih sparivanja \\\\ Između njih odaberemo ono spajanje $\mathcal{E}$ koje ima najmanju sumu duljina $n$ dužina (znamo da takvo postoji jer tih spajanja ima konačno mnogo).\\\\ \item te konačno koristeći geometrijsko znanje dolazimo do tražene tvrdnje.\\\\ Pretpostavimo da postoje dvije dužine koje se sijeku i označimo ih s $\overline{P_1C_1}$, $\overline{P_2C_2}$ (pritom su $P_1$, $P_2$ plave, a $C_1$, $C_2$ crvene točke). Ukoliko te dužine zamijenimo dužinama $\overline{P_1C_2}$, $\overline{P_2C_1}$, dobit ćemo spajanje $\mathcal{E}'$ koje ima manju ukupnu duljinu dužina. Naime, ukoliko označimo sjecište dužina $\overline{P_1C_1}$, $\overline{P_2C_2}$ sa $S$, prema nejednakosti trokuta primijenjenoj na trokute $\triangle P_1C_2S$ i $\triangle P_2C_1S$ slijede nejednakosti: \begin{align*} |P_1C_2| < |P_1S| + |C_2S|,\\ |P_2C_1| < |P_2S| + |C_1S|. \end{align*} Zbrajanjem ovih nejednakosti imamo $$|P_1C_2| + |P_2C_1| < (|P_1S| + |C_1S|) + (|C_2S| + |P_2S|) = |P_1C_1| + |P_2C_2|.$$ Ovo je u kontradikciji s odabirom spajanja. Dakle, $\mathcal{E}$ je traženo spajanje. \end{enumerate}$

Za bod upišite padel.

\textbf{Zadatak:} U ravnini je dano $2n$ točaka – $n$ plavih i $n$ crvenih, pri čemu nikoje tri ne leže na istom pravcu. Dokažite da se može postaviti $n$ dužina koje će kao krajeve imati plavu i crvenu točku, i to tako da se nikoje dvije dužine ne sijeku. \textbf{Rješenje:} \\ Kako bi rješili ovaj zadatak korstit ćemo nekoliko metoda: \begin{enumerate} \item prebrojavanjem utvridmo da imamo konačno uparivanja (ne nužno takva da se ne sijeku) \\\\ Ukupno imamo $n!$ različitih spajanja. Naime, ako plave točke označimo brojevima $1,2\dots,n$ i crvene također označimo istim brojevima, onda svako spajanje tih točaka možemo shvatiti kao preslikavanje koje svakom broju iz skupa ${1,2\dots,n}$ pridružuje točno jedan broj iz tog istog skupa (i različitim brojevima pridružuje različite brojeve). No, svako takvo preslikavanje možemo shvatiti kao da elemente skupa ${1,2\dots,n}$ redamo u niz (u nekom poretku), a to možemo napraviti na $n!$ načina: prvi član niza biramo na n načina, drugi na $n-1$ način i tako do zadnjeg koji biramo na 1 način. Zato to možemo napraviti na ukupno $n \cdot (n-1) \cdot \dots \cdot 2 \cdot 1 = n!$ načina. Ono što nam je zapravo bilo bitno jest da postoji konačno mnogo načina na koje to možemo napraviti.\\\\ \item zatim promatramo ektremni element tih sparivanja \\\\ Između njih odaberemo ono spajanje $\mathcal{E}$ koje ima najmanju sumu duljina $n$ dužina (znamo da takvo postoji jer tih spajanja ima konačno mnogo).\\\\ \item te konačno koristeći geometrijsko znanje dolazimo do tražene tvrdnje.\\\\ Pretpostavimo da postoje dvije dužine koje se sijeku i označimo ih s $\overline{P_1C_1}$, $\overline{P_2C_2}$ (pritom su $P_1$, $P_2$ plave, a $C_1$, $C_2$ crvene točke). Ukoliko te dužine zamijenimo dužinama $\overline{P_1C_2}$, $\overline{P_2C_1}$, dobit ćemo spajanje $\mathcal{E}'$ koje ima manju ukupnu duljinu dužina. Naime, ukoliko označimo sjecište dužina $\overline{P_1C_1}$, $\overline{P_2C_2}$ sa $S$, prema nejednakosti trokuta primijenjenoj na trokute $\triangle P_1C_2S$ i $\triangle P_2C_1S$ slijede nejednakosti: \begin{align*} |P_1C_2| < |P_1S| + |C_2S|,\\ |P_2C_1| < |P_2S| + |C_1S|. \end{align*} Zbrajanjem ovih nejednakosti imamo $$|P_1C_2| + |P_2C_1| < (|P_1S| + |C_1S|) + (|C_2S| + |P_2S|) = |P_1C_1| + |P_2C_2|.$$ Ovo je u kontradikciji s odabirom spajanja. Dakle, $\mathcal{E}$ je traženo spajanje. \end{enumerate} Za bod upišite \textbf{padel}.