Mai tineti minte prizonierii din inchisoare? A fost oferita in timpul regulamentar o solutie si inca una in afara acestui timp (solutia lui dadatroll). Solutia a doua parea a functiona mai bine pentru ca toti prizonierii aveau o sansa sa decida salvarea lor. Am rulat un script (in python, anexat) si am obtinut ca solutia lui dadatroll nu este convenabila. Asadar, nu i se ofera punctaj lui (orice rezolvarea a problemelor nerezolvate la timp se puncteaza cu jumatate de punctaj).
Daca veti rula scriptul pentru 5 prizonieri (este impractica solutia pentru mai mult de 10 prizonieri) veti obtine ca dadatroll si-ar salva colegii in 160 (maxim 596, minim 6) zile, pe cand iulia si ciprian in 30 (maxim 59, minim 11) zile. Solutia lor e mai concentrata in jurul mediei (abatere patratica medie mica), solutia lui dadatroll ruleaza mult mai bine in anumite cazuri, dar densitatea lor este prea mica fata de celelalte. Asadar, dadatroll a esuat.
Un alt prizonier, auzind solutia lui dadatroll a propus a treia metoda: asteptam xN zile, unde x este un numar real, si oricine ajunge in ziua x in camera cu becul va spune ca am fost toti in camera. Becul il vom aprinde si stinge la intamplare, doar pentru a da impresia ca-l folosim. Acum, trebuie determinat x astfel incat sa fie o sansa mare sa scapam toti, aproape de unitate. De exemplu pentru x=10 suntem salvati in proportie de 99,992%, acceptabil.
Intrebari: determinati dependenta numarului de zile in care scapa prizonierii urmand solutia oficiala (cea data de iulia) si valoarea lui x, minima, pentru care se obtine un procentaj mai mare de 99,99%. Se ofera cate un punct pentru ambele raspunsuri. Daca se si demonstreaza matematic formula dependentei numarului de zile, se mai ofera inca un punct respectivei persoane.
Saptamana trecuta, au mai obtinut cate un punct Laura si Ciprian pentru solutia oferita la cazul simplu. Cazul MD5 nu a fost rezolvat inca, se mai accepta solutii dar la jumatate de punctaj.
Si inca o veste: probabil vom face o pagina pe net unde vom propune aceste probleme impreuna cu solutiile pentru a fi mai usor in anumite aspecte. Si vom fi si primii care au facut asa ceva in Romania, unde exista o cultura pentru matematica…
Bine, dar eu am rulat scriptul ala acu o saptamana si tiam spus ca asa e. A mea solutie nu e optima.
Prima data cand l-am rulat solutia ta era de 10 ori mai rapida. Numai ca gresisem in implementare si nu ma interesa ce se intampla in intervalul de N zile inafara faptului ca primul nu trebuia sa mai intre acolo. O solutie evident falsa. Cand am refacut mi-am dat seama ca nu va merge din cauza ca probabilitatea ca sa se intample ce trebuie este foarte mica. Practic, solutia ta da o rezolvare in O(n^5/3) cel putin pe cand a Iuliei e in O(n^2) si aia riscanta in O(n). Aici se cer formulele din spatele notatiilor cu O. Aveti deja un hint nou..:P
Esti sigur k acel x, nu depinde de N? eu am obtinut urmatoarea dependenta:
n=2; x=7.500
n=3; x=8.667
n=4; x=9.250
n=5; x=9.800
n=6; x=10.167
n=7; x=10.429
n=8; x=10.625
n=9; x=10.778
n=10; x=11.000
n=11; x=11.091
n=12; x=11.250
n=13; x=11.385
n=14; x=11.429
n=15; x=11.533
n=16; x=11.625
n=17; x=11.706
n=18; x=11.778
n=19; x=11.842
n=20; x=11.900
n=21; x=12.000
n=22; x=12.045
n=23; x=12.087
n=24; x=12.167
n=25; x=12.200
n=26; x=12.231
n=27; x=12.296
n=28; x=12.321
n=29; x=12.379
n=30; x=12.433
Intr-adevar, pt n=5, daca schimb 99.99% cu 99.992% obtin x=10.
Am obtinut aceste valori, cu formula urmatoare, pentru probabilitatea sa fi trecut toti n, dupa k zile:
P(n,k)=suma pt i de la 0 la n-1 din:
(-1)^i*C(n,i)*(1-i/n)^k.
Ai o parte din raspuns, mai trebuie doar raspunsul la prima parte. (1/3)