How can we use the concept of GCD to solve this problem?

  • Context: MHB 
  • Thread starter Thread starter Saitama
  • Start date Start date
  • Tags Tags
    Gcd
Click For Summary

Discussion Overview

The discussion revolves around the application of the concept of the greatest common divisor (GCD) in solving a problem related to traversing a grid, specifically from the CodeChef problem "Traversing Grid." Participants explore how GCD relates to the points reachable from a given starting point and the implications for solving the problem.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant expresses confusion about how GCD is applied in the problem and seeks clarification.
  • Another suggests plotting points reachable from a specific coordinate to identify patterns related to GCD.
  • Participants share specific points they found reachable or unreachable from the starting point (3, 5) and discuss their GCD values.
  • There is a discussion about the GCD remaining unchanged after certain operations and how this relates to the problem.
  • Some participants question the existence of points with a GCD of 0 and clarify that GCD(0,0) is undefined.
  • One participant proposes that the GCD can be multiplied by 2 through specific operations, suggesting a form for reachable points based on GCD.
  • Another participant reflects on the challenge of recognizing the relevance of GCD in the problem initially.
  • There is mention of the operations' properties that preserve GCD, which may provide insight into the problem-solving approach.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the application of GCD to the problem, and multiple viewpoints regarding the relevance and implications of GCD remain. There is ongoing confusion and exploration of the concept without a definitive resolution.

Contextual Notes

Some participants express uncertainty about the calculations and the definitions of GCD in specific cases, such as GCD(0,0). The discussion includes various assumptions about the operations and their effects on GCD, which are not fully resolved.

Saitama
Messages
4,244
Reaction score
93
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!
 
Technology news on Phys.org
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.
 
Bacterius said:
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!
 
Pranav said:
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..
 
Bacterius said:
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. :(
 
Pranav said:
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)
 
I like Serena said:
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. :confused:
 
Pranav said:
$\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. :confused:

The initial point has $\gcd(3,5)=1$.
What does the $\gcd$ become after each of the operations?
 
I like Serena said:
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.
 
  • #10
Pranav said:
$\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$?
 
  • #11
I like Serena said:
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? :confused:

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)
 
  • #12
Pranav said:
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? :confused:

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)$?
 
  • #13
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. :(
 
  • #14
Pranav said:
$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)
 
  • #15
I like Serena said:
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.
 
  • #16
Pranav said:
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}
 

Similar threads

MHB Why is Fragmentation Offset Multiple of 8? Understanding IPv4 Fragmentation
  • · Replies 1 ·
Replies
1
Views
4K
How Can We Efficiently Parallelize the N-Queens Problem?
  • · Replies 11 ·
Replies
11
Views
4K
MHB Solve Computing an Average Problem | Help
  • · Replies 2 ·
Replies
2
Views
1K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
MHB Question about problem involving gcd
  • · Replies 2 ·
Replies
2
Views
2K
MHB Does Z[root(-3)] Qualify as a GCD Domain?
  • · Replies 1 ·
Replies
1
Views
2K
Java A question about the Eclipse IDE
  • · Replies 5 ·
Replies
5
Views
3K
Python Question about learning programming
  • · Replies 43 ·
2
Replies
43
Views
7K
C/C++ How can I optimize my C++ code for a sum problem on CodeChef?
  • · Replies 6 ·
Replies
6
Views
3K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K