bom, a minha proposta para a função que conta quantos caminhos num tabuleiro m x n tem área a é a recorrência:
f(m, n, a) = f(m - 1, n, a - n) + f(m, n - 1, a) A idéia é a seguinte: qualquer caminho acaba no ponto do canto inferior-esquerdo. Só há duas maneiras de chegar nesse ponto, uma é por cima e a outra é pela direita. Se o caminho vem por cima, então todos os n quadradinhos da última linha são incluídos e o caminho a partir do ponto logo acima é um caminho num tabuleiro m-1 x n cuja área deve ser a - n para que a área total seja a. Se ele vier pela direita então não há nenhum quadradinho da primeira coluna entrando para a contagem da área, logo qualquer caminho desse tipo é na verdade um caminho num tabuleiro m x n-1 de área a. A base da recorrência é bem simples: f(1, k, a) = f(k, 1, a) = { 0 ... se a > k ou a < 0k { 1 ... caso contrário a propósito, coloquei minha solução para o problema 3 da Cone Sul junto com a solução de vários outros problemas em: www.linux.ime.usp.br/~domingos/problemas_resolvidos.pdf [ ]'s ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================