E.W.Dijkstra Archive: A problem solved by my nephew Sybrand L. Dykstra (EWD 904)

A problem solved by my nephew Sybrand L. Dijkstra

Given a circular arrangement of 16 lights and one pushbutton. When the button is pushed the new state of each light depends as follows on the (old) states of that light and its clockwise neighbour:

when they were both on or both off, the light is on in the new state;
when one was on and the other was off, the light is off in the new state.

Prove that all lights are burning after the button has been pushed 16 or more times.

* *
*

Having studied "Een methode van programmeren" --"A method of programming"-- by W. H. J. Feijen and me, and hence being familiar with the symmetry and associativity of the equivalence, my young nephew solved this problem essentially by the following argument.

An arbitrary light is called "nr.0", and the clockwise neighbor of light nr.i is called light nr. i+1. With

B(i,j) ≡ "light nr. i is burning after the j-th push"

the behaviour of the system is given by

(0) B(i,j+1) ≡ B(i,j) ≡ B(i+1, j)

In preparation of a proof by mathematical induction we observe:

(i) since 2⁰ = 1, (0) equivales

B(i, j+2⁰) ≡ B(i,j) ≡ B(i+2⁰, j). (End of (i).)

(ii) From (the induction hypothesis)

(1) B(i, j+2ⁿ) ≡ B(i,j) ≡ B(i+2ⁿ,j)

we derive, since 2ⁿ + 2ⁿ = 2ⁿ⁺¹, by substituing i+2ⁿ for i

(2) B(i+2ⁿ, j+2ⁿ) ≡ B(i+2ⁿ, j) ≡ B(i+2ⁿ⁺¹, j)

and, similarly, by substituting j+2ⁿ for j

(3) B(i, j+2ⁿ⁺¹) ≡ B(i, j+2ⁿ) ≡ B(i+2ⁿ, j+2ⁿ)

Eliminating B(i+2ⁿ, j+2ⁿ) from (2) and (3) yields

(4) B(i, j+2ⁿ⁺¹) ≡ B(i, j+2ⁿ) ≡ B(i+2ⁿ,j) ≡ B(i+2ⁿ⁺¹, j)

Eliminating B(i, j+2ⁿ) ≡ B(i+2ⁿ, j) from (1) and (4) yields

(5) B(i, j+2ⁿ⁺¹) = B(i,j) ≡ B(i+2ⁿ⁺¹, j)

i. e. with n+1 substituted for n. (End of (ii).)

Combining observations (i) and (ii), we have proved (1) for all natural n, in particular for n=4:

(6) B(i, j+16) ≡ B(i, j) ≡ B(i+16, j)

Since lights nr. i and i+16 are identical, B(i, j) ≡ B(i+16, j), hence, from (6), B(i, j+16) .

q.e.d.

The above proof is, all by itself, nice enough to be recorded. I am particularly delighted, for when the section on predicate calculus in our book kindles the above in the mind of a 15-year-old, the seed is worth to be sown.