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?
The answer is not 97 or 455 :) Thank you!
Having an even number of steps actually makes this problem simpler.
The maximum distance traveled by going in any direction is 12. Also note that any pair of coordinates (x, y) in which x + y is odd is not valid because an even number of steps should either cancel out the direction or produce an even sum.
Counting, we see that there are 6(4) + 1 = 25 such points on the x and y axes.
On any line y = n, we should have n + x as an even number so for odd n's we can do ceil(n/2). For quadrant 1 this is:
ceil(11/2) + ceil(9/2) + ceil(7/2) + ceil(5/2) + ceil(3/2) + ceil(1/2) = 5 + 4 + 3 + 2 + 1 = 15.
For even n's, we can just do n/2 which is also, in quadrant 1, equal to 15.
So we should have 4(15+15) + 25 = 145.
Please let me know if I did anything wrong.