Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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!

share|improve this question
1  
Please don't use all caps - that represents shouting on the internet. –  Zev Chonoles Jan 24 '13 at 21:58

2 Answers 2

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.

share|improve this answer
    
Robert Israel, thanks a lot for your help so far, and your solution makes sense to me, but I'm not allowed to makeany assumptions without providing proof, like the gcd property involving (a+b)/3. Where can I find more about this? –  ANONYMOUS Jan 25 '13 at 16:45
    
So prove it. Hint: if $\gcd(a,b) = c$, we have $a=cx$ and $b=cy$ for some positive integers $x,y$, and $x \ne y$ if $a \ne b$. –  Robert Israel Jan 27 '13 at 5:25
    
Would this be proof enough? Without loss of generality, let a>b. Then gcd(a,b)≤b, and gcd(a,b)≤(a/2). So 2*gcd(a,b)≤a, which implies that 3*gcd(a,b)≤(a+b) And the result follows. –  ANONYMOUS Jan 28 '13 at 21:38
    
Yes, that does it. –  Robert Israel Jan 28 '13 at 22:34
    
Thanks, I now have everything I needed. I understand the question fully now! –  ANONYMOUS Jan 29 '13 at 13:52

Doing what you are trying with three primes gives the sum of vertices $1+a+b+c+ab+ac+bc+abc$ and the sum of edges $3+2(a+b+c)+ab+ac+bc$. Subtracting these would require $2+a+b+c=abc$ and the $abc$ is too big.

I also tried making a mirror image cube with $efg$ dropping to $1$ and multiplying all the vertices. Then each vertex has three factors and each edge has two and the vertices will win again.

Not a proof, either, but it doesn't look good.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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