Maths Olympiad Prep

Library / /40 of 92

Combinatorics Difficulty 6.3 National olympiad Prove it Iran

Is it possible to assign numbers 1,2,,81, 2, \ldots, 8 to the vertices of a cube in a way that the assigned number of each vertex divides the sum of numbers assigned to its neighbours? (Note that every number should be used once).

Solution

The answer is no. First, for every 1i81 \leq i \leq 8 we define NiN_i to be the set of numbers assigned to the vertices adjacent to the vertex with number ii. By the problem's assumption, the sum of elements of NiN_i is divisible by ii. Since the sum of every three numbers less than 88 is at most 7+6+5=187+6+5=18, the sum of elements of N8N_8 is either 88 or 1616. By checking different cases, it is easy to see N8N_8 equals to either {3,6,7}\{3, 6, 7\}, {4,5,7}\{4, 5, 7\}, {5,2,1}\{5, 2, 1\}, or {4,3,1}\{4, 3, 1\}. We will check these different cases.

* If N8={3,6,7}N_8 = \{3, 6, 7\}, let N6={x,y,8}N_6 = \{x, y, 8\}. Evidently N8N6=N_8 \cap N_6 = \emptyset. Now, by assumption, 6x+y+86 \mid x+y+8, and 11=1+2+8x+y+817=4+5+811 = 1+2+8 \leq x+y+8 \leq 17 = 4+5+8. These imply x+y=4x+y = 4 and so {x,y}={1,3}\{x, y\} = \{1, 3\}. This contradicts N8N6=N_8 \cap N_6 = \emptyset.

* The case N8={4,5,7}N_8 = \{4, 5, 7\} is similar to the previous case. We only need to consider N7N_7 instead of N6N_6.

* If N8={1,3,4}N_8 = \{1, 3, 4\}, denote by x,y,z,tx, y, z, t the numbers of other vertices as in the figure below. We have {x,y,z,t}={2,5,6,7}\{x, y, z, t\} = \{2, 5, 6, 7\}. It follows from tx+y+zt \mid x+y+z that tt is a divisor of t+x+y+z=20t+x+y+z = 20 so t=5t = 5. On the other hand, y1+3+ty \mid 1+3+t. Therefore yy must be either 11, 33 which is impossible.

Figure 1

* If N8={5,2,1}N_8 = \{5, 2, 1\}, denote the numbers of other vertices by x,y,z,tx, y, z, t as in the figure below. In this case {x,y,z,t}={3,4,6,7}\{x, y, z, t\} = \{3, 4, 6, 7\}. By a similar argument to the previous case, we have t=4t = 4. On the other hand, x1+5+tx \mid 1+5+t, so xx is a divisor of 1010, again impossible.

Figure 2

Therefore, in each case, the numbers cannot be assigned to the vertices of the cube and the solution is complete. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.