IMO 2006, Problem 6
IMO 2006, Problem 6
Assign to each side $ b $ of a convex polygon $ P $ the maximum area of a triangle that has $ b $ as a side and is contained in $ P $. Show that the sum of the areas assigned to the sides of $ P $ is at least twice the area of $ P $.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Visto che non penso di rubare il lavoro a nessuno, ecco una soluzione (non mia, ma di Jack) nata durante la cena di stasera:
1) l'area di un poligono non intrecciato i cui vertici hanno coordinate $ (x_i,y_i) $ è
$ S=\frac{1}{2}(x_1y_2-x_2y_1+x_2y_3-x_3y_2+\ldots $$ +x_{n-1}y_n-x_ny_{n-1}+x_ny_1-x_1y_n) $
2) fissato un lato di vertici x_1,y_1 e x_2,y_2, noi vogliamo trovare
$ \displaystyle{\frac{1}{2}\max_{i}(x_1y_2-y_1x_2+x_2y_i-x_iy_2+x_iy_1-y_ix_1)} $
e quindi calcolare
$ \displaystyle{\sum_{j}\frac{1}{2}\max_{i}(x_jy_{j+1}-y_jx_{j+1}+x_{j+1}y_i-x_iy_{j+1}+x_iy_j-y_ix_j)} $
posto $ x_{n+1},y_{n+1}=x_1,y_1 $.
3) vi sono termini che non dipendono da i e quindi possiamo portarli fuori dall'espressione da massimizzare, ottenendo la somma
$ \frac{1}{2} (x_1y_2-x_2y_1+x_2y_3-x_3y_2+\ldots $$ +x_{n-1}y_n-x_ny_{n-1}+x_ny_1-x_1y_n) $$ +\frac{1}{2}\sum\max((x_{j+1}-x_j)y_i+(y_j-y_{j+1})x_i) $
e il primo pezzo è proprio l'area S.
4) ora, le espressioni da massimizzare sono prodotti vettore $ a_j\times v_i $ dove a_j è il vettore che individua il punto x_{j+1},y_{j+1} rispetto al punto x_j,y_j e v_i individua il vertice con le coordinate x_i,y_i rispetto all'origine delle coordinate. Ovviamente, si ha
$ \max_i a_j\times v_i\geq a_j\times v_j $
e quindi
$ \sum\max_i a_j\times v_i\geq \sum a_J\times v_J=2S $
Da qui la tesi. (la convessità si usa nell'ultima uguaglianza).
1) l'area di un poligono non intrecciato i cui vertici hanno coordinate $ (x_i,y_i) $ è
$ S=\frac{1}{2}(x_1y_2-x_2y_1+x_2y_3-x_3y_2+\ldots $$ +x_{n-1}y_n-x_ny_{n-1}+x_ny_1-x_1y_n) $
2) fissato un lato di vertici x_1,y_1 e x_2,y_2, noi vogliamo trovare
$ \displaystyle{\frac{1}{2}\max_{i}(x_1y_2-y_1x_2+x_2y_i-x_iy_2+x_iy_1-y_ix_1)} $
e quindi calcolare
$ \displaystyle{\sum_{j}\frac{1}{2}\max_{i}(x_jy_{j+1}-y_jx_{j+1}+x_{j+1}y_i-x_iy_{j+1}+x_iy_j-y_ix_j)} $
posto $ x_{n+1},y_{n+1}=x_1,y_1 $.
3) vi sono termini che non dipendono da i e quindi possiamo portarli fuori dall'espressione da massimizzare, ottenendo la somma
$ \frac{1}{2} (x_1y_2-x_2y_1+x_2y_3-x_3y_2+\ldots $$ +x_{n-1}y_n-x_ny_{n-1}+x_ny_1-x_1y_n) $$ +\frac{1}{2}\sum\max((x_{j+1}-x_j)y_i+(y_j-y_{j+1})x_i) $
e il primo pezzo è proprio l'area S.
4) ora, le espressioni da massimizzare sono prodotti vettore $ a_j\times v_i $ dove a_j è il vettore che individua il punto x_{j+1},y_{j+1} rispetto al punto x_j,y_j e v_i individua il vertice con le coordinate x_i,y_i rispetto all'origine delle coordinate. Ovviamente, si ha
$ \max_i a_j\times v_i\geq a_j\times v_j $
e quindi
$ \sum\max_i a_j\times v_i\geq \sum a_J\times v_J=2S $
Da qui la tesi. (la convessità si usa nell'ultima uguaglianza).
Ultima modifica di EvaristeG il 16 lug 2006, 19:07, modificato 1 volta in totale.
Potere ai lacci delle scarpe!!!
Sì sì vado proprio fiero di questa dimostrazione post-caffè
Comunque più che geometria sembra algebra, o al massimo fisica...
Sì sì vado proprio fiero di questa dimostrazione post-caffè
Comunque più che geometria sembra algebra, o al massimo fisica...
Jack alias elianto84 alias jack202
http://www.matemate.it IL SITO
.::Achtung!!::. - Jordan causa nilpotenza -
http://www.matemate.it IL SITO
.::Achtung!!::. - Jordan causa nilpotenza -
-
MindFlyer
Qui sarebbe $ \max_i a_j\times v_i\geq a_j\times v_j $, tutto il resto funziona.EvaristeG ha scritto:Ovviamente, si ha $ \max_i a_j\times v_i\geq a_i\times v_i $
Stranissimo che per un problema IMO6 funzioni quella formula per le aree in modo così immediato, dev'essere sfuggito alla commissione.
Comunque complimenti a Jack per non averla esclusa a priori!
-
MindFlyer
AAARGH, mi sa che ci siamo presi tutti e 3 un bell'abbaglio con questa soluzione!!
In verità non funziona affatto, e l'errore sta nel segno di quel $ a_j \times v_j $, che è opposto a quello che vorremmo!
Mi spiego meglio: la formula che usa Jack fornisce un'area dotata di segno, e per la precisione l'area è positiva se i vertici del poligono convesso sono ordinati in senso antiorario, negativa altrimenti. La dimostrazione di questo fatto è semplice, e consiste nel prendere un punto nel piano e ridursi a dimostrarlo sui triangoli, ed infine ridursi al caso di un triangolo con un vertice nell'origine. In sostanza, l'area di un triangolo ABC può essere vista come Area(OAB)+Area(OBC)+Area(OCA), dove le aree sono dotate di segno a seconda dell'ordine dei vertici.
Ora, prendere j=i nell'ultimo passaggio equivale a considerare i triangoli del tipo $ P_iP_{i+1}P_i $, che hanno area 0. Ed infatti la nostra formula ci dà proprio Area($ OP_iP_{i+1} $)+Area($ OP_{i+1}P_i $)+Area($ OP_iP_i $). L'ultima area vale 0, le prime 2 sono uguali in modulo ma hanno segno opposto. Vediamo quindi che è vero che si può estrarre dalla sommatoria una quantità uguale all'area totale del poligono convesso (i termini che EvatisteG chiama "non dipendenti da i" nel punto 3), ma la seconda quantità che viene posta uguale all'area nel punto 4 ha invece segno negativo, ed ecco che magicamente va tutto a puttane.
In verità non funziona affatto, e l'errore sta nel segno di quel $ a_j \times v_j $, che è opposto a quello che vorremmo!
Mi spiego meglio: la formula che usa Jack fornisce un'area dotata di segno, e per la precisione l'area è positiva se i vertici del poligono convesso sono ordinati in senso antiorario, negativa altrimenti. La dimostrazione di questo fatto è semplice, e consiste nel prendere un punto nel piano e ridursi a dimostrarlo sui triangoli, ed infine ridursi al caso di un triangolo con un vertice nell'origine. In sostanza, l'area di un triangolo ABC può essere vista come Area(OAB)+Area(OBC)+Area(OCA), dove le aree sono dotate di segno a seconda dell'ordine dei vertici.
Ora, prendere j=i nell'ultimo passaggio equivale a considerare i triangoli del tipo $ P_iP_{i+1}P_i $, che hanno area 0. Ed infatti la nostra formula ci dà proprio Area($ OP_iP_{i+1} $)+Area($ OP_{i+1}P_i $)+Area($ OP_iP_i $). L'ultima area vale 0, le prime 2 sono uguali in modulo ma hanno segno opposto. Vediamo quindi che è vero che si può estrarre dalla sommatoria una quantità uguale all'area totale del poligono convesso (i termini che EvatisteG chiama "non dipendenti da i" nel punto 3), ma la seconda quantità che viene posta uguale all'area nel punto 4 ha invece segno negativo, ed ecco che magicamente va tutto a puttane.
Già, peccato per questo segno sbagliato. 
Ma forse si può rimettere in piedi... Lasciamo perdere la shoelace formula,
e prendiamo a_i come il vettore P_i P_{i+1}, v_i come il vettore
che va dal baricentro del poligono (è un punto interno) al vertice P_i.
La superficie di un triangolo è pari alla metà del valore assoluto
del prodotto vettore di due lati, e bisogna dimostrare che
$ \sum_{j} \max_{i} |a_j \times (v_i - v_j)|\geq 2\sum_{j}|a_j\times v_j| $
Ma forse si può rimettere in piedi... Lasciamo perdere la shoelace formula,
e prendiamo a_i come il vettore P_i P_{i+1}, v_i come il vettore
che va dal baricentro del poligono (è un punto interno) al vertice P_i.
La superficie di un triangolo è pari alla metà del valore assoluto
del prodotto vettore di due lati, e bisogna dimostrare che
$ \sum_{j} \max_{i} |a_j \times (v_i - v_j)|\geq 2\sum_{j}|a_j\times v_j| $
Jack alias elianto84 alias jack202
http://www.matemate.it IL SITO
.::Achtung!!::. - Jordan causa nilpotenza -
http://www.matemate.it IL SITO
.::Achtung!!::. - Jordan causa nilpotenza -
-
MindFlyer
Si può scrivere $ a_j=v_{j+1}-v_j $, e inoltre con l' ulteriore condizione $ \sum v_i =0 $, quelle sulla convessità (facilmente algebrizzabili) e quelle sull'ordine dei vettori (un po' meno agevole), si caratterizza completamente il problema in funzione dei soli vettori $ v_i $. Dubito che si arrivi a qualcosa in questo modo, ma tentar non nuoce. A voi l'algebra e i contazzi..elianto84 ha scritto:$ \sum_{j} \max_{i} |a_j \times (v_i - v_j)|\geq 2\sum_{j}|a_j\times v_j| $
-
pi_greco_quadro
- Messaggi: 158
- Iscritto il: 01 gen 1970, 01:00
- Località: Verona
permettete un'intromissione nella discussione anche se è passato un po' di tempo ma essendo stato in vacanza........ è un'idea che mi ronza nella testa da un po' di tempo.... magari l'avrete già pensata in tal caso non ci sarebbero problemi... comunque....
supponete di tracciare per ogni vertice una linea che divida il poligono in due parti uguali... ovviamente non è detto che queste linee passino anche per un altro vertice, ma questo non cambia nulla,infatti possiamo pensare di creare un nuovo vertice noi di 180° ed aggiungerlo, in questo modo si formeranno tante figure a "fiocco" che copriranno l'intera area del poligono...
Supponiamo di scegliere una di queste figure a "fiocco"... chiaramente l'area dei due triangoli che la compongono è uguale.... (si consideri che l'area di ognuno dei due triangoli più una parte in comune è uguale a metà poligono)
per fissare le idee... siano per esempio $ V_w,V_x,V_y,V_z $ quattro vertici e $ V_zV_w,\;V_xV_y $ i lati.. diciamo che $ I $ è il punto in cui si incontrano $ V_yV_z $ e $ V_xV_w $. Per quanto detto prima sappiamo che $ |V_zI|\cdot|V_wI|=|V_xI|\cdot|V_yI| $. Ne segue che o $ |V_wI|\geq |V_xI| $ oppure $ |V_zI|\geq |V_yI| $. Quindi ne consegue che uno tra $ V_xV_wV_y $ e $ V_zV_yV_x $ è almeno il doppio di $ V_xIV_y $, e similarmente ciò vale anche per l'altro lato.
Ma quindi avendo detto che la somma di tutte le nostre figure a "fiocco" è $ P $, procedendo in questo modo abbiamo ottenuto una serie di triangoli la cui somma è almeno $ 2P $.
Argh EvaG mi ha detto che tale soluzione è già stata pensata... vabbé ci ho pensato un mese ed era logico aspettarsi che qualcuno mooolto più bravo mi avesse battuto sul tempo... chiedo scusa a chiunque l'abbia pubblicata prima di me....
supponete di tracciare per ogni vertice una linea che divida il poligono in due parti uguali... ovviamente non è detto che queste linee passino anche per un altro vertice, ma questo non cambia nulla,infatti possiamo pensare di creare un nuovo vertice noi di 180° ed aggiungerlo, in questo modo si formeranno tante figure a "fiocco" che copriranno l'intera area del poligono...
Supponiamo di scegliere una di queste figure a "fiocco"... chiaramente l'area dei due triangoli che la compongono è uguale.... (si consideri che l'area di ognuno dei due triangoli più una parte in comune è uguale a metà poligono)
per fissare le idee... siano per esempio $ V_w,V_x,V_y,V_z $ quattro vertici e $ V_zV_w,\;V_xV_y $ i lati.. diciamo che $ I $ è il punto in cui si incontrano $ V_yV_z $ e $ V_xV_w $. Per quanto detto prima sappiamo che $ |V_zI|\cdot|V_wI|=|V_xI|\cdot|V_yI| $. Ne segue che o $ |V_wI|\geq |V_xI| $ oppure $ |V_zI|\geq |V_yI| $. Quindi ne consegue che uno tra $ V_xV_wV_y $ e $ V_zV_yV_x $ è almeno il doppio di $ V_xIV_y $, e similarmente ciò vale anche per l'altro lato.
Ma quindi avendo detto che la somma di tutte le nostre figure a "fiocco" è $ P $, procedendo in questo modo abbiamo ottenuto una serie di triangoli la cui somma è almeno $ 2P $.
Argh EvaG mi ha detto che tale soluzione è già stata pensata... vabbé ci ho pensato un mese ed era logico aspettarsi che qualcuno mooolto più bravo mi avesse battuto sul tempo... chiedo scusa a chiunque l'abbia pubblicata prima di me....