IMO 1983 SL 13

Origin: LUX

Problem

Let E be the set of 19833 points of the space R3 all three of whose coordinates are integers between 0 and 1982 (including 0 and 1982). A coloring of E is a map from E to the set {red, blue}. How many colorings of E are there satisfying the following property: The number of red vertices among the 8 vertices of any right-angled parallelepiped is a multiple of 4?

Solution

Given any coloring of the 3\times1983−2 points of the axes, we prove that there is a unique coloring of E having the given property and extending this coloring. The first thing to notice is that given any rectangle R1 parallel to a coordinate plane and whose edges are parallel to the axes, there is an even number r1 of red vertices on R1. Indeed, let R2 and R3 be two other rectangles that are translated from R1 orthogonally to R1 and let r2, r3 be the numbers of red vertices on R2 and R3 respectively. Then r1 + r2, r1 +r3, and r2 +r3 are multiples of 4, so r1 = (r1 +r2 +r1 +r3 −r2 −r3)/2 is even. Since any point of a coordinate plane is a vertex of a rectangle whose remaining three vertices lie on the corresponding axes, this determines uniquely the coloring of the coordinate planes. Similarly, the coloring of the inner points of the parallelepiped is completely determined. The solu- tion is hence 23\times1983−2 = 25947.