Franklin the fly starts at the point (0,0) in the coordinate plane. At each step, Franklin takes a step to the right, left, up, or down. After 10 steps, how many different points could Franklin end up at?
The ending point of the path Franklin made depends on all the moves Franklin made, not the order. Consider a random 10-step path Franklin could take. NESWNNESEW (N for North, S for south, W for west, E for East. Reduce our path by cancelling each E-W and each N-S pair, which will not change our endpoint. So our example reduces to NE. Notice that our reduced path must have an even number of moves, and it is thus possible to end at any point (x,y) where x+y is even and |x| + |y| is no greater than 10.'
If |x| + |y| = 0, there is one possibility for (x,y).
If |x| + |y| <= (less than equal to) 2, there are 9 possible paths ((0,0) (-+1,-+1) (0, +-2) (+-2,0)); these solutions will form a 3x3 diagonal grid
The solutions with |x| + |y| <= 10 will form an 11x11 grid, so there are 11^2= 121 ways