The solutions are in! We had a good response to last week’s problem:

  1. Consider a rectangle with sides of integer lengths a and b, subdivided into ab unit squares, and a diagonal line from corner to corner. Show that the number of unit squares that the line crosses is a+b-\gcd(a,b). (Count only those cases where the line crosses the interior of a square.)
  2. What would be the n-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 a = (a_1, ... , a_n) be the vector of box sidelengths, and n(a) the number of boxes crossed by the diagonal going from 0 to a. Then we claim

n(a) = \sum_{S \subseteq [n], S \neq \emptyset } (-1)^{|S| - 1} \gcd(\{a_i\}_{i \in S})

where |S| denotes the cardinality of a set S. [Note that for n=2, this simplifies to n(a) = a_1 + a_2 - \gcd(a_1,a_2), the result of part 1.]

Proof: Parametrize the diagonal by the function f(t) = ta for t \in [0,1], and let f_i(t) denote the i^{th} coordinate of f(t). Defining [n] = \{1,2, \ldots, n\}, we have

n(a) = | \{t \in [0,1) : f_i(t) \in \mathbb{Z} \mbox{ for some } i \in [n]\} |.

[Proof: let T = \{t_0 = 0 < t_1 < …t_n < 1\} be the set on the right-hand side. Each t_i corresponds to an interval (t_i, t_{i+1}) 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 t_i‘s and boxes crossed.]

For i = 1, \ldots, n, let A_i = \{t \in [0,1) : f_i(t) \in \mathbb{Z}\}. Then

n(a) = | T | = | \bigcup_{i \in [n]} A_i | = \sum_{S \subseteq [n]} (-1)^{|S| - 1} | \bigcap_{i \in S} A_i |

by the inclusion-exclusion principle, so we need only verify that | \bigcap_{i \in S} A_i | = \gcd(\{a_i\}_{i \in S}). Indeed, given t, ta_i will be an integer for all i \in S if and only if t  = k/gcd(\{a_i\}_{i \in S}) for k = 0, 1..., \gcd(\{a_i\}_{i \in S})-1, i.e. for \gcd(\{a_i\}_{i \in S}) different values of k. \Box

Remarks: Philipp Lampe notes that the case n = 3 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 n, 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.