number of days it takes to visit all the locations in matrix

Question

The seats in a classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right). After every day ,we are allowed to move to a new location (r+1,c+1) if present location is (r,c).We are provided infinite number of day so what is the minimum number of days in which all seats gets visited and why does the greatest common divisor of (n,m) needs to be equal to 1 for this to happen ?

Answer 1

First, we need to be clear that people in the back row one day sit in the front row the next day, and people in the right-most column move to the left-most column.

After that, it's easy to see that number of days to visit every seat is exactly equal to the number of seats, $m\cdot n$, if you are ever going to visit them all. One way to understand this is that if you ever revisit a seat, your future seating is going to be an exact duplicate of the last time you were in that seat. So unless you visit every seat before you return to an already-visited seat, you are not going to get to those other seats.

So what would cause you to miss out seats? If you just focus on the left-most column, you can see that you have moved back $m$ rows - plus some multiple of $n$ forward, if necessary. IF $m$ and $n$ are both multiples of some number $d>1$, then your shift in row number is also some multiple of $d$, and you will never get to visit seats that are other than a multiple of $d$ rows away from your first visit to that column. Again - revisiting any seat means that you will never see any other seats except the ones already visited.