The solutions are in! We had a good response to last week’s problem:
- Consider a rectangle with sides of integer lengths and , subdivided into unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is . (Count only those cases where the line crosses the interior of a square.)
- What would be the -dimensional analogue of the previous problem? How would you prove it?
The solution below is due to Paul Shearer (University of Michigan):
Solution to POW-2: We’ll solve part 2, which subsumes part 1.
Let be the vector of box sidelengths, and the number of boxes crossed by the diagonal going from 0 to a. Then we claim
where denotes the cardinality of a set . [Note that for , this simplifies to , the result of part 1.]
Proof: Parametrize the diagonal by the function for , and let denote the coordinate of . Defining  , we have
[Proof: let < < … < be the set on the right-hand side. Each corresponds to an interval where the line is in the interior of exactly one box, since a point in a box is interior if none of its coordinates is an integer. Hence there is a bijection between ‘s and boxes crossed.]
For , let . Then
by the inclusion-exclusion principle, so we need only verify that . Indeed, given , will be an integer for all if and only if for , i.e. for different values of .
Remarks: Philipp Lampe notes that the case is given by Andreescu and Feng, A Path to Combinatorics for Undergraduates: Counting Strategies (Birkhäuser, 2004). He also gave a solution from which a proof of the inclusion-exclusion principle (which involves binomial coefficients) can be extracted. A number of people gave the correct formula for general , but full credit was given only for complete proofs.
Also solved by Sune Jakobsen, Philipp Lampe. Solutions to part 1. were given by Jimbo Doe, Jason Dyer, and Marni Sheppeard.