Avoiding One Street

Difficulty: Hard · Topics: Discrete Mathematics, Combinatorics, Combinations

The figure is made of unit squares.

graph "x":[-0.7,4.7],"y":[-0.6,4.6],"axes":false,"ink":true,"label":"A 4 by 4 grid of unit squares from A (bottom left) to D (top right); the unit segment BC in the middle is highlighted","items":["type":"line","from":[0,0],"to":[4,0],"ink":true,"width":1.2,"type":"line","from":[0,0],"to":[0,4],"ink":true,"width":1.2,"type":"line","from":[0,1],"to":[4,1],"ink":true,"width":1.2,"type":"line","from":[1,0],"to":[1,4],"ink":true,"width":1.2,"type":"line","from":[0,2],"to":[4,2],"ink":true,"width":1.2,"type":"line","from":[2,0],"to":[2,4],"ink":true,"width":1.2,"type":"line","from":[0,3],"to":[4,3],"ink":true,"width":1.2,"type":"line","from":[3,0],"to":[3,4],"ink":true,"width":1.2,"type":"line","from":[0,4],"to":[4,4],"ink":true,"width":1.2,"type":"line","from":[4,0],"to":[4,4],"ink":true,"width":1.2,"type":"line","from":[2,1],"to":[2,2],"ink":false,"width":4,"type":"point","at":[0,0],"label":"A","anchor":"sw","type":"point","at":[4,4],"label":"D","anchor":"ne","type":"point","at":[2,2],"label":"B","anchor":"ne","type":"point","at":[2,1],"label":"C","anchor":"se"]

Moving along the grid lines, how many shortest paths go from A to D without using the segment BC?