At the vertices of a cube are written 8 different natural numbers, and on each of its edges is written the greatest common divisor of the numbers at the endpoints of the edge.
Can the sum of the numbers written at the vertices be the same as the sum of the numbers written at the edges?
I have no idea where to go with this question. Here are some ideas:
There is a mistake in the above picture.
I missed out two edges, b and c.
The vertices can be arranged in this manner, where no letter past a is equal to one.
All of the terms cancel out except for abc+ some vertex V for the sum of the vertices, and a+b+c+unknown edges x+y+z which all depend on what value to give V. I cannot decide this at all.
Other ideas presented to me, as well was what I believe, is that this just is not possible. However, I have no way of proving that.
Here are some ideas from another who tried this with me:
Clearly, if there were only as many edges as vertices it would never work, as the value of a connecting edge must be smaller than at least one of its vertex values. In the best case scenario one vertex is a and the other ab, then you get an edge value of a, but the vertex ab is necessarily bigger.
However, there are more edges than vertices, so one might hope to get some clever settings which work out.
Here some ideas against that hope:
You can't have just the majority of vertices being primes, because then two connected primes only give you a 1 on the edge and so to beat all the vertex primes, you'd need a couple of very bid edges. To get big edges you need at least one big vertex which isn't prime, so we conclude that there must be some bigger vertex somewhere.
But, say one big vertex is ab with b>a with a=>2.There are only three outgoing edges, so to not lose, you want all of them carry the b. But then the other side of these edges must be bc with c>2. Hence all the vertices together are somethink like (a+c+d+e)*d and the edges are only 3b.
This is no proof, but an argument against a vertex with only two prime factors.
But then I played around and and saw that vertices the number 2*3*5 is really the only one that wins over it's edges
Please help!
Best Answer
No, it's not possible. Note that if you didn't have the constraint of all vertex numbers being distinct, you could do it, e.g. with the "odd" vertices being $1$ and the "even" vertices $2$.
Note that for $a \ne b$, $\gcd(a,b) \le (a+b)/3$, with equality iff $a=2b$ or $b=2a$. Add this inequality over all the edges: each vertex is incident on $3$ edges, so we get $\sum(\text{edges}) \le \sum (\text{vertices})$, with equality if and only if in each pair of neighbouring vertices, one is twice the other. But that can't happen if all numbers are distinct, because the graph has cycles.
The proof generalizes, of course, to any $3$-regular finite graph.