73. Problema di minimo dal sapore ungherese

Rette, triangoli, cerchi, poliedri, ...
machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

73. Problema di minimo dal sapore ungherese

Messaggio da machete » 05 mag 2014, 22:27

Sia $XYZ$ un triangolo isoscele e rettangolo in $X$ con cateti unitari. Trovare, al variare di $P$ all' interno di esso, il minimo di:
$$
f(P)=14 \cdot PX+13\cdot PY+15\cdot PZ
$$
Ho tratto l' idea per questo problema dal problema 20 della Kavics Kupa 2014. In realtà più che il numero mi interessa il procedimento e se avete un algoritmo per risolverlo (magari con conti arbitrariamente brutti, ma sempre "algebrici") nel caso di tre pesi "generici" (io per il momento credo di averlo solo se i pesi sono lati di un triangolo. . . )

Dunque buon divertimento, o geometri, spero di esser stupito con soluzioni eleganti e concise e profonde :D
Spargi il defoliante
sulla cassa dirigente
[anonimo]

machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da machete » 16 mag 2014, 20:51

Metto un hint(one?) verso l' idea che ho usato io:
Testo nascosto:
guardate come questo tizio risolve il problema di trovare in un triangolo il punto che minimizza la somma delle distanze dai vertici:
http://www.youtube.com/watch?v=uP8V-O8hncI
Spargi il defoliante
sulla cassa dirigente
[anonimo]

Avatar utente
Drago96
Messaggi: 1137
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Drago96 » 18 mag 2014, 18:07

Wow, figo il fatto che il gradiente della distanza è un versore radiale! :D
Boh, poi magari tento dei conti, ora purtroppo non posso :(
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da machete » 21 mag 2014, 16:14

Vero? :) E' un fatto semplice ma che porta immediatamente ad una caratterizzazione del minimo! In ogni caso serve dell' altro lavoro per trovare il risultato! (che, grazie ai numeri dati, è bello)
Spargi il defoliante
sulla cassa dirigente
[anonimo]

Avatar utente
Drago96
Messaggi: 1137
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Drago96 » 21 mag 2014, 16:29

Ehi, idea al volo: i tre vettori devono avere somma 0, ovvero devono formare una spezzata chiusa; ma sono i lati di un triangolo, quindi possiamo ricavare i vari angoli grazie a Carnot. Ovvero, detto $\alpha $ l'angolo tra quello da 13 e quello da 15 abbiamo $14^2=13^2+15^2-2\cdot14\cdot15\cdot\cos (\pi-\alpha) $, da cui ricaviamo i tre angoli e quindi con qualche altro conto si dovrebbe riuscire a determinare il valore della funzione (sempre Carnot, suppongo)
Mi scuso per la soluzione a spezzoni, ma proprio non ho tempo :(
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

machete
Messaggi: 52
Iscritto il: 28 ago 2012, 15:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da machete » 21 mag 2014, 18:22

Bene Drago :D l'idea del triangolo è giusta e proficua, ma ovviamente va sviluppata a modino! Quando hai un po' di tempo butta giù il procedimento fino alla fine e fai il contozzo, uscirne senza morire è (la) parte (facile) dell' esercizio!

p.s. : e ricorda che l' annullarsi del gradiente è necessario, non sufficiente alla minimezza!

p.p.s. : e, IMPORTANTISSIMO, non dimenticare di controllare i bordi dei bordi!
Spargi il defoliante
sulla cassa dirigente
[anonimo]

fph
Site Admin
Messaggi: 3582
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da fph » 21 mag 2014, 20:49

machete ha scritto: p.s. : e ricorda che l' annullarsi del gradiente è necessario, non sufficiente alla minimezza!

p.p.s. : e, IMPORTANTISSIMO, non dimenticare di controllare i bordi dei bordi!
Sbaglio o anche il tizio del tuo video non si preoccupa troppo dei bordi e della differenza tra "gradiente nullo" e "minimo"?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
Drago96
Messaggi: 1137
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Drago96 » 22 mag 2014, 16:37

Orbene, tentiamo quest'arrembaggio all'analisi in più variabili...
Intanto mettiamo questo nostro triangolo, che se non ti dispiace chiamerò $\triangle ABC$, nel piano $Oxy$, in modo che $A=(0,0),B=(1,0),C=(0,1)$.
Prendiamo un generico punto $P$ di coordinate $(x,y)$ e definiamo $$f_A(x,y)=dist(P,A)=\sqrt{x^2+y^2} \\ f_B(x,y)=dist(P,B)=\sqrt{(x-1)^2+y^2} \\ f_C(x,y)=dist(P,C)=\sqrt{x^2+(y-1)^2}$$
Ovviamente quindi $$f(x,y)=14\cdot f_A(x,y)+13\cdot f_B(x,y)+15\cdot f_C(x,y)$$
Sfruttando ora il fatto che la derivata di $g(x)=\sqrt x$ è $g'(x)=\dfrac1{2\sqrt x}$, ci calcoliamo il gradiente delle tre funzioni, che risulta essere (risparmiatemi i passaggi stupidi) $$\nabla f_A(x,y)=\left\langle\dfrac{x}{\sqrt{x^2+y^2}},\dfrac{y}{\sqrt{x^2+y^2}}\right\rangle \\ \nabla f_B(x,y)=\left\langle\dfrac{x-1}{\sqrt{(x-1)^2+y^2}},\dfrac{y}{\sqrt{(x-1)^2+y^2}}\right\rangle \\ \nabla f_C(x,y)=\left\langle\dfrac{x}{\sqrt{x^2+(y-1)^2}},\dfrac{y-1}{\sqrt{x^2+(y-1)^2}}\right\rangle$$
Come ben si nota, ciascuno di essi è un vettore di lunghezza unitaria, la cui direzione è la stessa della retta che collega $P$ al rispettivo vertice e il cui verso è dalla parte opposta del vertice rispetto a $P$.
Il gradiente della somma è ovviamente la somma dei gradienti per la linearità della derivata; per trovare un punto critico -che speriamo vivamente essere il minimo-, dobbiamo imporre $$\nabla f(x,y)=\langle0,0\rangle$$ quindi alla fine ci troviamo a dover sistemare tre vettori di lunghezza $13,14,15$ in modo che sommino $0$.
Allora, notiamo intanto che sono le misure dei lati di un triangolo (per disuguaglianza triangolare -- inoltre $13=6+7,14=6+8,15=7+8$), quindi se li disponiamo a triangolo con i versi tutti nello stesso senso otteniamo una figura chiusa, ovvero la somma vettoriale è nulla. (occhio: in realtà non li possiamo disporre a triangolo, devono avere il punto di applicazione in comune, ma basta traslarli) Ora inizia la parte di conti!
Chiamiamo $\alpha$ l'angolo che c'è tra il vettore di $13$ e quello di $15$, che è uguale all'angolo $\angle BPC$; definiamo similmente $\beta$ e $\gamma$. Ora con un bel disegnino vediamo che se trasliamo i vettori a formare un triangolo, i suoi angoli sono di $\pi-\alpha$ e cicliche; quindi con Carnot ci calcoliamo i coseni: $$14^2=13^2+15^2-2\cdot13\cdot15\cdot\cos(\pi-\alpha) \\ 13^2=14^2+15^2-2\cdot14\cdot15\cdot\cos(\pi-\beta) \\ 15^2=13^2+14^2-2\cdot13\cdot14\cdot\cos(\pi-\gamma)$$ ovvero $$\displaystyle \cos\alpha=-\frac{33}{65},\;\;\cos\beta=-\frac{3}{5},\;\;\cos\gamma=-\frac{5}{13}$$
abbiamo fatto un passettino avanti, ma dobbiamo determinare $AP,BP,CP$... intanto diamogli un nome decente: $AP=a$ e cicliche; dato che mi voglio male, tento di impostare un sistema con Carnot, che alla peggio si risolverà con wolframalpha...
$$\begin{cases}2=b^2+c^2-2bc\cos\alpha \\ 1=c^2+a^2-2ac\cos\beta \\ 1=a^2+b^2-2ab\cos\gamma \end{cases}$$
Ora, WA ci dice che per la soluzione di questo sistema vale $f(P)=\sqrt{730}$, ma sinceramente non saprei risolvere quel sistema, se non provando a sostituire cose (e ciò è molto male in un sistema di secondo grado), quindi potrebbe esserci un metodo più intelligente per trovare il nostro caro $P$.
Bene, abbiamo quindi ricavato (prima o poi tenterò di ricavarlo da me) che in corrispondenza del punto in cui si annulla il gradiente abbiamo $f(P)=\sqrt{730}$; siamo già molto felici che il punto critico sia uno solo, controlliamo solo che sia un minimo e non un massimo (e se così non fosse, uno si arrabbia di brutto): prendiamo ad esempio il circocentro e otteniamo $f(O)=\dfrac{\sqrt2}2(13+14+15)=21\sqrt2$, che è fortunatamente maggiore di $f(P)$. Ora suppongo che questo mi basti a concludere: dovrei controllare sui bordi per vedere se ho un valore più basso, anche se il gradiente non si annulla (cosa che può accadere), ma questo non dovrebbe poter succedere dato che per scendere dovrei risalire, ma non ho un altro punto critico; non so se sia legittimo quello che ho detto, se no mi servirebbe una cosa tipo convessità della funzione, che si dovrebbe fare controllando la positività della derivata rispetto a $x$ dellla componente $x$ del gradiente e la stessa cosa con $y$... (in questo caso effettivamente vengono entrambi positivi)
Qualcuno mi aiuta a formalizzare l'ultima parte? :)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da <enigma> » 22 mag 2014, 17:38

Prendi $f(x,y)=x^3+y^3$ e un qualsiasi triangolo per cui $(0,0)$ è un punto interno, ripetendo il ragionamento col gradiente: cosa ottieni?
La derivata seconda (più precisamente l'Hessiana di $f$) basta, ma non liquidare con leggerezza quel che succede sul bordo (e finisci i conti) :wink:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da <enigma> » 22 mag 2014, 17:47

Giusto per tua cultura: $f \in \mathcal C^2(K)$ è convessa in $K$ se e solo se l'Hessiana di $f$ in $K$ è semidefinita positiva. O-equivalenza che torna più utile computazionalmente-se e solo se gli autovalori dell'Hessiana sono non negativi.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
Drago96
Messaggi: 1137
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Drago96 » 22 mag 2014, 18:48

<enigma> ha scritto:Prendi $f(x,y)=x^3+y^3$ e un qualsiasi triangolo per cui $(0,0)$ è un punto interno, ripetendo il ragionamento col gradiente: cosa ottieni?
Che l'unico punto critico è $(0,0)$, ma nel primo e nel terzo quadrante cresce e decresce a volontà... il fatto è che appunto non è "convessa"...
<enigma> ha scritto:La derivata seconda (più precisamente l'Hessiana di $f$) basta, ma non liquidare con leggerezza quel che succede sul bordo (e finisci i conti) :wink:
Uhm, vedrò di studiarmelo... però scusa: se io prendo un piano $x=k$ e seziono la funzione, e vedo che per ogni $k$ la mia funzione "sezionata" è convessa (sul piano), e anche per quanto riguarda l'altra variabile prendendo i piani $y=k$ ho tutte funzioni convesse (sul piano), mi basta a poter dire che la funzione nello spazio è convessa? Perché? Perché no?
Per i bordi, cosa intendi? Cosa dovrei controllare bene?
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
Kfp
Messaggi: 188
Iscritto il: 20 mag 2012, 19:17
Località: Brescia

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Kfp » 22 mag 2014, 21:30

forum ha scritto:Geometria
Drago96 ha scritto: Analisi in più variabili
Non c'è più religione.
"Signora, lei sì che ha le palle, mica come quella checca di suo figlio"

"La zuppa magica dedicata a te Gianluca"

"È "iamo", non rompere i coglioni"

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Troleito br00tal » 22 mag 2014, 21:46

Kfp ha scritto:
forum ha scritto:Geometria
Drago96 ha scritto: Analisi in più variabili
Non c'è più religione.
Più che altro come cazzo faceva sto problema a stare in una gara per liceali...

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da <enigma> » 23 mag 2014, 14:30

Drago96 ha scritto:Uhm, vedrò di studiarmelo... però scusa: se io prendo un piano $x=k$ e seziono la funzione, e vedo che per ogni $k$ la mia funzione "sezionata" è convessa (sul piano), e anche per quanto riguarda l'altra variabile prendendo i piani $y=k$ ho tutte funzioni convesse (sul piano), mi basta a poter dire che la funzione nello spazio è convessa? Perché? Perché no?
Prendi $f(x,y)=x^2y^2$ nel primo quadrante. La restrizione a qualsiasi retta parallela agli assi coordinati è convessa? Ci mancherebbe altro, è una parabola convessa. La funzione è convessa? Come no...

Non bastano le derivate seconde. Volendo proprio riformulare la condizione che ho scritto in termini di derivate seconde, un'equivalenza è:
$f \in \mathcal C^2(K)$ è convessa nel convesso $K$ $\iff$ $\partial_{xx}f \geq 0$, $\partial_{yy}f \geq 0$ e $\partial_{xx}f\ \partial_{yy}f \geq (\partial_{xy}f)^2$ in $K$.
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: 73. Problema di minimo dal sapore ungherese

Messaggio da Gottinger95 » 23 mag 2014, 23:38

Comunque, che la funzione distanza sia convessa lo si può verificare facilmente anche geometricamente: prendiamo un punto \(P\) di riferimento, e due punti \(A,B\) nel piano. Convessità vorrebbe che, detta \( f(\vec{X})\) la funzione distanza da \(P\), per qualsiasi \(t \in [0,1]\) si abbia
\[ f( t \cdot \vec A + (1-t) \cdot \vec B ) \le t \cdot f(\vec A) + (1-t) \cdot f( \vec B) \]
Sia \(C\) il punto sul segmento \(AB\) tale che \(AC = t \cdot AB\). Prendiamo un punto \(A'\) su \(AP\) tale che \(CA'\) sia parallelo a \(BP\): per talete \(PA'\) misura \(t \cdot AP\). Similmente definiamo \(B'\). Allora abbiamo, per disuguaglianza triangolare (e per \( B'P \parallel CA'\) )
\[ t \cdot f (\vec A) + (1-t) \cdot f(\vec B) = t \cdot AP + (1-t) \cdot BP = A'P + B' P = A'P + CA' \ge CP = f( t \cdot \vec A + (1-t) \cdot \vec B )\]
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Rispondi