Numesc asa problema de azi pentru ca a pornit de la o discutie privind capacitatile lui MD5 (aveti link pe wikipedia catre el aici). Ne gandim sa aflam daca nu cumva exista puncte fixe in trecerea unui rezultat md5 in alt rezultat md5. (Adica, daca nu cumva exista un sir de biti care va ajunge in acelasi sir dupa ce aplicam md5). Pentru MD5 gasiti scripturi si sursepe net pentru Python, PHP, JavaScript, C si altele.
Problema este insa mai simpla, nu vreau sa va chinuiti cu MD5-ul momentan. Sa consideram un alt alfabet in care toate literele sunt cifrele de la 0 la 9 si orice cuvant este deci format din aceste cifre (un cuvant poate incepe si cu 0!). Facem urmatoarea transformare: pentru fiecare cuvant de n cifre xnx(n-1)….x8×7x6×5x4×3x2×1 obtinem un cuvant de 4 cifre X4X3X2X1 unde Xi este suma modulo 10 a cifrelor xi,x(i+4),…. Daca numarul de cifre este mai mic decat 4 primele cifre in rezultat for fi 0.
Exemple: pentru numarul 1234567890 obtinem numarul 0258; pentru numarul 258 obtinem numarul 0258,…
Se pune intrebarea daca exista cuvinte care transformate astfel ajung in aceleasi cuvinte.
Daca da, se va oferi 1 punct celui care le va gasi pe toate, va demonstra ca sunt singurele cuvinte cu aceasta proprietate, va gasi cele mai mici cuvinte (un cuvant este mai mic decat altul daca numarul reprezentat de el este mai mic decat al celuilalt) si cele mai mari cuvinte de 8 litere care duc in aceste puncte fixe.
Daca nu, se va oferi 1 punct celui care va oferi demonstratia faptului ca nu exista. NU se accepta rezultatele rularii unui script pentru cazul in care nu exista aceste puncte fixe.
Suplimentar, se acorda cate un punct pentru fiecare punct fix descoperit la MD5 sau 2 puncte pentru demonstrarea faptului ca asemenea puncte nu exista (aici e cam greu sa faci un script care sa le testeze pe toate pentru ca ar dura prea mult).
Saptamana trecuta au raspuns corect: Ciprian si Laura (Lieserl) cate 2 puncte si Lothlorien un punct. Cu ocazia asta anunt ca avem un castigator! Clasamentul punctleor la ora actuala este urmatorul (ordinea este intamplatoare in cazul punctajelor egale):
Am luat si am verificat 1234567890. Mi-a dat 0258.
Am zis sa verific in jurul lui :
1234567891=0259
1234567892=0250
1234567893=0251
…………………………
1234567899=0257
Am zis sa il schimb pe x2.
1234567890=0258
1234567880=0248
1234567881=0249
1234567882=0240
1234567870=0238
1234567872=0230
1234567862=0220
1234567852=0210
1234567842=0200
1234567832=0290
1234567822=0280
1234567812=0270
1234567802=0260
1234567890=0258
1234567790=0158
1234567690=0058
1234567590=0958
1234567890=0258
1234566890=9258
1234565890=8258
Dupa observarea asta sunt sigura ca numarul
1234566531 are reprezentarea 9999. Verific. Corect.
Iar reprezentarea lui 1234567642 are ca reprezentare numarul 0000. Verific. Corect.
Toate numerele de la 1234560000 la 1234569999 au ca reprezentare un numar de la 0000 la 9999 fara sa se repete dupa regula urmatoare:
- notam ultimele 4 cifre ale numarului cu x4×3x2×1
y4= x4-7
y3= x3-6
y2= x2-4
y1= x1-2
(daca rezultatul e un numar negativ se va adauga 10)
Din acest fapt ne dam seama ca orice numar de forma abcd provine din cuvantul 1234567xyzt ; (x=a+7 , y=b+6, z=c+4, t=d+2) cat si din numarul abcd. Deci orice numar provine din cel putin doua cuvinte.
Toate indeplinesc propietatea. E evident ca daca toate o indeplinesc sunt si singurele.
O sa studiez si partea cuvintelor de 8 litere si partea suplimentara, dar mai tarziu ca acum am ceva treaba. Revin.
P.S. Nu sunt din Bucuresti si nu am cum sa imi “ridic” premiul. Poate cand o sa ajung la facultate.
Fie punctul fix abcd
Cel mai mic cuvant de 8 litere care duce in abcd este : 0000xyzt (x=a-1, y=b-1, z=c-1, t=d-1)
Cel mai mare cuvant de 8 litere care duce in abcd este :
9999xyzt (x=a+1, y=b+1, z=c+1, t=d+1)
Acum chiar ca revin mai tarziu
.
Stiu ca nu esti din Bucuresti, doar iti citesc blog-ul
. Sigur la facultate (sau la admitere sau poate trec candva pe acolo, poate ma voi intalni cu domnul profesor Sandu inainte de nationala la fizica)
Nush dak inteleg eu bine cerinta ta, dar dak da, inseamna k toate cuvintele din 4 litere sunt pucte fixe, si numai ele.
Dem. Daca numarul de litere este diferit de 4, numarul de litere va fi tot 4, si cuvintele, avand nr. dif de litere, vor fi diferite. daca nr de litere este 4, atunci, conform formulelor tale, X_k=x_k, pt k=1..4 si deci numarul este egal cu transformatul sau. Cum orice numar, se transforma intr-unul de 4 cifre(care este pct fix), cel mai mic nr de 8 cifre este 00000000 ,iar cel mai mare 99999999. Daca cumva te refereai pt un punct fix fixat, a4a3a2a1, atunci cel mai mic numar care se transforma in el este 0000a4a3a2a1, iar cel mai mare este 9999b4b3b2b1, unde bk=(ak+1) modulo 10.
Sper ca am inteles corect cerinta ta. O sa ma gandesc si la MD5.
P.S. I live far away from Bucharest, dar poate ne vedem in Grecia, la concursul de mate(exista sanse maricele ca eu sa fiu in echipa Clujului)
Mey, eu nu sunt nici din Bucuresti si nici in echipa de mate? Ce ma fac? Pot sa vin cu trenu?
Ne vedem si noi candva, Ciprian.
Dadatroll, dupa ce ajungi la 3 puncte poti veni si cu trenul:D