[Edu-sig] A mathematical teaser ...

Christian Mascher christian.mascher@gmx.de
Tue, 18 Feb 2003 18:27:39 +0100


> From: Gregor Lingl <glingl@aon.at>
> 
> 
> What strategy would you recommend, to solve the problem stated below?
> (For those of you who also read the tutor-list, please notice, that -
> although
> I posted this same problem there also - my *question* here is
> (intentionally)
> different).


Hi, 

thanks for the interesting problem. How does one get started on a way to
a solution? This is what I did (without a computer, but perhaps with
some programming experience involved):


[In case you want to do it youself: don't read on.]


(no-spoiler space)











a) visualize, find a short representation:

The state of the lock can be represented by four binary digits in an
2-2-array like this:
 0 0  or 1 0
 1 1     1 1

b) classify:

I wrote down all possible combinations for a locked state. These can be
grouped into three classes:

 type 1:  array contains only a single 0 or only a single 1
 
 type 2p: array contains two parallel 0 and two parallel 1
          like in  00
                   11                    
 type 2d: array contains two diagonal 0 and 1
          like in 01
                  10

I made the distinction between 2p and 2d later, when I realized how the
operations work on these types. At first I started with just two
classes/types. Type 1 came quite naturally, because 0 and 1 can be
interchanged without changing the problem.

c) analyse the operations on the types:

How do the four different operations P1,P2,D1 and D2 change the type. By
looking at the visual arrays, one sees that D2 is quite special:
If D2 works on type 2d, the lock opens.
If it works on type 1 or 2p, it leaves them in their respective class.
Now its quite clear how to get a solution.

The last bit was working out a graph - a sort of seaving procedure -
where you start with any state, then use D2, coming to type 1 or 2p
(when you haven't opend the lock already), use P2 to go to type 1 or 2d
and so on. Symbolically:

1,2p,2d -->D2--> 1,2p -->P2--> 1,2d -->D2--> 1 -->(D1 or P1)-->2p,2d
-->D2--> 2p -->P2--> 2d -->D2--> open.

I think this is the shortest path, but haven't proven it rigorously.
 
Greetings,

Christian



> 
> Thanks for letting me know your ideas
> Gregor
> 
> The problem is taken from "Spektrum der Wissenschaft", Feb. 2003 (which
> is the German edition of Scientific American):
> 
> Coded entry
> 
> To cut costs for a doorguard who asks silly mathematical riddles, the union
> of mathematical logicians has devised a sophisticated locking apparatus for
> their union's home.
> The lock of the door is controlled by four simple switches, which are
> arranged in a square. The door opens if all the switches are "on" or if all
> of them are "off". When a member arrives to enter, the door always is
> locked, which means that some switches are in the on position and some are
> off.
> No one who wants to enter can see the switches or touch them directly.
> Instead, there are four buttons on the door, labelled "P", "D", "1" and
> "2".
> If you press "P", a pair of two switches in a horizontal or vertical row is
> randomly selected. If you press "D" a pair of diagonally arranged switches
> is randomly selected.
> After this selection has taken place, pushing button "1" randomly selects
> one of the previously selected switches and changes its position.
> Contrary to that,
> pushing "2" switches both of them. The sequence "letter, digit" may be
> repeated until the door opens (or you lose patience).
> Find the shortest complete code which opens the door with certainty,
> regardless of the original position of the four switches.
>