Franklin the fly starts at the point (0,0) in the coordinate plane. At each point, Franklin takes a step to the right, left, up, or down. After 12 steps, how many different points could Franklin end up at?
To find how many different points Franklin could end up at,
that is, a maximum, we have to prohibit his going to any
step where he landed, or could have landed, before.
Step Choices Total
1 4 4 Franklin could go in any of the four directions.
2 3 4 • 3 = 12 Only three choices because Franklin could go in any of the four
directions except back to the place he was in the previous step.
3 3 4 • 3 • 3 = 36
4 3 4 • 3 • 3 • 3 = 108
5 3 4 • 3 • 3 • 3 • 3 = 324 See a pattern emerging. Let's write this as a generality.
n 3 4 • 3(n – 1)
So, at step 12, Franklin could have ended up at 4 • 311 = 708,588 points
.