2
$\begingroup$

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?

enter image description here

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?

$\endgroup$
5
  • 3
    $\begingroup$ Each one of your tags is wrong. $\endgroup$ Feb 8, 2023 at 22:51
  • 2
    $\begingroup$ 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 $\endgroup$
    – Will Jagy
    Feb 8, 2023 at 22:55
  • 2
    $\begingroup$ If $m=n$, then the spider walks on only $m$ tiles. $\endgroup$ Feb 8, 2023 at 23:17
  • 1
    $\begingroup$ I think it is $m+n - \gcd(m,n) $ $\endgroup$
    – Will Jagy
    Feb 9, 2023 at 0:26
  • $\begingroup$ @youthdoo Are you saying that every contest-math question is also a combinatorics question? $\endgroup$ Feb 10, 2023 at 11:18

3 Answers 3

2
$\begingroup$

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 .

enter image description here

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.

enter image description here

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)

$\endgroup$
3
  • $\begingroup$ "We subtract one because when we reach the corner we are simultaneously going up and right". sorry sir but i dont understand this part $\endgroup$
    – user1147681
    Feb 9, 2023 at 8:52
  • $\begingroup$ 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 . $\endgroup$ Feb 10, 2023 at 7:38
  • $\begingroup$ 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 ? $\endgroup$
    – user1147681
    Feb 10, 2023 at 8:13
1
$\begingroup$

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$:

enter image description here


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

$\endgroup$
1
  • $\begingroup$ thanks a lot (: $\endgroup$
    – user1147681
    Feb 12, 2023 at 16:29
0
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ "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. $\endgroup$
    – user1147681
    Feb 10, 2023 at 9:38

You must log in to answer this question.