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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/52108/755, math.stackexchange.com/q/1619367/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. P.S. What's the context where you encountered this? Is this a programming contest question? $\endgroup$– D.W. ♦Oct 11, 2016 at 14:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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