[Edu-sig] A mathematical teaser ...

[Gregor Lingl]

Thanks for your explanations - you arrived ad the right result, as e. g.
a program, done by Tim Peters, shows.

Hava look at the corresponding thread at tutor@python.org list:

http://mail.python.org/pipermail/tutor/2003-February/020846.html

(This is only one of the messages of the thread, which you can find at
http://mail.python.org/pipermail/tutor/2003-February/thread.html )

Regards
Gregor Lingl


Christian Mascher schrieb:

>>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.
>>
>>    
>>
>
>
>_______________________________________________
>Edu-sig mailing list
>Edu-sig@python.org
>http://mail.python.org/mailman/listinfo/edu-sig
>
>
>  
>