Problema: Suma in triunghi

[•Cosmin]

http://infoarena.ro/blog/suma-in-triunghi

[•alex_ovidiunitu]

Se observa lungimile laturilor sunt numere pitagoreice (5*5=4*4+3*3), deci triunghiul ABC este dreptunghic in A.
Cred ca M se va afla pe mijlocul ipotenuzei iar suma va fi 10. 

[•oriana]

daca M coincide cu C atunci suma e 13 ... 

[•alex_ovidiunitu]

Ai dreptate. Am dat raspunsul fara sa analizez mai bine problema.

[•steluta]

M poate fi si pe laturi sau strict in interior? 

[•Cosmin]

Poate fi si pe laturi.

[•floringh06]

Am sa incerc sa formulez si eu o solutie la problema asta.  

Am intalnit problema cu varfurile triunghiului aleatoare si suma 2MA + MB + MC trebuia sa fie minima.
Problema a fost la o regionala prin Asia in 2009 parca si se rezolva cu doua cautari ternare ceea ce
duce la complexitatea log(n)^2.

Am sa explic putin solutia de mai sus cu aplicatie in problema noastra.
De ce merge cautarea ternara? Fie M = (x, y). Functia f(x,y) = 2MA + MB + MC este o functie
convexa pentru y fixat si x variabil. Astfel pentru triunghiul dreptunghic de mai sus, daca vrem
sa maximizam f, tragem concluzia ca M nu poate fi decat pe marginea triunghiului.

Cazurile in care M este pe AB sau AC sunt similare. In ambele cazuri e clar ca este eficient ca M
sa fie cat mai departe de A, cu alte cuvinte coincide cu B sau C.
Cazul in care M este este pe BC nu este mult mai diferit. Oriunde s-ar afla M pe BC, valuarea lui
f(x, y) - 2*MA este egala cu BC. De aici tragem concluzia ca problema noastra s-a redus la a gasi
M pe BC astfel incat 2*MA sa fie maxim. Astfel ajungem la solutia M = C si anume f(x, y) = 13.


[Moderator] In general e corect ce zici. Dar nu ai nevoie de cautare ternara. Daca ne uitam pe o latura a triunghiului acolo tot o functie convexa ai, deci singurele locuri unde poate fi maximul sunt la capetele laturii. Deci e suficient sa te uiti la varfuri ca sa rezolvi problema.

Sper ca nu am povestit prostii mai sus

[•Cosmin]

Heh, ai spoiluit-o . Daca o stii dinainte, lasa-i pe restu sa se mai gandeasca. Pune te rog mesajul din nou mai tarziu.

[•rgrig]

Heh, ai spoiluit-o . Daca o stii dinainte, lasa-i pe restu sa se mai gandeasca. Pune te rog mesajul din nou mai tarziu.

Tocmai vroiam să scriu ultima parte cu "dacă e pe margini, atunci e C." Hai c-o scriu chiar dacă am văzut mesajul, dar omit partea pe care am văzut-o dar n-o făcusem.

Să vedem ce se întâmplă pe margini. Să zicem că M este pe AC. Dacă îl deplasăm cu un delta spre C atunci MC scade cu delta, 2MA crește cu 2 delta și MB crește și el. Per total, funcția crește când mergem spre C. Similar, pe AB crește când mergem spre B.

Să luăm acum M pe latura BC. Acum MB+MC e constant oriunde am lua Mul, așa că e bine să fim cât mai departe de A. Adică suma e minimă acolo unde cade înălțimea din A și crește pe o parte și pe alta.

În concluzie, maximul e fie la B fie la C. Verificând, vedem că e la C.

Mai rămâne de văzut dacă maximul poate fi în interior.

[•MciprianM]

O solutie neeleganta (sper ca si corecta):
Luam A (0,0), B (0, 3), C (4, 0). Generic M (x, y), unde y poate fi intre  zero si 3, iar x depinzand de y, intre 0 si 4 - (4/3)y  (Teorema lui Thales: x/4 = (3-y)/3).
Acuma 2MA + MB + MC = 2sqrt (x^2 + y^2) + sqrt (x^2 + (y - 3)^2) + sqrt ((x - 4)^2 + y^2),
care se vede ca pentru y fixat e cu atata mai mare cu cat x e mai mare (x >= 0) si atunci luam x = 4 - (4/3)y, adica M e pe ipotenuza. Raspunsul final 13 (folosind demonstratiile de mai sus sau, inlocuind in ecuatie pe x -> 2MA + MB + MC = 5 + 2 sqrt (25(y^2)/9 - 32y/3 + 16) care e mai mare cu cat functia de gradul 2 din interiorul radicalului e mai mare 25/9 > 0 asa ca functia tine apa si e mai mare pe unul din capete y: 0 sau 3 Suma ceruta are astfel valoarea maxima max (11,13).)

Selectati pentru solutia de mai sus 

[•floringh06]

@cosmin: Solutia oficiala era cu cautari ternare . Acolo nu spuneau nimic de reducerea la varfuri.