A rectangular 12 cm by 20 cm waffle is divided into 1 by 1 cm squares. An ant crawls along a straight path from one corner to the opposite corner. How many squares of the waffle does the ant cross through?
I tried to to use Pythagorean theorem but I don't think that would work. I think you could use PIE (Principle of Inclusion Exclusion) to solve this problem.
On
My first idea was that whenever the ant crosses a line, it will cross another square. So the ant should cross $1 + 11 + 19$ squares (one where it starts and one more for any line it crosses). But this is not true of course. We have to take into account the possibility that the ant crosses 2 lines at once (namely when it hits a point of the grid). In this case it would only cross one more square while passing 2 lines. So I came to the conclusion that the answer must be $1 + 11 + 19 - p$ where $p$ is the number of integer points that the ant crosses excluding the point $(0, 0)$ and $(12, 20)$. One can easily count $p$ now and calculate the result. In the general case one could use that $p = gcd(12, 20) - 1$. This formula is from a related question: How many number of integer coordinates exists between a line segment, including the end points?
You can divide it into $\gcd (12,20)=4$ pieces. It crosses a $3 \times 5$ rectangle and arrives at the opposite corner. Draw it and count. You should be able to generalize to an $m \times n$ rectangle when $m$ and $n$ are coprime because it will not go through any interior lattice points.