Is it possible to arrange natural numbers 1 to 8 on vertices of a cube such that each number divides sum of the three numbers sharing an edge with it?
Problem
Source: Iran MO Third Round 2021 F1
Tags: geometry, 3D geometry
26.09.2021 06:55
Solved with kvedula2004 and islander7. The answer is no. We can notice that either the numbers around 8 sum to 8 or 16, so we'll take 2 cases. Case 1. The sum of the numbers is 8. In this case, we know that the numbers around 8 are 1, 2, and 5 or 1, 3, and 4. Either way, if the number diametrically opposite 8 is $n$, then $n\mid 36-16=20$. In the first case, we get $n=4$, so thus we get the following diagram: [asy][asy] import three; unitsize(1cm); size(200); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); label("8", (0,0,0),(-1,-1,-1)); label("5", (1,0,0),(1,-1,-1)); label("2", (0,1,0),(-1,1,-1)); label("1", (0,0,1),(-1,-1,1)); label("4", (1,1,1),(1,1,1)); [/asy][/asy] However, the remaining numbers are $3,6,$ and $7$, no two of which, when combined with $8$, sum to a multiple of $5$. Thus, the other case must happen, and opposite to $8$ we have either $2$ or $5$; if it's $5$, we get [asy][asy] import three; unitsize(1cm); size(200); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); label("8", (0,0,0),(-1,-1,-1)); label("4", (1,0,0),(1,-1,-1)); label("3", (0,1,0),(-1,1,-1)); label("1", (0,0,1),(-1,-1,1)); label("5", (1,1,1),(1,1,1)); [/asy][/asy] However, $7$ must be surrounded by one of $5+4+3,5+4+1,$ or $5+3+1$, none of which is a multiple of 7. Thus, we have a $2$ opposite to the $8$ [asy][asy] import three; unitsize(1cm); size(200); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); label("8", (0,0,0),(-1,-1,-1)); label("4", (1,0,0),(1,-1,-1)); label("3", (0,1,0),(-1,1,-1)); label("1", (0,0,1),(-1,-1,1)); label("2", (1,1,1),(1,1,1)); [/asy][/asy] $7$ must be placed in the top left corner, but then we see that $3$ is surrounded by a sum of $8+5+6$, which is horrible. This case fails. Case 2. The sum of the numbers is 16. Then, 7 must be next to 8, and the sum of the numbers adjacent to 7 is 14. In addition, the sum of the two numbers next to neither 8 nor 7 is 6, which is the sum of the numbers next to 7 (not 8). Opposite to 7 must be a number dividing 15, which means it's a 1 or 5. Thus, we get two possible diagrams: [asy][asy] import three; unitsize(1cm); size(200); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); label("8", (0,0,0),(-1,-1,-1)); label("7", (1,0,0),(1,-1,-1)); label("1", (0,1,1),(-1,1,1)); label("5", (1,1,1),(1,1,1)); [/asy][/asy] In this case, the other numbers around 7 are 2 and 4, which fails. The other case is [asy][asy] import three; unitsize(1cm); size(200); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); label("8", (0,0,0),(-1,-1,-1)); label("7", (1,0,0),(1,-1,-1)); label("5", (0,1,1),(-1,1,1)); label("1", (1,1,1),(1,1,1)); label("2", (1,1,0),(1,1,-1)); label("4", (1,0,1),(1,-1,1)); [/asy][/asy] This means the bottom right corner is 6, which means the top back corner is 4, a contradiction. This means nothing works.
20.06.2022 15:40
The answer is NO. Assume contrary that such an arrangement exists. Color the vertices with an even number red and with odd number blue. Observe, There are four red and four blue vertices. For each red vertex, it has an even number of blue neighbours, and consequently odd number of red neighbours (as total neighbours is three). Claim: Each blue vertex has an odd number of blue neighbours. Proof: Note there are essentially two possible configurations to place the red vertices, so that the above conditions are true (like consider two cases on whether some red vertex has all three neighbours red or each red vertex has precisely one red neighbour). In both configurations, our Claim can be easily verified. $\square$ Now for each $x \in \{1,2,\ldots,8\}$, denote by $S(x)$ the sum of neighbours of $x$. We are given $$ x \mid S(x) $$By our Claim, note that $$ S(x) \text{ is odd } ~~ \forall ~ \text{odd } x $$Now $S(7)$ is odd and $$ S(7) \le 8+6+5 = 19 < 21 $$Hence we conclude $$ S(7) = 7 $$It directly follows that $1,2,4$ are neighbours of $7$. We obtain the configuration like below. [asy][asy] import three; unitsize(1cm); size(200); dot("$7$",(0,0,0),dir(-90),blue); dot("$1$",(1,0,0),dir(180),blue); dot("$2$",(0,1,0),dir(0),red); dot("$4$",(0,0,1),dir(90),red); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); [/asy][/asy] Next we look at $S(5)$ (which is odd). Clearly, $$ S(5) \ge 1+2+3 = 6 > 5 \qquad , \qquad S(5) \le 8+7+6 = 21 < 25 $$It follows that $$ S(5) = 15 $$Then sum of any two neighbours of $5$ is at least $$ 15 - 8 = 7 $$We look where is $5$ in the cube. Note $5$ cannot have two neighbours among $1,2,4$ since otherwise sum of two neighbours of $5$ would be $$ \le 2+4 = 6 < 7 $$It follows that $5$ is diametrically opposite to $7$ in the cube, as below: [asy][asy] import three; unitsize(1cm); size(200); dot("$7$",(0,0,0),dir(-90),blue); dot("$1$",(1,0,0),dir(180),blue); dot("$2$",(0,1,0),dir(0),red); dot("$4$",(0,0,1),dir(90),red); dot("$5$",(1,1,1),dir(-45),blue); draw((0,0,0)--(1,0,0)--(1,1,0)--(0,1,0)--cycle); draw((0,1,0)--(0,1,1)); draw((0,0,0)--(0,0,1)); draw((1,1,0)--(1,1,1)); draw((1,0,0)--(1,0,1)); draw((0,0,1)--(1,0,1)--(1,1,1)--(0,1,1)--cycle); [/asy][/asy] But then we have, \begin{align*} 1+2+\cdots + 8 &= \text{sum of all numbers in the cube} \\ &= (S(7) + 7) + (S(5) + 5) \\ &= 14 + 20 \\ &= 34 \end{align*}which is absurd. So we obtain our desired contradiction. $\blacksquare$