※ 引述《LPH66 (-6.2598534e+18f)》之铭言： : 囚犯猜帽子这个有着许多变形的题目又有一个新变形了 : 这个变形来自 Matt Parker 的 youtube 频道 : https://www.youtube.com/watch?v=7hJ4Azr--s8 : 现在这里有 N 个囚犯排成一直排, 有 N+1 顶帽子编号由 1 到 N+1 : 这些帽子随机地戴到这 N 个囚犯头上, 余下一顶 : 每个囚犯可以看到他前面的所有的囚犯头上的帽子 : 但他自己的和他後面的都看不到, 当然余下的那顶所有囚犯也都不知道 : (也就是说最後一个人只能看到 N-1 顶帽子, 有两顶他看不到) : 现在由最後一个人开始猜自己头上的帽子是几号 : 照惯例猜对的释放, 猜错的处死 : 不过限制是：只能猜 1 ~ N+1 (也就是所有帽子的号码)，以及不能猜已经被猜过的号码 : 那麽, 如果前面的人能知道後面的人的猜测是对是错, 最少能保证多少人获释？ : 如果前面的人不知道後面的人的猜测是对是错, 最少又能保证多少人获释？ : Matt Parker 在影片中有提到他的答案是 (右边关灯) [前者 N-2 人, 後者 N-3 人] : 不过没有讲他的方法 : 大家可以试着挑战看看 XD 可以做出 N-1 的解，不管知不知道猜对猜错 最後一人，也就是第 N 人，看到前 N-1 人头上帽子的数字， 假设第 i 人的帽子颜色是 a_i 造出一个 permutation π: [N+1]→[N+1] 使得 π(i)=a_i, i=1,2,...,N-1 且 π 为偶排列。 第 N 人就猜 π(N) 即可，他可能会挂掉。 但接下来的人，都可以依据必须是偶排列这件事， 猜对自己头上帽子的数字。 页末防雷 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.230.45 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1460851646.A.715.html ※ 编辑: arthurduh1 (140.112.230.45), 04/17/2016 08:07:57