OBM-U: 4a Questao!

["Marcio" <mcohen@xxxxxxxxxx>]

    Estou mandando as minhas ideias pra resolver o problema 4 da obm-u.. Eh
um pouco complicada, mas esta certa.. O problema eh que ela eleva um
pouquinho a probabilidade de erro no meio.. :) mas se eu fizesse com mais
calma acho que dava pra nao ter errado a besteira que eu errei na prova..
   O problema (enunciado melhor no site da obm):
A figura abaixo consiste de 9 triangulos equilateros de lado 1. Determine o
numero de percursos que vao do ponto na extrema esquerda para o ponto na
extrema direita passando por cada vertice no maximo uma vez.
     K    I     G    E    C
      .__  .__ .__ . __ .
    /  \   /  \  /  \   /  \  /  \
A/__\ /__\/__\ /__\/__\ B
        J     H    F     D
      Minha ideia foi comecar a contar do final, dando nome aos  vertices
alternadamente em cima e em baixo (ficando com algo do tipo BCDEFGHIJKA) e
dividir em casos mais faceis do tipo:
    Passa por B mas nao passa por C; passa por B e C mas nao por D, passa
por B,C e D mas nao por E, etc.. ateh os caminhos que passam por B,C,...,J
mas nao por K, e por ultimo os que passam por todo mundo.
    Eu fiz isso pq contar o numero de caminhos que passam exatamente uma vez
por cada um dos vertices de uma trelica triangulada horizontal de n vertices
era sempre facil.. Esses numeros sao (F_1,
F_2,...)=(1,1,1,2,3,4,6,9,13,19,28,...) pois em particular satisfazem a
relacao F_n = F_n-1 + F_n-3.
    A partir dai, chamando de B_n a resposta do problema para o caso com n
bases em baixo, e de A_n a resposta de um problema com mesmo enunciado, mas
sem o ultimo triangulo equilatero (i.e, com n-1 bases em baixo e terminando
em cima), da pra montar a seguinte recorrencia (feia e estupida, mas td bem
:)
    B_5 = B_4 + A_4 + B_3 + 2A_3 + 3B_2 + 4A_2 + 6B_1 + 9A_1 + 13 + 28
onde os coeficientes sao dados pela sequencia F_n.
    Por exemplo, o coeficiente de B_2 indica conta os caminhos passando por
C,D,E,F que nao passam por G. Existem B_2 caminhos de A ateh H. Em H, ele eh
obrigado a ir pro F e dai existem F_5 = 3 caminhos ateh o B passando por
todo mundo (pois sao 5 vertices)!
    O meu erro infeliz na prova, que no email ja esta corrigido, foi no
ultimo coeficiente.. O problema eh que esse eh o caso que ele tem que passar
por CDEFGHIJK. Mas como agora nao tem restricao, ele tmb passarah por A, e
portanto existem F_11=28 caminhos desse tipo [na prova, depois de mto tempo
nessa questao, eu contei os vertices (incluindo o B apenas) e coloquei F_10
= 19].
    Depois de entender o processo de montagem dessa recursao, pode-se montar
as recursoes para B_4, A_4, etc, de maneira similar (pq o importante eh
saber os F_n) e iterar ateh obter a resposta do problema B_    5.
Por exemplo,     B_4 = B_3 + A_3 + B_2 + 2A_2 +3B_1 + 4A_1 + 6 + 13
                         A_4 = A_3 + B_2 + A_2 + 2B_1 +3 + 6
    Claro que isso soh funciona porque o numero eh pequeno.. Difilmente eu
conseguiria usar esse argumento e mexer nas recorrencias para generalizar a
resposta. Mas como o problema nao era geral, acho que isso seria
desnecessario (embora mto mais bonito) na prova..
    Bom, continuando desse jeito, obervando que B_1 = 2 e A_1=1, eh rapido
mostrar que B_5 = 274.. Na prova, devido aquele erro que eu mencionei la no
ultimo caso a ser considerado (sempre o ultimo pra estragar :), eu contei um
pouco menos, dando apenas 252 casos..
    Para os que chegaram ateh o final desse email:
    Abracos,
    Marcio :)