Sunday, January 13, 2013

Colouring problems from Arthur Engel - problem 14

Diagram p14

Problem 14: Every space point is colored either red or blue. Show that among the squares with side 1 in this space there is at least one with three red vertices or at least one with four blue vertices.

Solution: (With reference to diagram p14)

Lemma 1: If there exist 2 red vertices at a distance of 1 unit and there doesn’t exist any unit square having at least 3 red vertices, then there must exist a unit square with 4 blue vertices.

Proof: With reference to diagram 1 on this page – draw parallel unit circles around the 2 red vertices; the circles must be perpendicular to the line joining the 2 red vertices. No point on these 2 circles can be coloured red since otherwise that point, along with the 2 red center points and the counterpart point on the other circle would form a unit square having 3 red vertices.

Lemma 2: If no 2 red vertices lie at a distance of 1 unit apart, then there must exist a unit square with 4 blue vertices.

(a) If there is no red vertex in the space, then all points must be blue and an all-blue unit square exists obviously. 
(b) If a red vertex does exist, draw a unit sphere around it. All points on the sphere must be blue and it is easy to construct a unit square having its 4 vertices on the spherical surface and hence being an all-blue unit square.

Combining lemmas 1 and 2, it follows that there must be a unit square having either 4 blue vertices or (at least) 3 red vertices.


1. Arthur Engel's book - reference on "Mathematical Olympiads" Wordpress blog

No comments:

Post a Comment