Seven vertices of a cube are labeled 0, and the remaining vertex labeled 1. You’re allowed to change the labels by picking an edge of the cube, and adding 1 to the labels of both of its endpoints. After repeating this multiple times, can you make all labels divisible by 3?
It's from an invariant handout. I am not even able to get the main idea and haven't been able to proceed too.
So first I named the vertices $a,b,c,d,e,f,g,h$ and let $a$ be the vertex having label $1$ and others $0$. Define $f(i) =$ the no labeled in the vertex $i$ Now, after pairing non adjacent vertices , let us say $(a,c,f,h)$ and $(b,d,e,g)$ , we get that if $a$ will be divisible by $3$ , it will be due to $3$ other vertices let's say $(b, d, e)$ , and we will have $3k+1=f(a)$. But $f(b),f(d),f(e)$ are divisible by $3$. So these vertices must have $2 \mod 3$ to other $2$ vertices .
But what should I do next ?
Thanks in advance! Also this question looks very well known, but I tried searching in MSE , but couldn't get anything.
You can color the vertices in two colors, white and black, with adjacent vertices having different colors.
Now assume the initial label $1$ vertex is white, then sums of whites will be always $1$ more than sums of blacks, since you are always incrementing both by $1$.
Then if all are divisible by $3$, it will lead to a contradiction, so it's impossible.