※ 引述《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/m.aspx?n=bbs/puzzle/M.1460851646.A.715.html ※ 編輯: arthurduh1 (140.112.230.45), 04/17/2016 08:07:57