Find the number of paths from $A$ to $I,$ if each step must be in a right-ward direction. (For example, one possible path is $A \to B \to C \to E \to F \to H \to I.$)

Answer 1

From the diagram, $A$ can be connected with $I$ by connecting $A$ with the upper vertex of isosceles right triangle $AIH$ such that the new path is only right-directed. This uses up a step to go from $A$ to triangle $AIH$. Removing triangle $AIH$ reveals a diagram in problem 18b, where $AH$ and lengths of other triangles were added. There are $\boxed{13}$ paths as above. [asy]
pair A, B, C, D, EE, F, G, H, I;

A = (0,0);
B = A + (1,0);
C = B + (4,0);
D = C + (7,0);
EE= D + (1,1);
F = EE + (3,0);
G = F + (1,1);
H = G + (4,2);
I = H + (3,3);

draw(A--B);
draw(B--C);
draw(C--D);
draw(D--EE);
draw(EE--F);
draw(F--G,dashed);
draw(G--H,dashed);
draw(H--I,dashed);

label("$A$",A,W);
label("$B$",B,SE);
label("$C$",C,SE);
label("$D$",D,W);
label("$E$",EE,NE);
label("$F$",F,SW);
label("$G$",G,S);
label("$H$",H,N);
label("$I$",I,NE);

label("3",D/2,S);
label("5",D + (2,0),S);
label("3",EE + (1.5,0),N);
[/asy]