At the vertices $A, B, C, D, E, F, G, H$ of a cube, $2001, 2002, 2003, 2004, 2005, 2008, 2007$ and $2006$ stones respectively are placed. It is allowed to move a stone from a vertex to each of its three neighbours, or to move a stone to a vertex from each of its three neighbours. Which of the following arrangements of stones at $A, B, \ldots , H$ can be obtained? $(\text{a})\quad 2001, 2002, 2003, 2004, 2006, 2007, 2008, 2005;$ $(\text{b})\quad 2002, 2003, 2004, 2001, 2006, 2005, 2008, 2007;$ $(\text{c})\quad 2004, 2002, 2003, 2001, 2005, 2008, 2007, 2006.$
Problem
Source: Italian TST 2004 - Problem 1
Tags: geometry, 3D geometry, linear algebra, matrix, tetrahedron, rectangle, invariant
grobber
19.06.2004 12:55
Is it by any chance true that all three of them are attainable? That's what seems to be true, but I there's something missing, especially since I didn't devise the sequence of moves. I used a matrix ($8\times 8$) and showed that the linear system of equations represented by it is compatible. Basicly, I denoted by $a,b,c,d,e,f,g,h$ the number of moves of the first kind operated on the vertices (labeled in your first picture, in the same order, $2001,2002,2003,2004,2005,2008,2007,2006$). Then we get a system of eqns of the type $3a=b+d+e$, etc. The matrix formed by the coefficients ($3$ and $-1$'s) has rank $7$ and the sum of the elements on each column is $0$. For any result column, the sum of the elements is also $0$ because the total sum of the numbers is constant. This means that the new column can't form any $8\times 8$ non-zero determinant with any other $7$ columns of the original matrix, thus making the system compatible. This means that we can find $a,b,c,d,e,f,g,h$. What's not clear is whether these solutions are natural for all three separate cases. Maybe in some cases they're not natural numbers and then we're toast . Anyway, I tried.. .
MindFlyer
19.06.2004 13:18
I suggest you to try a more elementary approach. It's problem 1, after all!
grobber
19.06.2004 15:55
Ok, I know for sure that the first one isn't attainable. Consider the two tetrahedrons $2005,2004,2002,2007$ and $2001,2006,2003,2008$. The difference between the sums of the vertices of these two tetrahedrons is $0$ at first and it can only decrease/increase by $6$ at a time (after a move), so it can't be $4$, as in the first picture. In the other two pictures the differences are $0,-6$, so I'll have to find other arguments (I'm sure at least one of them is attainable, though ).
grobber
19.06.2004 16:02
Sorry for the repeating nagging (), but I've just realized that the third config isn't attainable either: Consider the two rectangles $2001,2006,2007,2002$ and $2005,2004,2003,2008$. The difference between the sums of their vertices is $-4$, and it can increase/decrease by $4$, so it can't be $2$, like in the third picture. As for the second one, it's obvious: just perform the first kind of move on the vertices labeled $2008,2004$ at the beginning. So, the answer is: We can obtain only (b).
MindFlyer
20.06.2004 10:03
Yesssss! Note that a single invariant could prove both (a) and (c) are not attainable. Consider the vertices labelled 2005, 2001, 2008, 2006 in the first picture: their sum has constant parity, and in the first picture it's even, while in (a) and (c) it's odd.