No.Body

E foarte simplu, cine stie programare se poate apuca de ceva backtracking, mie imi e prea somn la ora asta ca sa scriu programe :D

Efe

A-ti??? :O

matchless

prima am incercat-o eu pe o foaie si am gasit 128 de cai :))
e greu sa gasesc o logica

catanedelcu

pai impartim problema in doua.
    o
  /  \
o     o
/ \   /  \
o   o     o    etc

numarul total de parcurgeri rezulta din suma coeficientilor din binomul lui newton (a+b)^n.  cu a si b = 1 ...
si vine in mod progresiv
            1                     =1 = 2^0
          1   1                  =2 = 2^1
        1   2   1                .....
      1   3   3   1             .....
    1   4   6   4    1         .....
 n....................       = C(n.0)+C(n,1)+C(n,2)+....C(n,n-1) = 2^(n-1) unde am notat C(n,m)= combinari de n luate cate m

partea a doua...asezam invers chestia asta si avem la fel evident . deci posibilitatile de parcurgere sunt date de suma facuta astfel : pt fiecare nod final din prima inmultim nr. de parcurgeri pana la el cu nr. de parcurgeri de la el pana la capatul celalalt . deci vom vedea repede ca solutia generala este suma patratelor coeficientilor dati de binomul lui newton deci ceva asa:

N = C(n-1,0)^2 + C(n-1,1)^2+C(n-1,2)^2+....+C(n-1,n-1)^2   pt n nivele

in cazul particular din problema , pt 7 vine

1^2+6^2+15^2+20^2+15^2+6^2+1^2 = 924

catanedelcu

asa ca sa dau suma ...prin transformari da  [Suma de C(n,i)^2 ] =  C( (2n), n )   adica pt. n+1 "nivele" avem
(2n)! /( n! * n!)  parcurgeri ... da' tot pe-acolo se-ajunge.