A 3 x 3 grid of buttons, numbered like a keypad

combinatorics/raised.buttons New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A 3 x 3 grid of buttons, numbered like a keypad

    7 8 9
    4 5 6
    1 2 3

has some buttons raised and some lowered.  The aim is to finish with
all buttons raised except the middle one, 5.  Rules:

a) You can only press raised buttons.
b) Pressing a corner button flips that and all adjacent buttons.  If
   you press 7, it flips 7, 8, 5 and 4 [Editor: was "9"].
c) Pressing an edge button flips all buttons on that edge.  If you
   press 8, it flips 7, 8 and 9.
d) Pressing the centre button flips all non-corner buttons: 5, 8, 6,
   2 and 4.

1) Can the puzzle be solved from every arrangement with at least one
   button raised?
2) Which arrangements cannot be reached from *any* arrangement?
3) Are there any arrangements which cannot be reached from *every*
   arrangement?

(From the OS/2 program "Brain Teaser" by Mr Nijland.)

[ Editor: 9 is not adjacent to 7, and the solution's move sequences
work only with 7 flipping 4, 5, 7, 8. ]

Show solution

Any arrangement can be reached from any initial position, except the
initial position in which all buttons are down.

First, note that if there is no restriction on pushing only raised
buttons, it is possible to flip any single button.  1-2-3-4-5-7 flips 1,
2-4-6-7-9 flips 2, and 2-4-5-6-8 flips 5.  Thus, given any initial and
any final pattern, there is a set of buttons which will change the
initial to the final position.  (From the above rules, you can work out
that 1 needs to be pushed if an odd number of 1,3,6,7,8 need to be
changed, 2 needs to be pushed if an odd number of 1,2,3,4,5,6 need to be
changed, and 5 needs to be pushed if an odd number of 1,3,5,7,9 need to
be changed.)

Given an initial and a final position, find the set of buttons which
need to be pushed.  We will now show that each of these buttons can
actually be pushed, in combination with some self-cancelling double
pushes.

If any outer button B (that is, not 5) needs to be pushed and is not up,
and there is at least one outer button which is up, find the nearest
such button along the outside.  (Thus, if only 7 and 8 are up and 2
needs to be pushed, 7 is the nearest button).  Push that button; it will
go down, but the button one closer to B will now be up.  If that button
isn't B, push it, and so on until you reach B.  The button which was
pushed just before B will be back up again (since B put it up), so it
can be pushed.  Now the next button over will be up, so you can push it,
and so on.  (In the above example, pushing 2 with 7 and 8 up would
require 7-4-1-2-1-4-7.)

If 5 is the only button up and 1 or 2 needs to be pushed, push 5-2-1-5,
and then use the above method to push 1 or 2 again.

If 5 is not up and needs to be pushed, but a corner (say 1) is up, push
1-2-5-1 if 2 is down (so that the first 1 puts it up), or 1-5-2-1 if 2
is up, and then use the above method to push 2 again.

If 5 is not up and needs to be pushed, and no corner is up but an edge
(say 2) is up, push 2-1-5.  Now neither 1 nor 2 is up, but 3 is up (the
2 put it up), so 3-2-3 will push 2; this puts 1 up, so you can now push
1.

Here is an example: starting with just 1 up, get to the position
with everything but 5 up.  The necessary pushes are 5, 6, 8, and 9.

789
456
123

DDD
DDD
UDD

To push 5, we will do 1-2-5-1 first, and we must then push 2 in this
position:

DUD
UUU
DDU

Pushing 2 can be done by 3-2-3:

DUD
UUU
UUD

Now we push 6 and 8, both up which are already up:

UDD
UUD
UUU

The nearest outer buttons to 9 which are up are 7 and 3; if we start at
3, then we push 3-6-9-6-3:

UUU
UDU
UUU

-- David Grabiner <grabiner@math.harvard.edu>

> Any arrangement can be reached from any initial position, except the
> initial position in which all buttons are down.

The final position with all buttons raised is impossible to reach
from any other position.

-- Jeff Kenton <jkenton@world.std.com>