Since the cat’s out of the bag and we’ve had some public discussion of our first Problem of the Week, I thought I’d officially kick things off with a new problem, this time under the ground rules discussed in our last post. This one comes from our regular reader John Smith, who wrote me this problem in email. It comes in two parts; here’s the first:

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.)

A little while later, John wrote me a follow-up question, which will be our part two:

What would be the $n$-dimensional analogue of the previous problem? How would you prove it?

Please submit your solutions through email to topological[dot]musings[At]gmail[dot]com, rendering the stuff in brackets in the obvious way; please do not reply in comments! Solutions should arrive by May 20 (11:59pm UTC time if you want to be exact). We will post one of the correct solutions (or otherwise our own), but all correct solutions will be acknowledged, and successful solvers will have their names entered into our Problem-Solving Hall of Fame. So get your answers in, and happy solving!

[Added May 15: if you just want to solve part one, that’s fine — credit will be awarded for correct solutions. In general for multi-part problems, we ask that you submit all parts you intend to solve in one mailing — thanks.]