Browse · MathNet
PrintRomanian Mathematical Olympiad
Romania counting and probability
Problem
a) Prove that one cannot assign to each vertex of a cube 8 distinct numbers from the set 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 such that, for every edge, the sum of the two numbers assigned to its vertices is divisible by 3.
b) Prove that one can assign to each vertex of a cube 8 distinct numbers from the set 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.
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.
Techniques
Coloring schemes, extremal argumentsPigeonhole principleOther