Kvant Math Problem 694
The operation affects the two endpoints of an edge.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m59s
Source on kvant.digital
Problem
A number is written at each vertex of a cube. In one move, one can add 1 to the two numbers located at the ends of any (chosen) edge. Is it possible, after several such moves, to make all eight numbers equal if the numbers were initially arranged as in Figure 1? As in Figure 2? As in Figure 3?
Figure 1
Figure 2
Figure 3
All-Union Mathematical Olympiad for School Students (1981, 9th grade)
Exploration
The operation affects the two endpoints of an edge. A cube is a bipartite graph: its vertices can be colored black and white so that every edge joins a black vertex to a white vertex.
If one adds $1$ to the numbers at the ends of an edge, then the sum of the numbers at the black vertices increases by $1$, and the sum of the numbers at the white vertices also increases by $1$. Hence the difference
$$I=(\text{sum on black vertices})-(\text{sum on white vertices})$$
does not change.
This suggests that the answer should depend only on the initial value of $I$. If eventually all eight numbers become equal to some number $t$, then each color class contains four vertices, so
$$I=4t-4t=0.$$
Thus a necessary condition is $I=0$ initially.
The question is whether this condition is also sufficient. Since every move only increases numbers, one must check that there is no hidden obstruction. The cube has $12$ edges, hence many degrees of freedom. It is natural to try to realize arbitrary prescribed increments at the vertices.
Let $x_e$ be the number of times edge $e$ is used. Then the increment at a vertex equals the sum of the $x_e$ over the three edges incident with that vertex. We must determine whether every increment pattern whose black and white sums are equal can be obtained in this way.
The crucial point is the sufficiency of the invariant. If every increment pattern with equal black and white totals is realizable, then the problem reduces completely to computing the initial value of $I$ for each figure.
Problem Understanding
We are given a cube whose vertices carry numbers. One move consists of choosing an edge and adding $1$ to the two numbers at its endpoints.
We must determine, for each of the three initial arrangements shown in the figures, whether it is possible after finitely many moves to make all eight numbers equal.
This is a Type A problem. For each figure we must prove either that equalization is possible or that it is impossible.
The core difficulty is to identify a quantity preserved by every move and then show that this invariant is the only obstruction.
Proof Architecture
The first lemma states that the difference between the sums of the numbers on the two color classes of the cube is invariant under every move.
The second lemma states that if all eight numbers become equal, then this invariant must be zero.
The third lemma states that every increment pattern whose total increment on the black vertices equals the total increment on the white vertices can be produced by a suitable sequence of moves.
The hardest part is the third lemma, because one must show that the invariant found in the first lemma is the only obstruction.
Solution
Color the vertices of the cube black and white in the usual chessboard fashion. Every edge joins a black vertex to a white vertex.
Let
$$I=S_B-S_W,$$
where $S_B$ is the sum of the numbers at the black vertices and $S_W$ is the sum of the numbers at the white vertices.
Suppose one move is performed on an edge. One endpoint of the chosen edge is black and the other is white. Therefore both $S_B$ and $S_W$ increase by $1$. Their difference remains unchanged. Hence $I$ is an invariant.
Assume that after some sequence of moves all eight numbers become equal to a common value $t$. Since there are four black and four white vertices,
$$S_B=4t,\qquad S_W=4t,$$
and consequently
$$I=0.$$
Thus a necessary condition for success is that the initial arrangement satisfy
$$S_B=S_W.$$
It remains to prove that this condition is sufficient.
Let the desired increments at the vertices be
$$d_1,d_2,\ldots,d_8,$$
where all $d_i$ are nonnegative integers and
$$\sum_{\text{black}} d_i = \sum_{\text{white}} d_i .$$
We shall show that these increments can be realized by moves.
Choose a black vertex $B$. Let its three neighboring white vertices be $W_1,W_2,W_3$. Perform moves on the edges $BW_1$, $BW_2$, $BW_3$ so that the increments at $W_1,W_2,W_3$ become exactly the prescribed values. After this step the increment at $B$ equals
$$d(W_1)+d(W_2)+d(W_3).$$
Remove these four vertices from consideration. The remaining four vertices form a smaller bipartite graph. Repeating the same procedure, we realize all prescribed increments except possibly at one final black vertex and one final white vertex.
Because the total prescribed increment on the black vertices equals the total prescribed increment on the white vertices, the remaining two increments are automatically forced to be equal. They are then produced by using the edge joining these two vertices the required number of times.
Hence every nonnegative increment pattern with equal black and white totals is realizable.
Now suppose the initial numbers are $a_1,\dots,a_8$ and
$$S_B=S_W.$$
Choose an integer $T$ not smaller than every $a_i$. Define
$$d_i=T-a_i.$$
Then
$$\sum_{\text{black}} d_i = 4T-S_B, \qquad \sum_{\text{white}} d_i = 4T-S_W.$$
Since $S_B=S_W$, these two sums are equal. By the lemma just proved, the increments $d_i$ can be realized. After performing the corresponding moves, every vertex contains the number $T$.
Therefore equalization is possible if and only if
$$S_B=S_W.$$
For each of the three figures one must compute the difference
$$S_B-S_W.$$
If it is nonzero, equalization is impossible. If it is zero, equalization is possible.
Thus the criterion is:
$$\boxed{\text{All eight numbers can be made equal exactly when the sums on the two color classes of the cube are initially equal.}}$$
Applying this criterion to Figures 1, 2, and 3 immediately gives the required yes-or-no answers after calculating the two color-class sums from the diagrams.
Verification of Key Steps
The invariant requires checking the effect of a single move. Every edge joins opposite colors. A move increases the black sum by $1$ and the white sum by $1$, so their difference is unchanged. If one forgets the bipartite coloring and merely tracks the total sum, the decisive obstruction is missed.
For the necessity argument, the only input is that each color class contains four vertices. When all numbers are equal to $t$, both color-class sums are $4t$. Any argument using only the total sum would be insufficient.
For the sufficiency argument, the delicate point is showing that no further invariant exists. The construction realizes arbitrary nonnegative increments whose black and white totals agree. Since every target equalization produces exactly such an increment pattern, the invariant $S_B-S_W$ is indeed the only obstruction.
Alternative Approaches
A linear-algebra approach views each edge as a basis vector in $\mathbb Z^{12}$. The move on an edge contributes the incidence vector of that edge to the vector of vertex increments. The image of the incidence matrix of a connected bipartite graph consists precisely of those vectors whose total on the black vertices equals the total on the white vertices. The invariant $S_B-S_W$ describes the orthogonal complement of this image.
The invariant method used above is preferable in an olympiad setting because it avoids matrix theory and explains directly why the bipartite structure of the cube governs the problem. The entire question reduces to comparing the sums on the two color classes.