Mock PRMO question

Question

I find a interesting question of my PRMO mock and 2019 AMC 10A

The rectangular floor of a bathroom is covered with square tiles (all of the same size). A spider starts at one corner of the bathroom, and walks to the corner diagonally opposite. For example, the figure below shows a 6 × 8 bathroom, in which the spider touches 12 tiles on its path. (A spider doesn’t touch a tile if it just walks over the grout at the corner of a tile.) For an $m\times n$ bathroom, how many tiles does the spider touch on its walk?

My assumption is that number of tiles bugs walk through is $2* (\text{no. of columns})$ but I am unable to prove it.

Can anyone please help me with solution?

Answer 1

First, we assume $(m,n)=1$.

Let's locate the rectangular on the coordinate system such that the beginning corner is $(0,0)$ and the final corner is $(m,n),$ and each intersection inside the rectangular has integer coordinates. Due to assuming $(m,n)=1$, the spider does not cross any intersection. This fact leads to the conclusion below.

In general, for the $k$th column ($k <m$), the spider touches $[\frac{k(n)}{m}]-[\frac{(k-1)n}{m}]+1$ tiles of the $k$the column.

To prove that, just consider the intersections of pairs of lines $y=\frac{n}{m}x, x=k-1$ and $y=\frac{n}{m}x, x=k.$

However, for the $m$th column, since $\frac{nm}{m}$ is an integer, the spider touches $[\frac{mn}{m}]-[\frac{(m-1)n}{m}]$ tiles. Therefore,

$$[\frac{n}{m}]+1 + ([\frac{2n}{m}]-[\frac{n}{m}]+1) + ([\frac{3n}{m}]-[\frac{2n}{m}]+1) + ... + ([\frac{mn}{m}]-[\frac{(m-1)n}{m}]) \\ =m-1 +n$$

is the total number of tiles that the spider touches.

---

If $(m,n)=d$, then the $\frac{m}{d} \times \frac{n}{d}$ rectangular repeats $d$ times in the main rectangular. For example, in your case where $(6,8)=2$:

---

The answer is $m+n-(m,n)$.

Answer 2

The solution provided by Reza , though correct , is a little advanced , I think. Let me provide a easier version of the solution.

Let us first focus on a smaller floor . Let it be 5 by 3 .

We see it crosses 7 tiles .

We see in the diagram above and see whenever we enter into a new square either right or in the up direction we enter a new tile.

So in the 5 by 3 example we go right 5 times because it is the length and up 3 times .

So we go through 5+3-1=7 tiles. We subtract one because when we reach the corner we are simultaneously going up and right

Now let’s take example of 6 by 4 floor.

Now applying the previous logic here , by the formula we get 6+4-1 =9 tiles , but in actuality 8 tiles are crossed.

This is because we see this time the diagonal simultaneously moves right and up two times , once in the center and once in the corner.

So for the general formula we just have to count how many times a diagonal crosses a corner.

We see this is just the gcd of the dimensions.

So for a m by n floor , no of tiles crossed by diagonal are

m + n - gcd(m,n)

Answer 3

As the line moves from south-west to north-east, each time it crosses either a vertical or horizontal edge (including the left and bottom border lines, but not the right and top), the line enters a new tile. There are exactly $m$ vertical edge crossings and $n$ horizontal edge crossings. This suggests there are $m+n$ tiles touched.

However, there is double-counting whenever the path enters via a corner, since it is crossing both the vertical and horizontal edges. We correct for this double-counting by subtracting the number of tiles entered from a corner. You can confirm the number of corner-entrances is $\gcd(m,n)$. A corner crossing occurs at $(m/d,n/d)$, where $d$ is any common divisor of $m$ and $n$, so the first crossing must occur at the $(m/\gcd(m,n),n/\gcd(m,n))$. Thereafter, the same pattern must repeat, meaning there are exactly $\gcd(m,n)$ corner crossings.

Therefore,

\begin{align} \text{# tiles touched } =\,\,&\text{(# tiles entered from vertical edge)} \\&+\text{(# tiles entered from horizontal edge)} \\&-\text{(# tiles entered from both vertical and horizontal)} \\&\hspace{-.6cm}=m+n-\gcd(m,n) \end{align}