Din GInfo 7/99 SOLUȚIILE problemelor propuseVă prezentăm în continuare câteva din soluțiile oficiale pentru problemele propuse în cadrul taberei de pregătire de la Sinaia. Soluțiile aparțin autorilor problemelor
P079902: La cinemaObservăm că există trei cazuri: l dacă permutarea dată este cea identică, numărul necesar de minute este 0; l dacă permutarea dată conține numai cicluri de lungine 2, numărul necesar de minute este 1; l dacă permutarea conține cel puțin un ciclu de lungime mai mare decât 2, atunci numărul necesar de minute este 2. În cazul 3 se acționează separat pentru fiecare ciclu din interiorul permutării. Fie ciclul de lungime p: a1 a2 a3 ... ap-2 ap-1 ap a2 a3 a4 ... ap-1 ap a1 În primul minut schimbăm a1 cu ap, a2 cu ap-1 etc. Dacă ciclul are lungime impară, atunci elementul din mijloc rămâne neschimbat. Se va ajunge la următoarea configurație: a1 a2 a3 ... ap-2 ap-1 ap a1 ap ap-1 ... a4 a3 a2 În cel de-al doilea minut schimbăm a2 cu ap, a3 cu ap-1 etc. Remarcăm că astfel am și ajuns la configurația dorită: a1 a2 a3 ... ap-2 ap-2 ap a1 a2 a3 ... ap-2 ap-1 ap Se procedează în mod analog pentru fiecare ciclu, ajungându-se în final la permutarea identică.
P079905: Fire Există cel puțin două soluții care îi permit electricianului să descopere corespondența dintre capetele firelor în doar două mișcări, adică o coborâre în beci și o urcare în pod. Deoarece nu se poate rezolva problema în mai puțin de două mutări pentru nici un caz, aceste soluții sunt optime. Pentru prima soluție vom considera întâi cazul în care numărul de fire este impar. Pentru a putea prezenta mai ușor acest caz, vom considera, de exemplu, numărul de fire egal cu 11. În pod, electricianul scurtcircuitează cinci perechi de fire (ele sunt legate prin linii punctate în figura 1), lăsând liber un fir. Apoi coboară în beci și identifică capetele de jos ale perechilor scurtcircuitate. Notează capetele de jos cum se vede în figura 1 și apoi le scurtcircuitează așa cum arată liniile punctate.
Fig. 1 Fig. 2 Urcând din nou în pod, electricianul înlătură toate scurtcircuitele, dar lasă firele împreună pe porțiuni insulare, astfel încât perechile să fie acum identificabile. Verifică apoi continuitatea dintre firul liber (despre care știe că este capătul de sus a firului F) și un alt fir. După ce a găsit celălalt fir, el poate imediat să-l noteze cu E2 și să-i identifice perechea E1. Apoi verifică continuitatea dintre E1 și un alt capăt, care, odată găsit, poate fi notat cu D2 și perechea lui cu D1. Continuând în același fel, capetele rămase sunt ușor identificate. Se observă că procedeul este valabil pentru orice număr impar de fire. Pentru un număr par de fire (cu excepția lui doi) se poate aplica procedeul de mai sus puțin modificat. De exemplu, să admitem un al 12-lea fir în extrema dreaptă a figurii 1. Aceleași 5 perechi sunt scurtcircuitate, în pod rămânând două fire libere. În beci, firele sunt scurtcircuitate ca înainte, iar al 12-lea fir este notat cu G. Revenind în pod, electricianul identifică ușor pe G ca fiind singurul fir rămas liber dintre cele două fire libere inițial. Restul de 11 fire se notează așa cum s-a explicat mai sus. Un procedeu mai eficient, care ține seama de toate cazurile, este prezentat în continuare pentru 15 fire (figura 2). Electricianul scurtcircuitează în pod firele în grupe de câte 1, 2, 3, 4 și 5 notate respectiv cu A, B, C, D, E. Ultima grupă nu trebuie să fie completă. Apoi coboară în beci și identifică grupele. Numerotează firele și le scurtcircuitează în grupele Z, Y, X, W, V. Urcând din nou în pod, electricianul înlătură scurtcircuitările. Acum el poate identifica firele fără nici o problemă. Firește, A este firul 1. Firul 3 este singurul din grupa B care este conectat cu 1. Perechea lui este 2. În grupa C, firul 6 se conectează cu 1 și firul 5 cu 2. Firul rămas în C va fi 4. Se aplică același procedeu și în continuare. Metoda se aplică identic pentru orice număr de fire.
P079906: Ora de gimnasticăNumărul de configurații (o configurație reprezintă un mod de aranjare a elevilor din cerc) fiind finit (în număr de 2n), la un moment dat configurațiile vor începe să se repete. Problema cere deci să se afle baza și perioada cu care ciclează aceste configurații. Baza reprezintă numărul de pași după care configurațiile încep să cicleze, iar perioada reprezintă lungimea unui ciclu. Datorită numărului foarte mare de configurații, memorarea tuturor configurațiilor este imposibilă. De aceea, se va folosi următorul algoritm: Pasul 1. Inițial, vom reține în două variabile A și B configurația inițială: NA=0, NB=0, NA și NB reprezentând câți pași am făcut pentru a realiza configurația A, respectiv configurația B, din configurația inițială. Pasul 2. Avansăm în A cu un pas, iar în B cu 2 pași; NA=NA+1; NB=NB+1. Pasul 3. Dacă A și B nu rețin două configurații identice, atunci repetăm Pasul 2. Pasul 4. În acest moment NB-NA reprezintă un multiplu al perioadei. Pentru a afla efectiv perioada, pornim de la A si numărăm câți pași am realizat pentru a ajunge din nou în configurația A. Pentru a găsi baza, pornim de la configurația inițială și numărăm câți pași am realizat pentru a ajunge în configurația A. Pasul 5. Știind baza B și perioada P, configurația la care se ajunge după K pași este configurația la care ajunge după doar B+(K-B) mod P pași.
Algoritmul de aflare a bazei și a perioadei, prezentat mai sus, se bazează pe faptul că diferența dintre NA și NB crește la fiecare pas cu o unitate, deci în mod sigur configurațiile reținute în A și B vor fi egale după un număr de pași care este egal cu lungimea perioadei sau cu un multiplu al acesteia.
P079907: OrigamiO abordare brute force a acestei probleme ar cere menținerea unei structuri de date ce descrie starea colii de hârtie de pe masa mașinii. Desigur, zonele de o anumită grosime formează o reuniune de poligoane, prin urmare putem menține o listă de perechi de forma (grosime, listă de poligoane) unde listă de poligoane reprezintă lista zonelor colii în care avem grosime pliuri suprapuse. Inițial avem deci o singură zonă (un singur poligon) de grosime 1, și anume pătratul (0, 0, 100, 100). La fiecare îndoire trebuie să facem următoarele operații: l determinăm poligoanele "tăiate" de linia de îndoire și le descompunem în două; l oglindim poligoanele dintr-unul din semiplane în celălalt; l intersectăm poligoanele astfel suprapuse; l pentru fiecare poligon rezultat din intersecție, calculăm grosimea (numărul de pliuri) ca sumă a grosimilor poligoanelor din care provine. Desigur că o astfel de rezolvare este corectă, dar implementarea este foarte anevoioasă.
Soluția mai simplă pornește de la observația că avem nevoie doar de grosimea origami-ului în punctele candidate pentru efectuarea perforației. Cum putem calcula grosimea într-un astfel de punct? Ne uităm la ultima îndoire efectuată: dacă punctul se află în semiplanul dinspre care se face îndoirea, atunci grosimea este evident 0 (tocmai am pliat ce era acolo); dacă punctul se află în semiplanul spre care se face îndoirea, atunci pliurile din acel punct sunt cele dinainte de îndoire plus cele ce au venit în urma îndoirii. Ca urmare, grosimea este grosimea inițială în acel punct plus grosimea inițială în punctul simetric față de linia de îndoire. Bineînțeles, inițial coala are grosimea 1 în interiorul pătratului (0, 0, 100, 100) și 0 în rest. Prin urmare, algoritmul este următorul:
var t:array of linie; { lista de îndoiri } n:Integer; { numărul de îndoiri } function grosime(p:punct; k:Integer); { calculează grosimea în punctul p, } { după primele k îndoiri } begin if k=0 then if p in patrat(0,0,100,100) then grosime:=1 else grosime:=0
else if stanga(p,t[k]) then grosime:=grosime(p,k-1)+ grosime(simetric(p,t[k]),k-1) else grosime:=0 end;
Implementarea recursivă are avantajul simplității, fiind o traducere directă a celor prezentate anterior. Nu insistăm aici asupra calculului simetricului unui punct fața de o dreaptă sau asupra determinării de ce parte se găsește un punct față de o dreaptă. Mai remarcăm faptul că numărul de apeluri ale funcției grosime crește exponențial cu numărul de îndoiri, dar că și în cazul primei abordări (prin crearea unei liste de zone poligonale cu grosimile corespunzătoare) complexitatea algoritmului este exponențială în numărul de îndoiri, deoarece însuși numărul de zone poligonale poate crește exponențial.
P079908: PermanentEste evident că, similar ca și în cazul determinantului, înmulțind elementele de pe o linie (sau coloană) a matricei cu o constantă k, valoarea permanentului crește de k ori. Rezultă imediat că putem "scoate în fața permanentului" o constantă dacă împărțim o linie (coloană) la acea constantă. Inițial trebuie să calculăm permanentul matricei . Se observă că pe linia i putem da factor comun valoarea i și permanentul matricei A devine perm A=n!-perm B, unde . Din nou se observă că pe coloana i putem da factor comun valoarea i și permanentul matricei A devine perm A=(n!)2-perm C, unde . Este evident că permanentul acestei matrice este n! deoarece fiecare produs din dezvoltarea permanentului este 1 și există n! astfel de produse care sunt însumate. În concluzie avem perm A=(n!)3, deci problema se reduce la a determina numărul de cifre al lui (n!)3. Orice număr zecimal N poate fi scris sub forma N=10lg N; de aici rezultă imediat că numărul de cifre al lui N este [lg N]+1. Am redus problema la calculul valoarii , număr care este egal cu 3lg n!+1. Există mai multe posibilități pentru calculul valorii lg n!, cea mai rapidă fiind transformarea logaritmului zecimal în logaritm natural și folosirea formulei lui Stirling. Formula de transformare din logaritm zecimal în logaritm natural este , iar formula lui Stirling este: , unde , adică , iar este un termen care evident tinde la 0, deci poate fi considerat nul (în cazul nostru erorile vor fi nesemnificative). În concluzie numărul de cifre al permanentului matricei A va fi:
P079909: PitagoraPentru ca trei numere a, b și c (a < b < c) să poată fi laturile unui triunghi dreptunghic ele trebuie să satisfacă relația a2+b2=c2 (teorema lui Pitagora). Cunoscând numărul a trebuie să determinăm perechi de numere b și c pentru care a2=c2-b2, adică a2=(c+b)(c-b). Datorită faptului că a, b și c sunt numere naturale, înseamnă că (c-b) va trebui să fie divizor al lui a2. Pentru a determina perechile cerute vom considera toți divizorii d ai lui a2 și vom rezolva sistemul de două ecuații liniare:
Rezolvând sistemul obținem și . La sfârșit va trebui să verificăm dacă numerele b și c obținute în acest mod satisfac condiția suplimentară a<b<c.
[cuprins] |