# Mock PRMO 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.

• Each one of your tags is wrong. Feb 8, 2023 at 22:51
• well, a 1 by 3 floor, the spider walks on all three tiles. Meanwhile, you should divide $m,n$ by $\gcd(m,n)$ to get coprime numbers Feb 8, 2023 at 22:55
• If $m=n$, then the spider walks on only $m$ tiles. Feb 8, 2023 at 23:17
• I think it is $m+n - \gcd(m,n)$ Feb 9, 2023 at 0:26
• @youthdoo Are you saying that every contest-math question is also a combinatorics question? Feb 10, 2023 at 11:18

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)

• "We subtract one because when we reach the corner we are simultaneously going up and right". sorry sir but i dont understand this part
– user1147681
Feb 9, 2023 at 8:52
• First of all don't call me sir . In the previous logic when me move up or right , we enter a n ew tile, but when we hit a corner where the diagonal is not in a particular tile , we are adding it 2 times , but actually we are just moving into 1 tile , so we subtract 1. Actually my english is a little weak , so i couldnt express it in pure english . Feb 10, 2023 at 7:38
• in 1st example when we reach 5th cell , we are moving just rightwards but we have also counted for upward that's why are subtracting 1 , is my logic correct. my english is also weak do u know hindi ?
– user1147681
Feb 10, 2023 at 8:13

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

• thanks a lot (:
– user1147681
Feb 12, 2023 at 16:29

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}

• "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" . how did u prove it sir , can u give me hint or prof that total number of corner entrance is equal to gcd.
– user1147681
Feb 10, 2023 at 9:38