USAMO 2005 - Rette bilanciate
USAMO 2005 - Rette bilanciate
Sia n un intero maggiore di 1. Supponiamo che esistano 2n punti nel piano e che almeno 3 di questi non giacciano sulla stessa retta. Supponiamo che n di questi 2n siano colorati di blu e gli altri n di rosso. Una retta nel piano viene detta bilanciata se passa attraverso un puno blu e un punto rosso e, per ogni semipiano diviso dalla retta, il numero di punti blu da una parte è uguale al numero di punti rossi dalla medesima parte. Dimostrare che esistono almeno 2 rette bilanciate.
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Carino, vediamo se quello che scrivo può avere un senso...
- Dato l'insieme dei $ 2n $ punti, costruiamo un poligono convesso $ L $ tale che:
i) i suoi vertici siano punti dell'insieme
ii) non vi siano punti dell'insieme situati al di fuori di esso.
Consideriamo un vertice $ B_{0} $ di $ L $ , e supponiamo che $ B_{0} $ sia blu.
Consideriamo ora gli altri vertici di $ L $: se tra di essi ve n'è almeno uno rosso, allora abbiamo finito, poichè ci saranno almeno due lati $ h $ e $ h_{1} $ di $ L $ unenti un punto blu ed uno rosso. Essendo infatti $ L $ convesso, le rette $ r $ ed $ r_{1} $ passanti rispettivamente per $ h $ e $ h_{1} $ , lasceranno in un semipiano nessun punto e nell'altro semipiano $ 2n-2 $ punti, di cui $ n-1 $ blu e $ n-1 $ rossi.
Ci resta da esaminare il caso in cui tutti i vertici di $ L $ siano di uno stesso colore, ad esempio, blu.
Consideriamo il punto $ B_{0} $.
Sia $ B_{1} $ il primo vertice che si incontra procedendo sul perimetro di $ L $ da $ B_{0} $ in senso orario.
Sia $ t $ la retta passante per questi due punti. Facciamo ruotare $ t $ in senso orario con centro di rotazione in $ B_{0} $.
Chiamiamo $ P_{1}, P_{2}, P_{3}, ..., P_{n-2}, P_{n-1} $ i punti che $ t $ incontra, nell'ordine in cui li incontra, di modo che $ P_{1}=B_{1} $ e $ P_{n-1}=B_{n-1} $ (dove $ B_{n-1} $ è il primo vertice di $ L $ che si incontra procedendo da $ B_{0} $ in senso antiorario).
Sempre facendo ruotare $ t $ in senso orario, sia $ R_{1} $ il primo punto rosso che $ t $ incontra. Si avranno così da una parte di $ t , s $ punti blu , con $ s>0 $, per ciò che si è detto prima, e $ 0 $ punti rossi ,mentre dall'altra parte di $ t $, $ n-(s+1) $ punti blu e $ n-1 $ punti rossi.
Consideriamo il primo semipiano descritto, e oserviamo che ogni qual volta $ t $ incontra un punto rosso, il numero di punti rossi nel semipiano aumenta di uno.
Sia $ R_{n} $ l'ultimo punto rosso che $ t $ incontra: sappiamo per certo che nel semipiano che stiamo considerando, il numero di punti blu sarà inferiore a quello di punti rossi, poichè nel semipiano adiacente vi satranno $ l $ punti blu , $ l>1 $, e, ovviamente $ 0 $ punti rossi.
Abbiamo quindi dedotto che:
i) all'inizio, con $ t $ passante per $ R_{0} $, i punti blu erano in numero maggiore dei punti rossi.
ii) alla fine, con $ t $ passante per $ R_{n} $, i punti rossi erano in numero maggiore dei punti blu.
iii) per ogni $ R_{i} $ che $ t $ incontrava, il numero di punti rossi nel semipiano era il numero di punti rossi del semipiano delimitato da $ t $ passante per $ R_{i-1} $, $ +1 $.
Quindi ci sarà un certo $ R_{j} $ per cui il numero di punti blu nel semipiano è uguale al numero di punti rossi. La retta $ t $ passante per $ R_{j} $ è dunque bilanciata.
Inoltre, potendo fare questo ragionamento per qualsiasi altro vertice di $ L $, e dal momento che $ L $ ha almeno tre vertici, allora esisteranno almeno due rette bilanciate, e la dimostrazione è completa.
- Dato l'insieme dei $ 2n $ punti, costruiamo un poligono convesso $ L $ tale che:
i) i suoi vertici siano punti dell'insieme
ii) non vi siano punti dell'insieme situati al di fuori di esso.
Consideriamo un vertice $ B_{0} $ di $ L $ , e supponiamo che $ B_{0} $ sia blu.
Consideriamo ora gli altri vertici di $ L $: se tra di essi ve n'è almeno uno rosso, allora abbiamo finito, poichè ci saranno almeno due lati $ h $ e $ h_{1} $ di $ L $ unenti un punto blu ed uno rosso. Essendo infatti $ L $ convesso, le rette $ r $ ed $ r_{1} $ passanti rispettivamente per $ h $ e $ h_{1} $ , lasceranno in un semipiano nessun punto e nell'altro semipiano $ 2n-2 $ punti, di cui $ n-1 $ blu e $ n-1 $ rossi.
Ci resta da esaminare il caso in cui tutti i vertici di $ L $ siano di uno stesso colore, ad esempio, blu.
Consideriamo il punto $ B_{0} $.
Sia $ B_{1} $ il primo vertice che si incontra procedendo sul perimetro di $ L $ da $ B_{0} $ in senso orario.
Sia $ t $ la retta passante per questi due punti. Facciamo ruotare $ t $ in senso orario con centro di rotazione in $ B_{0} $.
Chiamiamo $ P_{1}, P_{2}, P_{3}, ..., P_{n-2}, P_{n-1} $ i punti che $ t $ incontra, nell'ordine in cui li incontra, di modo che $ P_{1}=B_{1} $ e $ P_{n-1}=B_{n-1} $ (dove $ B_{n-1} $ è il primo vertice di $ L $ che si incontra procedendo da $ B_{0} $ in senso antiorario).
Sempre facendo ruotare $ t $ in senso orario, sia $ R_{1} $ il primo punto rosso che $ t $ incontra. Si avranno così da una parte di $ t , s $ punti blu , con $ s>0 $, per ciò che si è detto prima, e $ 0 $ punti rossi ,mentre dall'altra parte di $ t $, $ n-(s+1) $ punti blu e $ n-1 $ punti rossi.
Consideriamo il primo semipiano descritto, e oserviamo che ogni qual volta $ t $ incontra un punto rosso, il numero di punti rossi nel semipiano aumenta di uno.
Sia $ R_{n} $ l'ultimo punto rosso che $ t $ incontra: sappiamo per certo che nel semipiano che stiamo considerando, il numero di punti blu sarà inferiore a quello di punti rossi, poichè nel semipiano adiacente vi satranno $ l $ punti blu , $ l>1 $, e, ovviamente $ 0 $ punti rossi.
Abbiamo quindi dedotto che:
i) all'inizio, con $ t $ passante per $ R_{0} $, i punti blu erano in numero maggiore dei punti rossi.
ii) alla fine, con $ t $ passante per $ R_{n} $, i punti rossi erano in numero maggiore dei punti blu.
iii) per ogni $ R_{i} $ che $ t $ incontrava, il numero di punti rossi nel semipiano era il numero di punti rossi del semipiano delimitato da $ t $ passante per $ R_{i-1} $, $ +1 $.
Quindi ci sarà un certo $ R_{j} $ per cui il numero di punti blu nel semipiano è uguale al numero di punti rossi. La retta $ t $ passante per $ R_{j} $ è dunque bilanciata.
Inoltre, potendo fare questo ragionamento per qualsiasi altro vertice di $ L $, e dal momento che $ L $ ha almeno tre vertici, allora esisteranno almeno due rette bilanciate, e la dimostrazione è completa.