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.

### Like this:

Like Loading...

*Related*

## Leave a comment

Comments feed for this article