Unimi geocombinatorica.

Rette, triangoli, cerchi, poliedri, ...
Rispondi
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Unimi geocombinatorica.

Messaggio da enomis_costa88 »

La soluzione combinatorica è più geometrica di quello che possa sembrare :wink:

Questo è il più facile dei 3 unimi che ho postato..magari gli esperti possono concentrarsi sull'1..


Si consideri un cerchio di area 1 e 2007 punti al suo interno. Mostrare che esiste una terna di punti che forma un triangolo (eventualmente degenere) la cui area non supera $ \frac{1}{2005} $

Buon divertimento!
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Avatar utente
pi_greco_quadro
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: Verona

Messaggio da pi_greco_quadro »

Vabbè, visto che non lo guarda nessuno...

Beh poniamoci innanzitutto nel caso peggiore, ovvero nel caso in cui i 2007 punti considerati determinino un poligono convesso. Ora, è noto che la somma degli angoli interni ad un poligono convesso è (n-2)*180°, quindi in qualche modo devo riuscire a costruire almeno (n-2) triangoli disgiunti, nel senso che, scelti comunque due triangoli distinti tra essi, è vuota l'intersezione delle rispettive aree. Un modo per realizzare tale configurazione è la seguente: scegliamo un vertice, che chiamiamo V, e lo congiungiamo con (n-3) diagonali a tutti gli altri vertici non adiacenti. In questo modo riusciamo a costruire esattamente n-2 triangoli.
Perché questo era il caso peggiore? beh supponiamo di avere almeno un angolo ottuso nel nostro poligono, allora esso sarà concavo. Quindi esisterà almeno un segmento congiungente due vertici che sarà esterno all'area del poligono, e quindi potremo formare almeno un altro triangolo disgiunto dagli n-2 precedenti, d'altra parte ancora ottenibili poiché la somma degli angoli interni al poligono sarà stavolta > (n-2)*180. Quindi il minimo numero di triangoli disgiunti possibili dati n punti è (n-2). Da questo segue la tesi.
Disco es cultura, metal es religion (Metal py)
"Ti credevo uno stortone.. e pure vecchio.. (Lei)"
Rispondi