Why does GCD solve the grid traversal problem?

[Saitama]

Hello all!

I was trying to solve this problem which is supposed to be easy: Traversing Grid | CodeChef

I couldn't solve it so I looked at some solutions, they seem to be using the concept of GCD. I am unable to understand why this works, please help. Thanks!

 

[Nono713]

I would try and plot all the points near the origin reachable from, say, (3, 5) and see if you can find a pattern. That won't be part of your solution, but it'll help you understand where the GCD comes in.

 

[Saitama]

I would try and plot all the points near the origin reachable from, say, (3, 5) and see if you can find a pattern. That won't be part of your solution, but it'll help you understand where the GCD comes in.

Sorry, but I do not really see it. I found the following points reachable from (3,5) near the origin: (2,3), (1,3), (1,-3), (2,-3), (-1,3), (-2,3), (-2,-3), (-1,-3), (1,2), (1,-2), (0,2), (0,-2)... but no matter, I can never reach the origin. I am still clueless about this, please help!

 

[Nono713]

Sorry, but I do not really see it. I found the following points reachable from (3,5) near the origin: (2,3), (1,3), (1,-3), (2,-3), (-1,3), (-2,3), (-2,-3), (-1,-3), (1,2), (1,-2), (0,2), (0,-2)... but no matter, I can never reach the origin. I am still clueless about this, please help!

Make a grid and draw the points reachable and those not reachable..

 

[Saitama]

Make a grid and draw the points reachable and those not reachable..

I drew a grid for -3<=x<=3 and -5<=y<=5 and couldn't reach the following points: (0,0), (0,3), (0,-3), (3,3), (3,-3), (-3,-3), (-3,3), (0,5) and (0,-5). But I still do not see how this helps. :(

 

[I like Serena]

I drew a grid for -3<=x<=3 and -5<=y<=5 and couldn't reach the following points: (0,0), (0,3), (0,-3), (3,3), (3,-3), (-3,-3), (-3,3), (0,5) and (0,-5). But I still do not see how this helps. :(

What's the $\gcd$ of each of those reachable versus unreachable pairs? (Wondering)

 

[Saitama]

What's the $\gcd$ of each of those reachable versus unreachable pairs? (Wondering)

$\gcd$ of unreachable pairs is $0, 3, 5$ and for the reachable ones, $1, 2$ (as per the above grid). But I am still stumped.

 

[I like Serena]

$\gcd$ of unreachable pairs is $0, 3, 5$ and for the reachable ones, $1, 2$ (as per the above grid). But I am still stumped.

The initial point has $\gcd(3,5)=1$.
What does the $\gcd$ become after each of the operations?

 

[Saitama]

The initial point has $\gcd(3,5)=1$.
What does the $\gcd$ become after each of the operations?

$\gcd$ stays the same i.e 1 after each operation.

 

[I like Serena]

$\gcd$ stays the same i.e 1 after each operation.

Almost.
How did you reach a point with $\gcd=2$ then?

Anyway, do you see that none of the operations can bring you to a point with a $\gcd$ of $3$ or $5$?

Btw, you mentioned that some points had $\gcd=0$.
Can you give an example?
Does it really have a $\gcd$ of $0$?

 

[Saitama]

Almost.

Umm...is my answer incorrect? You asked for the $\gcd$ if I apply each of the operations once to (3,5). So, in one operation, I can reach (8,5), (6,5), (5,3) or (3,-5) and all of them have $\gcd$ as 1.

How did you reach a point with $\gcd=2$ then?

For example, (3,5)->(6,5)->(6,-5)->(1,-5)->(1,5)->(5,1)->(5,-1)->(4,-1)->(1,4)->(2,4).

Anyway, do you see that none of the operations can bring you to a point with a $\gcd$ of $3$ or $5$?

Yes, I do but how does that help?

Btw, you mentioned that some points had $\gcd=0$.
Can you give an example?
Does it really have a $\gcd$ of $0$?

Really sorry about that, when I was calculating the gcds, I accidentally considered (0,0) as a reachable point. (Tmi)

 

[I like Serena]

Umm...is my answer incorrect? You asked for the $\gcd$ if I apply each of the operations once to (3,5). So, in one operation, I can reach (8,5), (6,5), (5,3) or (3,-5) and all of them have $\gcd$ as 1.

For example, (3,5)->(6,5)->(6,-5)->(1,-5)->(1,5)->(5,1)->(5,-1)->(4,-1)->(1,4)->(2,4).

Yes, I do but how does that help?

Ah. I meant repeated application of the operations.
Note that for any $x,y$ we have: $\gcd(x,y)=\gcd(y,x)=\gcd(x,-y)=\gcd(x+y,y)$.
So if we keep repeating any of the first 3 operations, the $\gcd$ will always remain the same.
The odd one out is the 4th operation. The question remains what is can do with the $\gcd$.
A single application to (3,5) won't affect the $\gcd$ yet, but there are ways that it can.

Really sorry about that, when I was calculating the gcds, I accidentally considered (0,0) as a reachable point. (Tmi)

What is $\gcd(0,0)$?
And what is $\gcd(2,0)$?

 

[Saitama]

What is $\gcd(0,0)$?
And what is $\gcd(2,0)$?

$0$ and $2$ respectively but I am still clueless about solving the given problem. :(

 

[I like Serena]

$0$ and $2$ respectively but I am still clueless about solving the given problem. :(

The 4th operation combined with the 1st operation can multiply the $\gcd$ with $2$.
So the $\gcd$ can only be of the form $2^k\cdot \gcd(x_0,y_0)$.
Any point with a $\gcd$ that is not of that form is not reachable.

Btw, $\gcd(0,0)$ is undefined instead of $0$. (Nerd)

 

[Saitama]

The 4th operation combined with the 1st operation can multiply the $\gcd$ with $2$.
So the $\gcd$ can only be of the form $2^k\cdot \gcd(x_0,y_0)$.
Any point with a $\gcd$ that is not of that form is not reachable.

Btw, $\gcd(0,0)$ is undefined instead of $0$. (Nerd)

Thanks for all the help ILS!

But still, how one is supposed to know that the concept of gcd is to be used in this problem? I had no idea until I looked at the solutions.

 

[I like Serena]

Thanks for all the help ILS!

But still, how one is supposed to know that the concept of gcd is to be used in this problem? I had no idea until I looked at the solutions.

We are looking for a property of a pair of numbers that the operations will leave unchanged.
The $\gcd$ is a natural property to consider.Furthermore, the given operations give us a clue, since they match the properties of a $\gcd$.

In particular the operation $(x,y) \mapsto (x+y,y)$ looks like the key concept to evaluate a $\gcd$, which is that adding or subtracting one of the numbers from the other, leaves the $\gcd$ unchanged.
It leads to the algorithm:
\begin{cases}\gcd(x,x) &= x \\
\gcd(x,y) &= \gcd(x - y,y) & \text{if }x > y \\
\gcd(x,y) &= \gcd(x, y-x) & \text{if }y > x \end{cases}