Competition problem — Combinatorics

Library / /3 of 27

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.