You may also like

problem icon

Weekly Problem 41 - 2007

The Queen of Spades always lies for the whole day or tells the truth for the whole day. Which of these statements can she never say?

Proximity

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

Solution to Proximity by Tony and John, State College Area High School, PA, USA.
icosahedron
We give a proof by contradiction.

Suppose no vertex has more than one red neighbour.

Without loss of generality say the vertex at the top is red. Then none of the five vertices around the upper horizontal pentagon, which are neighbours of the top vertex, are red. This is because if any of them were red then there would be two vertices each having two red neighbours which is not allowed.

Now consider the five vertices around the lower horizontal pentagon. Only one of these can be red because if two were red then there would be a vertex with two red neighbours which is not allowed.

The argument shows that of the eleven vertices discussed only two can be red. We know that there is a third red vertex so it must be the vertex at the bottom. However if the bottom vertex is red then there will be two vertices on the lower horizontal pentagon having two red neighbours which is not allowed.

We have reached a contradiction.

So the assumption that no vertex has more than one red neighbour is false.

We have proved that there is at least one vertex with two red neighbours.