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.