各种囚犯问题(第1,2,4(1)已解出)

superacid

1.对100个囚徒，法官给每个囚徒指派一个1到100之间的编号，不同的囚犯编号可能会重复。每个囚徒知道别人的编号，但是不知道自己的。然后法官给每个囚徒一次机会猜测自己的编号。现在的提问是：如果发编号之前，囚犯可是商量一个对策，有什么策略能保证至少有一个囚徒能猜对自己的编号？
2.100个囚犯，每个人头顶上有一个黑帽子或者白帽子，至少有一个黑帽子，每个人可以看到其他人帽子的颜色却看不到自己的，监狱长先让大家看看别人头顶上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就拍手，第一次关灯没有声音，第二次也没有，一直到第5次，才有声音响起，问有多少人带着黑帽子？
3.(1)有100个囚犯分别关在100间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？
(2)大家都知道房间里的灯泡一开始是不亮的。如果灯泡的初始状态并不确定，问题有解吗？
(3)在以上协议中，只有一个人能知道所有人都来过房间。是否存在一个协议，使得最终可以产生两个人，他们都知道所有人都进过房间？如果存在这样的协议，给出一个来；如果不存在，证明之。为了方便思考，你可以暂时假设初始时房间的灯泡不亮。
(4)还是100个囚犯，还是一个空房间，还是要求所有囚犯事先构造一个协议，能保证有人可以断定出所有人都来过房间。不过，这次不同的是，房间里有两个灯泡，分别由两个开关来控制（不妨假设初始时他们都是不亮的）。大家估计要说了，一个灯泡都能解决的事儿，用两个灯泡还不容易？嘿嘿，这次有一个附加的要求：所有人都必须遵循同一套策略。
4.(1)100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯，坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后，看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了，他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略，那么最理想的策略是什么？
(2)无穷个囚犯面向数轴的正方向依次就座，第i个囚犯坐在数轴上坐标为i的地方，他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子，然后依次叫每个囚犯猜测自己头上的帽子颜色，猜对了的予以释放。另外一点和原来不同的是，囚犯们不能听到其他人的猜测。另外注意到，由于每个人前面都有无穷多个人，因此囚犯们无法通过数他前面的人数来判断出自己的位置，于是我们不得不加上一句：每个人都知道他后面有多少人（即他是第几个被问的）。同样地，事先所有囚犯可以商量出一个策略,它可以保证除了有限个囚犯之外，其他囚犯全部释放！你能想出这个策略吗？
5.典狱长要和100个囚犯玩这么一个游戏。典狱长给每个囚犯发两个手套，一个黑色的，一个白色的。之后，每个囚犯的额头上都会写上一个实数，所有这100个实数互不相同。每个囚犯都能看到其他99个囚犯前额上所写的数，但不能看到自己的数。接下来，每个囚犯必须独立地决定把哪个手套戴在哪只手上。等到所有囚犯都戴好了手套，典狱长会把他们按照前额上所写的数从小到大地排好，并要求他们手牵着手站成一横排。如果每两只握在一起的手都戴着相同颜色的手套，那么所有100个囚犯都可以被释放。在游戏开始前，他们可以聚在一起，商量一个对策。游戏开始后，囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗？

superacid

顶到n楼之后发解答

superacid

没事顶一下吧，题目还是挺有意思的