Triunghiuri echilaterale - JBTST V 2007, problema 4
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Laurian Filip
- Site Admin
- Posts: 344
- Joined: Sun Nov 25, 2007 2:34 am
- Location: Bucuresti/Arad
- Contact:
Triunghiuri echilaterale - JBTST V 2007, problema 4
Spunem ca o multime de puncte este libera daca nu exista niciun triunghi echilateral cu varfurile printre punctele multimii. Aratati ca orice multime de \( n \) puncte in plan contine o submultime libera formata din cel putin \( sqrt{n} \) puncte.
-
Laurian Filip
- Site Admin
- Posts: 344
- Joined: Sun Nov 25, 2007 2:34 am
- Location: Bucuresti/Arad
- Contact:
vad ca nu se chinuie nimeni so rezolve 
... chiar asteptam o solutie mai frumoasa.
evident ca daca \( [\sqrt{n}] \)<3 acele puncte nu pot forma vreun triunghi echilateral.
daca \( \sqrt{n} \)=3 rezulta ca avem minim 5 puncte in multime. Luam 2 dintre aceste puncte. Segmentul respectiv poate forma un triunghi echilateral doar cu 2 puncte (cele 2 de pe mediatoare, de o parte si cealalta a segmentului) . Cum avem mai mult de 4 puncte in total \( \rightarrow \) gasim o submultime libera.
folosim metoda inductiei...
P(k): daca \( [\sqrt{n}]=k \) gasim o submultime libera cu cel putin k elemente
Presupunem P(k) adevarata si aratam P(k) \( \rightarrow \) P(k+1)
Asadar stim ca P(k) e adevarat deci intr-o multime cu \( k^2-2k+2 \) elemente gasim o submultime libera de k elemente.
Asadar intr-o multime cu \( k^2+1 \) elemente gasim o submultime libera de k elemente. Cele k elemente formeaza \( \frac{(k-1)k}{2} \) segmente. Fiecare dintre aceste segmente poate forma un triunghi echilateral doar cu 2 puncte.
cum \( k^2+1-k>\frac{(k-1)k}{2} \cdot 2 \) rezulta ca mai ramane un punct pe care il putem adauga submultimii libera astfel incat sa ramana libera.
Asadar P(k) \( \rightarrow \) P(k+1) si P(3) e adevarat deci P(n) e adevarata \( \forall n \in \mathbb{N} \)
obs: asta e minunata mea solutie de 6 puncte
... chiar asteptam o solutie mai frumoasa. evident ca daca \( [\sqrt{n}] \)<3 acele puncte nu pot forma vreun triunghi echilateral.
daca \( \sqrt{n} \)=3 rezulta ca avem minim 5 puncte in multime. Luam 2 dintre aceste puncte. Segmentul respectiv poate forma un triunghi echilateral doar cu 2 puncte (cele 2 de pe mediatoare, de o parte si cealalta a segmentului) . Cum avem mai mult de 4 puncte in total \( \rightarrow \) gasim o submultime libera.
folosim metoda inductiei...
P(k): daca \( [\sqrt{n}]=k \) gasim o submultime libera cu cel putin k elemente
Presupunem P(k) adevarata si aratam P(k) \( \rightarrow \) P(k+1)
Asadar stim ca P(k) e adevarat deci intr-o multime cu \( k^2-2k+2 \) elemente gasim o submultime libera de k elemente.
Asadar intr-o multime cu \( k^2+1 \) elemente gasim o submultime libera de k elemente. Cele k elemente formeaza \( \frac{(k-1)k}{2} \) segmente. Fiecare dintre aceste segmente poate forma un triunghi echilateral doar cu 2 puncte.
cum \( k^2+1-k>\frac{(k-1)k}{2} \cdot 2 \) rezulta ca mai ramane un punct pe care il putem adauga submultimii libera astfel incat sa ramana libera.
Asadar P(k) \( \rightarrow \) P(k+1) si P(3) e adevarat deci P(n) e adevarata \( \forall n \in \mathbb{N} \)
obs: asta e minunata mea solutie de 6 puncte