IMO shortlist 1985/5 solution

26th IMO 1985 shortlist

Problem 5

T is the set of all lattice points in space. Two lattice points are neighbors if they have two coordinates the same and the third differs by 1. Show that there is a subset S of T such that if a lattice point x belongs to S then none of its neighbors belong to S, and if x does not belong to S, then exactly one of its neighbors belongs to S.

Solution

Let S be the set of points (x, y, z) with 2x + 4y + 6z = 0 mod 7. If 2x + 4y + 6z

= 0 mod 7, then (x, y, z) is in S
= 1 mod 7, then (x, y, z+1) is in S
= 2 mod 7, then (x-1, y, z) is in S
= 3 mod 7, then (x, y+1, z) is in S
= 4 mod 7, then (x, y-1, z) is in S
= 5 mod 7, then (x+1, y, z) is in S
= 6 mod 7, then (x, y, z-1) is in S

So if x is in T - S, then at least one of its neighbours belongs to S. Also if (x, y, z) is in S, then (x±1, y, z), (x, y±1, z), (x, y, z±1) are not in S. In other words, if a point is in S, then none of its neighbours are in S. Finally, if (x, y, z) is in S, then none of (x±2, y, z), (x, y±2, z), (x, y, z±2), (x±1, y±1, z), (x±1, y, z±1), (x, y±1, z±1) are in S, so no point has two of its neighbours in S. That establishes that S has the required properties.

Comment

2x + 4y + 6z may seem fairly obvious, but I got there by a tortuous route. I started, of course, by looking at 1D. That is obvious: ... 0 0 X 0 0 X 0 0 X 0 ... , where X denotes the members of S. 1 point in 3 belongs to S.

2D is not quite so obvious. But with a little experimentation one can get:

0  0  0  0  X  0
0  0  X  0  0  0 
X  0  0  0  0  X
0  0  0  X  0  0
0  X  0  0  0  0

Obviously 1 point in 5 belongs to S and the pattern repeats with period 5 in both directions. At this point I started looking for a suitable pattern for 3D. I needed 1 point in 7. It did not take long to find:

0  0  0  X  0  0  0
X  0  0  0  0  0  0
0  0  0  0  X  0  0
0  X  0  0  0  0  0
0  0  0  0  0  X  0
0  0  X  0  0  0  0
0  0  0  0  0  0  X
0  0  0  X  0  0  0

I then tried to think what the next plane up would look like. After some more fiddling around I hit on:

2  6  3  0  4  1  5
0  4  1  5  2  6  3
5  2  6  3  0  4  1
3  0  4  1  5  2  6
1  5  2  6  3  0  4
6  3  0  4  1  5  2
4  1  5  2  6  3  0

The number denotes the z-coordinate. So the pattern represents a 7 x 7 x 7 cube of lattice points which repeats.

At this point it occurred to me that since the pattern in each line was the same, the points belonging to S satisified some equation like 4x + 2y - z = 0 (or some constant, but 0 if we take the origin in the right place) mod 7. I then junked all the scaffolding and wrote out the solution above.

26th IMO shortlist 1985