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 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 ?
Intr-o alta prolema data 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 a deduce rezolvarea care foloseste 'codul Prufer':http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence ? {*FIXME: reformuleaza intrebarea; nu e clara intentia*}
Adi Carcu imi zicea ca in 99 ca au inceput sa se dea 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 in el. Astfel ei au rezolvat o problema de dificultate medie in cateva minute.
Adi Carcu imi zicea ca in '99 au inceput sa se dea probleme la baraj 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 in el. 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, dar rezultatul e foarte apropiat de n!/e si astfel prin variarea dimensiunii intrarii poti sa rezolvi problema foarte repede.
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. {*FIXME: nu am inteles :)*}
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.
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 pe Google :).
