Problem:
Let be a positive integer. Denote by the set of points with integer coordinates such that
A path is a sequence of distinct points in such that, for
, the distance between and is 1 (in other words, the points and are neighbors in the lattice of points with integer coordinates).
Prove that the points in cannot be partitioned into fewer than paths (a partition of into paths is a set of nonempty paths such that each point in appears in exactly one of the paths in ).
Solution:
Color the points in as follows (see Figure 1):
- if , color white if is even and black if is odd;
- if , color white if is odd and black if is even.
Figure 1: Coloring of S_
Consider a path in . A pair of successive points and in the path is called a pair of successive black points if both points in the pair are colored black.
Suppose now that the points of are partitioned into paths and the total number of successive pairs of black points in all paths is . By breaking the paths at each pair of successive black points, we obtain paths in each of which the number of black points exceeds the number of white points by at most one. Therefore, the total number of black points in cannot exceed the number of white points by more than . On the other hand, the total number of black points in exceeds the total number of white points by exactly (there is exactly one more black point in each row of ). Therefore,
There are exactly adjacent black points in (call two points in adjacent if their distance is 1 ), namely the pairs
for . Therefore (the number of successive pairs of black points in the paths in the partition of cannot exceed the total number of adjacent pairs of black points in ) and we have , yielding
This problem was suggested by Gabriel Carroll.
The problems on this page are the property of the MAA's American Mathematics Competitions