Question

Downtown Mathville is laid out as a 6 x 6 square grid of streets (see diagram below). Your apartment is located at the southwest corner of downtown Mathville (see point H). Your math classroom is located at the northwest corner of downtown Mathville (see point M). You know that it is a 12-block walk to math class and that there is no shorter path. Your curious roommate (we’ll call her Curious Georgia) asks how many different paths (of length 12 blocks – you don’t want to back track or go out of your way) could you take to get from your apartment to the math class. It should also be clear that no shorter path exists. Can you solve Curious Georgia’s math problem?

Answer 1

Answer: 924 paths

Explanation:

Since there is no shorter path, we know that the path must consist of 6 blocks to the north and 6 blocks to the east. Thus, the problem is equivalent to finding the number of ways to arrange 6 N's (for north) and 6 E's (for east) in a sequence such that no two N's are adjacent and no two E's are adjacent.

Let's denote N by 1 and E by 0. Then the problem is equivalent to finding the number of 12-digit binary sequences (i.e., sequences consisting of 0's and 1's) such that there are no consecutive 1's or consecutive 0's.

We can solve this problem using dynamic programming. Let F(n,0) be the number of n-digit binary sequences that end in 0 and have no consecutive 0's, and let F(n,1) be the number of n-digit binary sequences that end in 1 and have no consecutive 1's. Then we have the following recurrence relations:

F(n,0) = F(n-1,0) + F(n-1,1)

F(n,1) = F(n-1,0)

with initial values F(1,0) = 1 and F(1,1) = 1.

Using these recurrence relations, we can compute F(6,0) and F(6,1), and the total number of valid sequences is F(6,0) + F(6,1) = 132. Therefore, there are 132 different paths of length 12 blocks from your apartment to the math class.