1
$\begingroup$

There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. Given two vertices u and v, I want to find the length of the shortest path between them. I think that the shortest path should pass through gcd(u, v) or lcm(u, v) (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct? If it is not correct, then how to solve this? It is not my homework.

$\endgroup$
1
$\begingroup$

Given two vertices $u$ and $v$, I want to find the length of the shortest path between them. I think that the shortest path should pass through $\gcd(u, v)$ or $lcm(u, v)$ (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct?

I think the claim is not strictly true as written, and I will provide a counter-example.


First a claim: For any two vertices in this graph, there is a shortest path between them which uses only edges whose weight is a prime.

Pf: If the weight is not a prime, it can be factored, and this yields a different path between the same two vertices. The sum of any sequence of positive numbers all at least 2 is less than or equal to their product (trivial, by induction), so that is a shorter path, which can be substituted into the original in place of the non-prime edge.

(Note that a slightly stronger thing we could say is "shortest paths can only contain edges whose weight is a prime or is 4", proof left to reader.)


Now take two arbitrary non-prime coprime numbers, say, 6 = 2 * 3, and 35 = 5 * 7.

Clearly, a shortest path using only prime edges has at least 4 steps.

Also, we can ignore the possibility of a shortest path using edges corresponding to primes which are not {2, 3, 5, 7} -- by commutativity of multiplication, any such edges can be reordered until the end, without changing the weights of any of the edges, and the total effect of any such edges for primes which were not originally involved must be a loop, so in fact they could be skipped.

It follows (from this argument) that the shortest paths from 6 to 35 are in bijection with orderings of {2, 3, 5, 7}. They all have the same cost, which is 2 + 3 + 5 + 7.

Some of them pass through the lcm or gcd, but some do not. For instance, 6 -> 2 -> 10 -> 70 -> 35.


I think you can prove that there is a shortest path passing through the gcd? And there is a shortest path passing through the lcm?


I think the idea to prove that would be, look at the edges in the path, and look at which ones make the number larger, and which ones make the number smaller. Then rearrange the edges using commutativity of multiplication as before. If you sort it so that those that make the number larger come first, and then are followed by those that make the number smaller, then in the middle I think you pass through the lcm. If you sort it so that those that make the number smaller come first, then I think you pass through the gcd.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let's assume u<=v (otherwise interchange u and v).
1. u|v trivial u=gcd(u,v), v=lcm(u,v) (special case u=v)
2. gcd(u,v)=1 => path must go either via 1 or via u*v=lcm(u,v)
3. gcd(u,v)=x => path analog to path from u/x to v/x (which is solved by 2.)

There always exists at least one shortest path going through gcd(u,v).
There exists at least one shortest path going through lcm(u,v) if lcm(u,v)<=N.
There can exist shortest paths passing neither gcd nor lcm, e.g. u=2*3,v=5*7:

2*3->2->2*5->5->5*7
2*3->2->2*7->7->5*7
2*3->3->3*5->5->5*7
2*3->3->3*7->7->5*7

or u=4,v=9: 4->2->6->3->9

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.