Correct solutions were also received from Laura Taylor, Rich Bernstein, Chris Mossell, Matt Kaiser, Alex Uskov, Sean Koors, Adam Allen, Jon Cone, Mark Chakoian.  Further correct solutions were submitted by Alejandro Vellano, Marko Marevic, Chris Greenslade, Alexei Vorobyov, Fransesc Suñol y Esquiro, Jack Derry, M. Lynch, Jens Voss, Augustin A. Murillo, Bill Soudirette, Lou Cairoli, Nick McGrath, Seymur Cahangirov, Andrew Finkenstadt, Tim Finkenstadt, Philippe Fondanaiche, Michail Chavkin, Burkart Venzke, Nancy Schwarzkopf.

Imagine a worm crawling along such a diagonal.  In going from the bottom left to upper right corner, he/she/it will have to cross each of the vertical and each of the horizontal lines, except the first ones, of course.  It's easy now to deduce the formula given above.

Note that if n and m are not relatively prime then the diagonal line will cross a point of intersection of some vertical and horizontal lines.  This will reduce the problem to a smaller case.  In general, if the greatest common divisor of n and m is d, then the number of squares crossed is m + n -d.

You are visitor number 2349 to this page.