Maths Olympiad Prep

Library / /26 of 45

Combinatorics Difficulty 5.8 AIME, harder Prove it Romania

a) Prove that one cannot assign to each vertex of a cube 8 distinct numbers from the set {0,1,2,3,,11,12}\{0, 1, 2, 3, \ldots, 11, 12\} such that, for every edge, the sum of the two numbers assigned to its vertices is even.

b) Prove that one can assign to each vertex of a cube 8 distinct numbers from the set {0,1,2,3,,11,12}\{0, 1, 2, 3, \ldots, 11, 12\} such that, for every edge, the sum of the two numbers assigned to its vertices is divisible by 3.

Solution

a) If in a vertex is written a number from the given set, then its "neighbors" have to be of the same parity. This shows that all the written numbers must have the same parity. Since the set contains 7 even and 6 odd elements, this task is impossible.

b) The task can be accomplished through assigning to "neighbor" vertices distinct numbers which are not divisible by 3, and which yield different residues mod 3. An example is shown in the figure.
Figure 1

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.