Ilość odpowiednich krawędzi w n-kącie

novy154 · Post autor: **novy154** » 18 lis 2012, o 23:42

Dobry wieczór,
Nasunęło mi się pewne pytanie.
Mamy n-kąt. Każdy z wierzchołków możemy połączyć z pozostałym na n-1 sposobów, jednak wtedy każdy odcinek jest liczony podwójnie, zatem mamy w takim n-kącie \(\displaystyle{ \frac{n(n-1)}{2}}\) 'krawędzi'.

Moje pytanie jest takie:
Ile krawędzi spośród \(\displaystyle{ \frac{n(n-1)}{2}}\) możemy maksymalnie wybrać, aby nie utworzyć trójkąta?

JakimPL · Post autor: **JakimPL** » 19 lis 2012, o 00:19

Nie utworzyć trójkąta z samych połączeń czy ogólnie? Dla drugiego przypadku ta liczba jest mała.

novy154 · Post autor: **novy154** » 19 lis 2012, o 00:30

Rysujemy sobie, przykładowo 6-kąt.
Kolejno malujemy jakimś kolorem krawędzie tak długo, aż zamalowanie dowolnej następnej utworzy trójkąt.

JakimPL · Post autor: **JakimPL** » 19 lis 2012, o 00:33

To możemy tylko jedną krawędź dla sześciokąta "zamalować", tak?

novy154 · Post autor: **novy154** » 19 lis 2012, o 09:10

Szlag by to, nie rozumiemy się.

W przypadku sześciokąta możesz zamalować 6 boków, potem, jeżeli dobrze liczę, trzy przekątne. Zamalowanie dowolnego następnego odcinka utworzy już trójkąt.