How can you change the counts on vertices of a tetrahedron if you increase/decrease the counts on all vertices of a face the same amount?

Question

Hard question to ask, but here's the idea:

I'm creating a game to teach invariants. I want to make a game where each vertex of a platonic solid (we'll start with a tetrahedron) has a counter - all initially set to 0.

If you click a face, the counter on each vertex of that face increases by 1. If you right-click a face, the counters on each vertex of that face all decrease by 1.

I want to describe all possible counter values attainable in this game. Clearly a necessary condition is that the sum of the counters on the tetrahedron be a multiple of 3, but I don't think that's sufficient. For example, I don't think (0,0,1,2) is possible.

What possibilities exist? And what if we start with a different platonic solid?

Edit: I think I was wrong in asserting that (0,0,1,2) was impossible. So maybe my necessary condition is sufficient? Is the same true for an octahedron and an icosahedron?

Answer 1

To add to the other answers, one often does not need to use linear algebra to solve simple puzzles like this one. For this puzzle it suffices to observe that incrementing one face and decrementing another results in +1 to one vertex and −1 to an adjacent vertex, and clearly any such pair is possible. Thus it obviously is possible to obtain any configuration with sum divisible by 3 simply by using the appropriate number of increments and then adjusting the counts one by one via the (+1,−1) operation. Now this is more ad-hoc, but the general meta-technique of finding move sequences that have as local effect as you can find applies to many puzzles including general permutation puzzles such as the Rubik's cube.

To demonstrate the power of this meta-technique, I will fully solve the question for the octahedron, which was not solved in the other answers.

For the octahedron, the (+1,−1) operation increments a vertex and decrements the opposite vertex. Since we are unable to find a way to change adjacent vertices, we should immediately suspect that there is a stronger invariant involving opposite vertices. Indeed, the 3 pairs of opposite vertices have the same sum, and this invariant is trivial to prove.

Are all these states possible? Yes! We now give an explicit algorithm to solve any such state (i.e. find a move sequence to change it to the all-zero state). Orient the octahedron with 1 top vertex, 1 bottom vertex and the other vertices facing left, right, front and back respectively. First solve the bottom vertex via any lower face and the back vertex via any upper face. Next solve the left and right vertices via the upper-left-front and upper-right-front face respectively. Now we have solved all vertices except at most the front and top vertex. I claim that those are also solved. To see why, note that the 3 opposite-sums remain equal (after the move sequence that generates the state and after any further moves), and at the end the left and right vertices sum to zero, the other sums must sum to zero as well.

Answer 2

The value of each vertex is the sum of the clicks on each face incident on that vertex. This gives one linear equation for each vertex in terms of face clicks. This leads to slightly different situations for different Platonic solids.

• For the tetrahedron, this gives a linear system of four equations (four vertices) in four unknowns (four faces). This is always uniquely solvable in rational numbers (because these four equations are linearly independent -- in fact the vertex equations for any Platonic solid are linearly independent). Any set of vertex counter values corresponds to exactly one set of (rationally many) face clicks. As noted in comments, to ensure that these rational numbers are actually integers, the sum of the vertex counter values must be a multiple of $3$. (The subsequent cases also give rational solutions and a similar condition ensure integrality.)
• For the cube, this gives a linear system of eight equations in six unknowns. This system is overdetermined. While some sets of vertex values will be realizable, not all such sets will be. (This most closely follows your intended example for they hypothetical tetrahedron in the Question. While the example in the Question wasn't apt, a similar example for a cube can be.)
• For the octahedron, there are six equations in eight unknowns. This system is underdetermined. In this case, for each set of vertex counter values, there will be multiple ways to click the faces to get those vertex counter values.
• For the dodecahedron, there are $20$ equations in twelve unknowns. This is again overdetermined. Some sets of counter values cannot be realized by any set of face clicks.
• For the icosahedron, there are twelve equations in $20$ unknowns. This system is underdetermined. In this case, for each set of vertex counter values, there will be multiple ways to click the faces to get those vertex counter values.

(Notice that the dualities cube $\leftrightarrow$ octahedron and dodecahedron $\leftrightarrow$ icosahederon are being demonstrated in the above.)

Answer 3

The matrix $\pmatrix{0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0}$ represents a surjection from $\mathbb Z^4 \approx$ (the free abelian group on the four faces) onto $\mathbb Z^4 =$ (the free abelian group on the four vertices). One can see by a pretty quick row reduction calculation (the same calculation shows that the determinant equals $\pm 1$, although I'm not sure if its $+1$ or $-1$ because I was careless with row permutations). Therefore every possibility exists.

For the octahedron, there are eight faces and six vertices, so the corresponding matrix represents a group homomorphism $\mathbb Z^8 \mapsto \mathbb Z^6$. For the icosahedron, there are 20 faces and 12 vertices, so the corresponding matrix represents a group isomorphism $\mathbb Z^{20} \mapsto \mathbb Z^{12}$. One must do the row reduction calculation in each case, but I'll bet that in both cases the group homomorphism is surjective. Nonetheless, without doing the calculation one does not know a priori that the homomorphisms are surjective.

Answer 4

Let $F$ be the set of faces and $V$ the set of vertices; say $f$ and $v$ are their cardinalities, and choose an order on each set. Then the incidence relation cab be represented by an $v\times f$ incidence matrix $A$ with entries in $\{0,1\}$. If $C\in\Bbb Z^f$ is a column vector representing the net number of clicks per face, the result for the vertices is given by the matrix$\times$vector product $AC$. Since $C$ can be any integer column vector, you are looking for the $\Bbb Z$-span of the columns of $A$.

This $\Bbb Z$-span can be more easily understood by performing a column echelon computation with only integral coefficients on the matrix, dropping zero columns. For instance for the tetrahedron we can transform $$ A= \pmatrix{0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0} \to\pmatrix{3&-1&-1&-1\\0&1&0&0\\0&0&1&0\\0&0&0&1}=A' $$ and it follows that the matrix has (full) rank $4$, so there are no linear equations imposed on vertex counts $(n_1,n_2,n_3,n_4)$ to be in the image. The only condition is the congruence $n_1+n_2+n_3+n_4\equiv0\pmod3$, since then the solution $C=(\frac{n_1+n_2+n_3+n_4}3,n_2,n_3,n_4)$ to $A'C=(n_1,n_2,n_3,n_4)$ is integral.