Library / Local Mathematical Competitions /3 of 23

Local Mathematical Competitions

Combinatorics Difficulty 4.5 AIME Prove it Romania

Of the vertices of a cube, 7 of them have assigned the value $0$ , and the eighth the value $1$ . A move is selecting an edge and increasing the numbers at its ends by an integer value $k > 0$ . Prove that after any finite number of moves, the g.c.d. of the $8$ numbers at vertices is equal to $1$ .

Solution

Let us alternately colour the vertices in black and white. After any move, the difference between the sums of the numbers at the black and the white vertices remains $1$ , therefore the g.c.d. of the $8$ numbers is equal to $1$ (as it is dividing the difference of the sums mentioned above).

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.