Jumping Fleas
In the plane, the points with integer coordinates are called lattice points . Suppose a flea in the plane jumps from one lattice point to another. Each jump is one unit to the right, one unit to the left, one unit up, or one unit down. If the flea starts at the origin and makes exactly 10 jumps, how many lattice points could possibly be the final landing place of the flea?
Details and assumptions
There is no restriction on which lattice points the flea can land on. As a specific example, the flea is allowed to make 5 jumps to the right, and then 5 jumps to the left to land back at the origin.
The answer is 121.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The flea can end up at most 10 jumps to the right, left, up, or down. We can inductively show that the sum of coefficients of the lattice point that the flea is on has the same parity as the number of jumps that the flea has taken. Hence, the flea cannot end up at a lattice point that is an odd number of jumps away from the origin. The set of possible ending lattice points forms a diamond square shape in the plane with 1 1 ⋅ 1 1 = 1 2 1 lattice points. It is easy to see that each of these lattice points can be reached through exactly 10 jumps. For example, take an even number of jumps to reach the point, the jump up and down till the total number of jumps is 10. So the number of possible ending lattice points is 121.
The picture below suggests a solution when the flea makes exactly 2 jumps instead of 10.