[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.
>