In 2006 s-a dat la lot determinarea numarului de acoperiri cu dominouri a unui diamant aztec (http://mathworld.wolfram.com/AztecDiamond.html). Formula e foarte simpla $2^n(n+1)/2^$ insa demonstratia solutiei e foarte complicata - implica folosirea de permanenti apoi transformarea lor in determinanti folosind numere complexe. Probabil nici baietii din lotul national de matematica nu s-ar descurca cu o problema de genul asta. Surprinzator, mare parte din concurentii de la concursul respectiv au rezolvat-o perfect. Unul dintre cei care nu a rezolvat-o, a fost Adrian Vladu, care, in loc sa incerce sa ghiceasca formula, a incercat sa gaseasca rezolvarea matematica. {*FIXME: reformuleaza fraza urmatoare. E un fel de gand personal amestecat cu o informatie*} Inca imi pare rau ca am fost in comisie si nu m-am uitat mai atent pe problema respectiva pentru ca o vazusem inainte in faza de documentare pentru articolele mele cu 'probleme de acoperire':implica-te/scrie-articole si stiam ca nu poate fi rezolvata decat prin ghicirea rezultatului.
Cand participi la un concurs online te poti uita pe 'Online encyclopedia of integer sequences':http://www.research.att.com/~njas/sequences/. Am folosit siteul asta pentru cateva probleme de la concursurile topcoder, si pentru o problema la Oni by Net; Sau poti sa cauti rezultatele direct pe Google :)
Cand participi la un concurs online te poti uita pe 'Online encyclopedia of integer sequences':http://www.research.att.com/~njas/sequences/ Am folosit siteul asta pentru cateva probleme de la concursurile topcoder, si pentru o problema la Oni by Net. Sau poti sa cauti rezultatele pe Google :).
Radu Stefan a folosit o metoda destul de misto pentru a rezolva urmatoarea problema:
_Se cere sa se numere in cate moduri se pot aseza k regi pe tabla de sah de n x n astfel incat regii sa nu se atace._
Radu s-a gandit ca solutia va fi un polinom in doua variabile P(n, k), iar gradul polinomului nu va fi prea mare (parca el a presupus ca limita e 6). Astfel a generat folosind metoda backtracking solutiile pentru n <= 6 si k <= 6. A considerat coeficientii polinomului ca necunoscute si a rezolvat sistemul de ecuatii liniare date P(n, k) si valorile obtinute prin algoritmul backtracking. A luat punctaj maxim pe problema respectiva.
Radu s-a gandit ca solutia va fi un polinom in doua variabile P(n, k), iar gradul polinomului nu va fi prea mare (parca el a presupus ca limita e 6). Astfel a generat folosind metoda backtracking solutiile pentru n <= 6 si k <= 6. A considerat coeficientii polinomului ca necunoscute si a rezolvat sistemul de ecuatii liniare date P(n, k) si valorile obtinute prin algoritmul backtracking. Astfel luat punctaj maxim pe problema respectiva.
Trucul asta se aplica usor pe alte probleme, trebuie doar sa stiti sa folositi metoda de rezolvare a sistemelor liniare.
Problema patrat s-a dat la selectia lotului in 2005. Ea cerea +determinarea numarului de patrate magice de dimensiune 3x3 unde suma elementelor de pe linii, coloane si diagonale este N_. Solutia este un polinomul de gradul 4. Fie el P(X) = aX^4^ + bX^3^ + cX^2^ + dX + e. Numim V_1, V_2, V_3, V_4 si V_5 numarul de solutii pentru N = 1, ... 6. Acum sistemul de care vorbeam mai sus va arata asa:
Pentru polinoame intr-o singura variabila puteti sa folositi metoda 'diferentelor divizate':http://en.wikipedia.org/wiki/Divided_differences#Forward_differences care e foarte simpla de implementat.
a + b + c + d + e = V_1
16a + 8b + 4c + 2d + e = V_2
81a + 27b + 9c + 3d + e = V_3
256a + 64b + 16c + 4d + e = V_4
625a + 125b + 25c + 5d + e = V_5
Pentru polinoame intr-o singura variabila mai puteti folosi metoda 'diferentelor divizate':http://en.wikipedia.org/wiki/Divided_differences#Forward_differences care are o implementare foarte simpla.
Daca formula e ceva mai complicata decat un polinom, putem sa speram ca sirul solutiilor e caracterizat de o recurenta liniara, si astfel putem folosi din nou rezolvarea de sisteme de ecuatii lineare pentru a afla coeficientii recurentei.
Sper ca am aratat ca propunerea unei probleme de formula este o idee proasta! Si chiar daca va confruntati cu una veti putea sa o rezolvati rapid folosind micile trucuri expuse mai sus.
Sper ca am aratat ca propunerea unei probleme de formula este o idee foarte proasta! Si chiar daca va confruntati cu una veti putea sa o rezolvati rapid folosind micile trucuri expuse mai sus.
In rest Paste Fericit si Bafta la ONI!
