Va prezint in continuare solutiile. Este interesant de urmarit cum sunt gandite solutiile, care desi sunt echivalente sunt prezentate putin diferit.
*Stefan Ciobaca* generalizeaza problema:

<i>Eu as fi propus o generalizarea: ai <tex>2^n</tex> triedre drepte in n dimensiuni.

Eu as fi propus generalizarea: ai <tex>2^n</tex> triedre drepte in n dimensiuni.

Rezolvarea prin divide et impera: iei cele <tex>2^n</tex> puncte si le separi printr-un hiperplan astfel incat jumate sa fie de-o parte, jumate de cealalta parte s.a.m.d., avand in vedere ca toate hiperplanele sa fie perpendiculare intre ele. Evident, chestia asta se poate. Apoi, fiecare triedru il orientezi spre semisemisemi...semi spatiul total opus si cu marginile paralele cu axele de coordonate q.e.d.</i>

Rezolvarea prin divide et impera: iei cele <tex>2^n</tex> puncte si le separi printr-un hiperplan astfel incat jumate sa fie de-o parte, jumate de cealalta parte s.a.m.d., avand in vedere ca toate hiperplanele sa fie perpendiculare intre ele. Evident, chestia asta se poate. Apoi, fiecare triedru il orientezi spre semisemisemi...semi spatiul total opus si cu marginile paralele cu axele de coordonate q.e.d.

Imi place cum se vede defectul profesional de programator citind demonstratia.
Solutia lui *Radu*:

<i>Rezolvam prin inductie dupa nr de dimensiuni.

Rezolvam prin inductie dupa nr de dimensiuni.

In primul rand: fixezi o directie pt primul plan, il muti paralelel cu el insusi astfel incat sa separe punctele in 2 parti egale, 4 de o parte, 4 de alta (daca stau mai multe pe planul ala exact,nu conteaza, alegi cateva si le declari de o parte, sa fie 4 si restul de cealalta).
Apoi sa zicem ca le luam pe alea de deasupra:

 proiectiile lor pe planul respectiv sunt 4 puncte care conform inductiei (pt plan). Cu diedrele din plan faci triedre cu a 3-a dreapta in jos ca sa acopere semispatiul inferior la fel pt alea de sub plan pui dreapta a 3-a din triedru in sus ca sa acopere semispatiul inferior superior.</i>

 proiectiile lor pe planul respectiv sunt 4 puncte care conform inductiei (pt doua dimensiuni) acopera planul. Cu diedrele din plan faci triedre cu a 3-a dreapta in jos ca sa acopere semispatiul inferior. La fel pt alea de sub plan, pui dreapta a 3-a din triedru in sus ca sa acopere semispatiul superior.

Radu a lasat demonstratia putin incompleta avand incredere ca ma prind singur de cazul 2d si 1d.
Solutia lui *Catalin*:

<i>Ideea mea e sa gasesc o solutie in care triedrele au laturile orientate paralel cu axele, pentru simplitate.

Ideea mea e sa gasesc o solutie in care triedrele au laturile orientate paralel cu axele, pentru simplitate.

- Rotim sistemul astfel incat sa nu existe doua lanterne cu coordonate X, Y sau Z egale (pentru a scapa de cazuri particulare).

va lumina catre sensul pozitiv al axei Ox si catre sensurile negative ale axelor Oy si Oz; cu alte cuvinte, ea va lumina punctul de coordonate (+inf, -inf, -inf).

Dandu-se un punct P(x,y,z), trebuie demonstrat ca exista o lanterna care il lumineaza. Analizam coordonata x. Datorita constructiei, x va fi fie mai mare decat toate coordonatele x ale lanternelor marcate cu X+, fie mai mic decat toate coordonatele x ale lanternelor marcate cu X- (fie ambele, daca x este situat intre cele doua grupuri de 4 lanterne). Alegem acel set de 4 lanterne si reluam rationamentul pe axele Oy si Oz. in final, obtinem minim o lanterna care lumineaza punctul P.</i>

Dandu-se un punct P(x,y,z), trebuie demonstrat ca exista o lanterna care il lumineaza. Analizam coordonata x. Datorita constructiei, x va fi fie mai mare decat toate coordonatele x ale lanternelor marcate cu X+, fie mai mic decat toate coordonatele x ale lanternelor marcate cu X- (fie ambele, daca x este situat intre cele doua grupuri de 4 lanterne). Alegem acel set de 4 lanterne si reluam rationamentul pe axele Oy si Oz. in final, obtinem minim o lanterna care lumineaza punctul P.

Si la Catalin se vede programatorul din spatele solutiei. Se observa structura solutiei pe baza vectorilor de cate 3 elemente in baza 2.

Si la Catalin se vede programatorul din spatele solutiei. Se observa cum structura rezolvarii este bazata pe vectorii de cate 3 elemente in baza 2.

*Stefan Istrate* are o solutie foarte misto, cu desene dragute, pe care o gasiti pe 'forum':http://infoarena.ro/forum/index.php?topic=2218.0 . Merita sa o cititi!

La solutia lui Stefan Ciobaca si cea a lui Catalin Francu nu e demonstrata ipoteza ca _putem gasi un sistem de coordonate in care toate punctele au coordonatele x1, x2, .. respectiv diferite_ . Va incurajez sa va incercati puterile pe aceasta subproblema in sectiunea de 'comentarii':http://infoarena.ro/forum/index.php?topic=2222.0

O problema similara a fost propusa la un ACM in regiunea din Nord Estul Europei: _Se cere iluminarea planului cu n lanterne ce pot fi rotite (n <= 30) de coordonate date, al caror fascicul emitea lumina sub un unghi de marime 2pi/n. Pentru fiecare lanterna trebuia returnata orientarea ei._ Cred ca la aceasta problema, pe langa solutia ei, e interesant si algoritmul folosit pentru evaluarea corectitudinii unui rezultat.

O problema similara a fost propusa la un ACM in regiunea din Nord Estul Europei: _Se cere iluminarea planului cu n lanterne (n <= 30) de coordonate date, ce pot fi rotite, al caror fascicul emite lumina sub un unghi de marime 2pi/n. Pentru fiecare lanterna trebuie returnata orientarea ei._ La aceasta problema, pe langa solutia ei, e interesant si algoritmul folosit pentru evaluarea corectitudinii unui rezultat.

Pentru mai multe probleme interesante cu lanterne puteti citi urmatoarele lucrari:

<i>Bose, J., L. Guibas, A. Lubiw, M. Overmars, D. Souvaine and J. Urrutia, '"The floodlight illumination problem"':blog/alta-problema-misto-solutie?TheFloodProb.ps
Czyzowicz, J., E. Rivera-Campo and J. Urrutia, '"Optimal floodlight illumination of stages"':blog/alta-problema-misto-solutie?OptFloStages.ps </i>
 
 
'Comentarii':http://infoarena.ro/forum/index.php?topic=2222.0

Bose, J., L. Guibas, A. Lubiw, M. Overmars, D. Souvaine and J. Urrutia, '"The floodlight illumination problem"':blog/alta-problema-misto-solutie?TheFloodProb.ps
Czyzowicz, J., E. Rivera-Campo and J. Urrutia, '"Optimal floodlight illumination of stages"':blog/alta-problema-misto-solutie?OptFloStages.ps

2222