Probleme "de formula"

Probleme de formula

Nu imi plac problemele "de formula"! Acestea sunt problemele de natura matematica din concursurile de programare, care ,de obicei, cer numararea unor configuratii si au ca raspuns o formula. Un motiv este lipsa de originalitate; e foarte probabil ca problema sa fi fost luata dintr-o carte de matematica. Alt motiv este ca nu testeaza partea de programare; de obicei programele ce rezolva astfel de probleme sunt usor de implementat (cateodata mai ai nevoie de numere mari...). Al treilea motiv e ca nu departajeaza elevii dupa valoarea sau ideile lor, ci mai mult "randomizeaza" rezultatele; unele formule sunt foarte greu de gasit pe cale matematica, dar sunt mai usor de ghicit.

Nu imi plac acest tip de probleme! Un motiv ar fi lipsa lor de originalitate, e foarte probabil ca problema a fost luata din o carte de matematica. Alt motiv ar fi ca nu testeaza partea de programare, de obicei programele ce rezolva problemele astea sunt foarte simple implicand doar o instructiune de scriere si una de citire (cateodata mai ai nevoie sa si implementezi numere mari dar cam atat). Al treilea motiv e ca  nu departajeaza elevii intre ei dupa valoarea sau ideile lor, ci mai mult randomizeaza rezultatele, pentru ca unele formule sunt foarte greu de gasit pe cale matematica, dar sunt mai usor de ghicit.

Pentru a gasi formula de rezolvare, putem sa ne uitam la cateva rezultate mici si sa incercam sa ghicim cum arata formula ce le genereaza. O metoda banala ar fi sa variem fiecare parametru de intrare si sa vedem cum se modifica numarul cautat.

Pentru a gasi formula ce ne rezolva problema, ne uitam la cateva rezultate mici si sa incercam sa ghicim cum arata formula ce le genereaza. O metoda banala ar fi sa variem fiecare parametru de intrare si sa vedem cum se modifica numarul cautat.

In problema mea 'aladdin2':problema/aladdin2, se cere _numarul de colorari al celulelor unei table n X m cu alb sau negru astfel ca orice patrat de dimensiune 2x2 sa aiba exact doua patrate colorate alb si doua colorate negru_. Formula e banala $2^n^ + 2^m^ - 2$ si se observa imediat cu variarea dimensiunilor.

In problema mea 'aladdin2':problema/aladdin2 , se cere _numarul de colorari ale celulelor unei table nxm cu alb sau negru, astfel ca orice patrat de 2x2 sa aiba exact doua patrate colorate alb si doua colorate negru_. Formula e banala 2^n^ + 2^m^ - 2 si se observa imediat cu variarea dimensiunilor.

Intr-o alta prolema data la un baraj se cerea _afisarea numarului de arbori partiali ai unui graf bipartit complet cu n noduri de o parte si m noduri de cealalta_. E mult mai simplu sa ghiciti de formula $n^n-1^ * m^m-1^$ decat sa mergeti pe calea rezolvarii oficiale care deduce formula prin folosirea 'codului Prufer':http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence

In alta problema la un baraj se cerea determinarea _numarului de arbori partiali ai unui graf bipartit complet cu n noduri in o partitie si m noduri in cealalta partitie_. Credeti ca era greu sa va prindeti de formula n^n-1^ * m^m-1^ , fara decuce rezolvarea care foloseste 'codul prufer':http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence ?

Adi Carcu imi zicea ca in '99 au inceput sa se dea probleme la baraj pentru care rezultatul era o combinare. La a doua problema de genul asta, multi dintre concurenti au generat triunghiul lui Pascal si au cautat rezultatele din exemplu in el. Astfel ei au rezolvat o problema de dificultate medie in cateva minute.

Adi Carcu imi zicea prin 99 ca au inceput sa se dea cateva probleme la barajele de anul respectiv pentru care rezultatul era o combinare. La a doua astfel de problema, multi dintre concurenti au generat triunghiul lui pascal si au cautat rezultatele din exemplu acolo. Astfel ei au rezolvat o problema de dificultate medie in cateva minute.

Alta problema interesanta e determinarea _numarului de permutari fara puncte fixe_. Problema are o solutie draguta folosind programare dinamica. Totusi poate fi rezolvata altfel urmand schimbarea rezultatului o data cu variarea lui $n$, si se observa destul de usor ca poate fi folosita formula $[n!/e + 1]$.

Alta problema interesanta e determinarea numarului de permutari fara puncte fixe. Problema are o solutie draguta folosind programare dinamica, dar rezultatul e foarte apropiat de n!/e si astfel prin variarea dimensiunii intrarii poti sa rezolvi problema foarte repede.

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. Eu vazusem problema in faza de documentare pentru articolele mele cu 'probleme de acoperire':implica-te/scrie-articole. Stiam ca nu poate fi rezolvata decat prin ghicirea rezultatului. De aceea inca imi pare rau ca am fost in comisie si  problema a fost folosita in concurs.

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^. Dar demonstratia solutiei e foarte complicata, ea 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. 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 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 cauta 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. Astfel 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.

Problema patrat(lot 2005), 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, ..., 5$. Acum sistemul de care vorbeam mai sus va arata asa:

Trucul asta se aplica usor pe alte probleme, trebuie doar sa stiti sa folositi metoda de rezolvare a sistemelor liniare.

$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.

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.

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 *foarte proasta*! Si chiar daca va confruntati cu una veti putea sa o rezolvati rapid folosind micile trucuri expuse mai sus. Chiar daca si eu am propus o problema de formula, sper ca ele vor disparea din concursurile importante gen ONI, baraje si LOT.

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!

protected

private

3029