Author Topic: Prisoners and switches  (Read 6068 times)

MrPuzzle

  • Jr. Member
  • **
  • Posts: 75
Prisoners and switches
« on: 七月 08, 2004, 08:57:09 am »
I hate to be the only person who's posting problems. If I don't see other people posting a problem,  this will be my last problem posting :).

------------------
  The warden meets with the 23 prisoners when they arrive. He tells
them:
 
You may meet together today and plan a strategy, but after today you
will be in isolated cells and have no communication with one another.
 
In this prison, there is a "switch room" which contains two light
switches, labelled "A" and "B", each of which can be in the "on" or
"off" position. I am not telling you their present positions. The
switches are not connected to any appliance. After today, from time to
time, whenever I feel so inclined, I will select one prisoner at
random and escort him to the "switch room", and this prisoner will
select one of the two switches and reverse its position (e.g. if it
was "on", he will turn it "off"); the prisoner will then be led back
to his cell.  The switches will not be touched by anyone else.

Each prisoner will visit the switch room aribtrarily often. That is,
for any N it is true that eventually each of you will visit the switch
room at least N times.)

At any time, any of you may declare to me: "We have all visited the
switch room." If it is true (each of the 23 prisoners has visited the
switch room at least once) then you will all be set free. If it is
false (someone has not yet visited the switch room), you will all
remain here forever, with no chance of parole.  

Devise for the prisoners a strategy which will guarantee their
release.

froid

  • Newbie
  • *
  • Posts: 16
Prisoners and switches
« Reply #1 on: 七月 08, 2004, 11:55:40 am »
我有好题目的话也会出,不过暂时没有,请原谅  :(


n个囚犯中任意选定一个为队长。除了队长外,任何囚犯如果发现A开关是关的,而且他以前碰过A开关的次数少于两次,就把A开关打开,否则(如果A是开的,或者他已经把A关过两次了),就去动B开关。队长的任务是,看见A开关开了就把它关掉,否则就去动B开关,并且记住他关了几次A开关,如果这个次数到了2n-2次,就报告所有n个人都出来过了。

证明:

队长看见的A开了,而这并非其他某个囚犯动了A的可能情况,只有最开始A就是开的这种。但是如果他看见了2n-2次A开,表明至少有n-1个人碰过A了,否则每人最多碰两下,最多只有2n-4+1=2n-3次(加1就是第1次A就是开的情况)。而如果时间足够长,队长一定能看见2n-2次A开,因为只有队长会去关A,所以每次A开队长都会看见。如果开始A是开的,那就不用说了,囚犯里还有2n-2次开A的储备,如果开始A是关的,那么囚犯就会开2n-2次A给队长看。