YLL討論網

話說從前有100個農夫犯了死罪,國王要將他們全部處死!!!
但是國王行刑的方式很特別,他把農夫排成一直線,全部向前看,然後國王會在每人頭上戴一頂帽子, 帽的顏色是紅, 黃或者綠的...

由於100人排成直線,排最後的那個人可以看到前面全部99人的帽的顏色,倒數第二那個就可以看到前面98人的帽子的顏色,如此類推,.而第二人只能看到第一人的帽子的顏色.第一人就什麼也看不到, 而這國王要農夫們逐個猜自己頭上帽子的顏色,.猜中就不用死,.答錯便會被殺, 然後下一個答...
而農夫只准許說一個字的答案: "紅", "黃"或者 "綠" ,若有人說其他任何形式的答案的話就100人全部都要死!!!!

農夫們希望將犧牲的人數減到最少,於是向國王提議讓他們自己商量一陣,
國王認為這些農夫再怎麼討論都不會有什麼結果, 於是就答應他們...還答應讓農夫們自己決定回答的次序,.等農夫們商量完, 排成直線之後, 把帽子戴上在他們頭上...然後開始回答...

請問農夫們最好的方案是什麼?

asmobia 寫到:

 

我目前想到的方法是從最後一個人( 第一百人, 就是那個看得見所有其他人的人 )開始; 所有偶數號的人( 第一百, 第九十八, 第九十六... ), 報出他前一個人( 第九十九, 第九十七, 第九十五 )的顏色; 而所有奇數號的人, 就照著她背後的人的指示脫困.

 

這樣算來, 全部一百人可以分成兩類:

"一定活":   奇數號的五十人肯定獲釋;

"幫別人":   偶數號的五十人有三分之一的機會矇對;

 

期望值是:

50 + 50/3 = 66.66..

 

題目的理解是:
1. 除了紅, 黃, 綠三個單字, 不可以有其他的答案或資訊傳遞, 並且只能回答一個.
2. 答錯了自己被殺, 答對了自己獲釋.
3. 一個人的答案, 以及其結果是答對還是答錯, 當場即時知道 其他人都也聽的到.
4. 每個人不是自私的, 為了最多人獲釋, 有人願意犧牲.
5. 各色帽子的數量沒有上限, 比如說, 可能所有帽子都是紅色.


農夫商量的答題原則:
1.如果知道自己帽子的顏色, 先自保, 答出正確答案. 如果不知道自己帽子的顏色, 盡力提示前面的人, 也就是說出前面人帽子的顏色.
2.從最後1人開始向前, 以提示前面最多連續顏色的帽子為最優先策略. 也就是說: 排在Y位置的人, 如果前面是2個以上連續顏色的帽子, 比方說是5個連續紅色, 而在他更前方, 沒有比5個連續顏色更多時, 他就回答紅. 如果在他更前方, 有比5個連續顏色更多時, 比方說7個, 他這一輪就不回答.
3.當後面人提示了我帽子顏色, 就可以在這輪準備回答(所提示顏色). 但請稍微等待3秒鐘, 如果3秒後, 後面沒有人回答, 我就可以回答.
4.回答過的人, 不論對錯, 農夫們就必須把他排除在策略計算之外.
5.每一個人都需警覺: 如果在他更前方連續顏色更多者都已回答, 也就是說, 在尚未回答者隊伍中, 他的更前方, 已沒有比5個連續顏色更多, 他必須即時(3秒內)回答(提示), 以解救前方連續顏色的第8人(顏色已不正確).
6.當更前方沒有比我正前方連續顏色更多時, 就是我該回答的時機.

由於答對的期望值與帽子顏色的分配有關, 計算太複雜, 無法提出精算值. 但這個策略的期望值, 應該>50 + 50/3 = 66.66策略.

呵呵,不是很明白p大大的答案,不過答案是不對的
你好像誤解了題意---最後面的人先回答,才到前面的人回答,一個一個接下去!

piny大大的話有矛盾!

"那還不如每個人都唸出前一個的帽子顏色，而1-99號則依後面的指示說出正確顏色'

跟本不可能唸出前一個的帽子顏色又可以說出正確顏色,
除非好運有連續的顏色

題意是說...
看到99頂帽子的人先答
什麼都看不到的人是最後一個嗎?

回aaadfg﹕是的

可以拉長音嗎...
例如:紅,紅~,紅~~
短音代表紅,介於中間的代表黃,長音代表綠之類的
利用長短音來告訴前面那一個人的顏色...
這樣可以保證救到99個人
有點作弊的感覺...= =
(殘忍的國王呀...)

應該不可以吧,雖然題目沒說明清楚
不過的確很像作弊(這樣也給你想到,雖然不是答案xD~~)

目前只想到一般大家會想到方法:
基數順序的人回答前面的人的帽子的顏色
而偶數的人則是照著上一個人所說的顏色回答
這麼一來至少有50個人得救
期望值=50+50/3=66.666

將六個連續的人分為一組, 最後面的一人為犧牲者一號, 他前面的是犧牲者二號,
再前面的是獲救者一號, 獲救者二號, 獲救者三號與獲救者四號.
獲救者四號由於站在最前面, 所以看不見其他五個人;
犧牲者一號站在最後面所以看得到另外五個人.
犧牲者提供情報, 獲救者利用情報脫困.

狀況A:
四個獲救者都是同一個顏色(比如說"紅").

犧牲者的情報A:
兩個犧牲者都報告那個顏色("紅").

獲救者的動作A:
獲救者一號看見前面三個都是"紅", 所以他喊"紅".
獲救者二號看見前面兩個都是"紅", 又聽見後面喊"紅", 所以他也喊"紅".
獲救者三號看見前面是"紅", 又聽見後面兩個都喊"紅", 所以他也喊"紅".
獲救者四號聽見後面三個都喊"紅", 所以他也喊"紅".

結論A:
我們可以處理只有一種顏色的情形.

 

 

 

狀況B:
四個獲救者一共有三種顏色,其中必有一色且唯有一色出現兩次(比如說"紅").

犧牲者的情報B:
兩個犧牲者都報告那個出現兩次的顏色("紅").

獲救者的動作B:
***********************************************************
由於情報B與情報A是一樣的(都是紅色), 所以要分清這是四個人同一顏色;
還是四個人有三種顏色, 紅色出現兩次.

假設某一個獲救者知道現在不是四人都紅色, 而是四人有三色, 紅色兩次的話.
依據他眼前看到的與背後聽來的其他三筆資料, 他一定算的出自己是什麼.

獲救者一號肯定看見前面有兩個顏色以上,
所以他知道這不是四人同一色, 而是四人三色, 紅色兩次.

獲救者二號可能看見前面有兩個顏色以上,
那他就知道這不是四人同一色, 而是四人三色, 紅色兩次.

獲救者二號也可能看見前面兩個都是"紅",但是這樣的話獲救者一號絕對不是猜紅;
所以獲救者二號仍然知道這不是四人同一色, 而是四人三色, 紅色兩次.

獲救者三號若是聽見先前有人不猜紅,
那他就知道這不是四人同一色, 而是四人三色, 紅色兩次.

獲救者三號若是聽見先前兩人都猜紅, 那他面前看到的帽子肯定不是紅.
所以獲救者三號仍然知道這不是四人同一色, 而是四人三色, 紅色兩次.

獲救者四號肯定聽見前面的猜測有兩個顏色以上,
所以他知道這不是四人同一色, 而是四人三色, 紅色兩次.

由於大家都知道現在不是四人同一色, 而是四人三色, 紅色兩次;
所以依據大家眼前看到的與背後聽來的其他三筆資料, 大家一定算的出自己是什麼.
***********************************************************

結論B:
我們可以處理有三種顏色的情形.

 

歸結A與B, 我們想出"方案甲":
兩個犧牲者都報出"同樣"的答案時, 代表四個人會有一種顏色或三種顏色.
兩個犧牲者報出"不同"的答案時, 代表四個人會有兩種顏色.

 

 

狀況C:
四個獲救者有兩種顏色,兩種顏色出現次數可能為3:1或是2:2(比如說"紅":"黃")

 

犧牲者的情報C:
若是3:1, 則第一號犧牲者報告出現三次的那色(比如說"紅");
第二號犧牲者報告出現一次的那色(比如說"黃").

若是2:2, 則第一號犧牲者報告"沒有"出現的那色(比如說"綠");
第二號犧牲者報告有出現但"不是"第一號獲救者的顏色.

 

獲救者的動作C:
***********************************************************
只要知道是3:1還是2:2, 任一獲救者就可以依據背後聽到與眼前看見的三筆資訊算出自己的顏色.

我們知道, 要真的是2:2, 獲救者一號是絕對不會選第一號犧牲者的報告的(因為那色沒有出現!!)
獲救者一號也是絕對不會選第二號犧牲者的報告的(因為那是故意自殺!!)
所以只要獲救者一號選的是兩個犧牲者都沒有報出的顏色, 那大家都知道這是2:2;
不然就是3:1.

接下來再看獲救者一號會不會選錯?

若是獲救者一號看見前面三人只有一種顏色, 那他就知道是3:1而不是四人同色(請看方案甲).
若是獲救者一號看見前面有兩種顏色, 首先他知道這不是四個人有三種顏色(請看方案甲).
接下來他要看看第一號犧牲者報的顏色出現了沒; 若沒有, 那就是2:2, 不然就是3:1.

所以獲救者一號無論如何不會選錯.
也就是說,大家一定都知道這是3:1或是2:2.

若是3:1, 那犧牲者一號報的顏色出現三次, 犧牲者二號報的顏色出現一次;
大家都可以因此算得出自己的顏色.
若是2:2, 那兩個犧牲者都"沒"報出的顏色是獲救者一號與另一人的顏色.
而犧牲者二號所報出的顏色是剩下兩個人的顏色; 大家都算得出自己的顏色.
***********************************************************

結論C:
我們可以處理有兩種顏色的情形.

 

 

大結論:
若是兩個犧牲者報的顏色一樣, 那不是四人都同色就是四人有三色(其中有一色出現兩次).
第一號獲救者看得到前面三人.
第二號獲救者看得到前面兩人, 聽到後面一人.
第三號獲救者看得到前面一人, 聽到後面兩人.
第四號獲救者聽得到後面三人.
無論如何每人都有三筆資訊, 不會搞錯.

若是兩個犧牲者報的顏色不一樣, 那全部只有兩色( 3:1 或 2:2 ).
若是第一號獲救者猜的是兩個犧牲者都沒题到的, 那就是 2:2
不然就是 3:1.
每人仍然是看到加聽到共有三筆資訊, 不會搞錯.
故六個人中必有四人過關.

100/6 = 16餘4 ( 共十六組"六個人", 外加四個人剩下 )
剩下的四個人, 讓偶數號的人掩護奇數號的人, 故犧牲兩個, 獲救兩個.
16*4 + 2 = 66

所以肯定獲救的有 66 人, 剩下 34 人有 1/3 的矇對機會.
66 + ( 34/3 ) = 77.33
答: 66人肯定獲救, 期望值 77.33 人

 

無解= ="(個人認為啦...)


題目並沒有給他一個明確的提示= ="

就是規律....

沒有規律就算你怎麼推算他都可以改變= ="

比如：3人一組........當你測到犧牲者已經掛掉五組了...(和三個數字可以排成六種排列是一樣的..) 你得到的答案是紅.綠.黃(比如而已...)


可是國王並沒有說他是依一定規律排列.....

所以你能保證第六組就是紅綠黃???

只能隨機亂掰摟~.~

還答應讓農夫們自己決定回答的次序,.等農夫們商量完, 排成直線之後, 把帽子戴上在他們頭上...然後開始回答...

super king 寫到:呵呵,不是很明白p大大的答案,不過答案是不對的
你好像誤解了題意---最後面的人先回答,才到前面的人回答,一個一個接下去!

你在頂樓的題目中, 不是說:

“於是就答應他們...還答應讓農夫們自己決定回答的次序”

 

我同意P的說法.........


你的題目這個矛盾很大= ="


我的結果還是一樣=="(跟P不同..)


無解...

沒有規律根本找不出來...


PS.P你隱形吼...XD被我抓到了哈哈!!

由於100人排成直線,排最後的那個人可以看到前面全部99人的帽的顏色,倒數第二那個就可以看到前面98人的帽子的顏色,如此類推,.而第二人只能看到第一人的帽子的顏色.第一人就什麼也看不到, 而這國王要農夫們“”“逐個”“”“猜自己頭上帽子的顏色,.猜中就不用死,.答錯便會被殺, 然後下一個答...

“於是就答應他們...還答應讓農夫們自己決定回答的次序”

我覺得問題沒有矛盾!只是看起來容易另人誤解!
前面的那段可以說明最後面的人回答先,然後逐個回答
讓她們決定次序是應該決定要誰犧牲吧!!

Super king, 你在瞎掰喔!
前一段描述, 是國王原本的規則; 後一段是國王讓步的規則. 語意清楚, 沒有模擬兩可.
題目定了, 你不可以任意竄改題意.

雖然最後一人所得到的資訊最多, 看起來應該最有資格首先回答. 但是資訊愈多, 有可能愈混淆. 以整體利害觀點, 不見得是第一回答的最佳人選.

我提出的動態決策法, 盡最大可能利用顏色分配連續的優點, 應該是強化樓二66.66人的好策略. 最差的情況就是全部沒有顏色連續, 而完全吻合後面一人提示前面一人(2n → 2n-1)的結果.

況且..........

你自己當然清楚= ="

要是讓路人來看我想沒看過這個題目的一樣會和我們誤解..

我不想筆戰...

這是事實罷了

可以開票...

讓大家看看是不是你的題目讓人誤解...

呃...大家用辭別太激動...

基本上以我的觀點...
國王要求要一個一個依序回答
只有兩種選擇...
可能是由前到後or由後到前
"農夫可以自行決定回答順序"
意思是不一定一號農夫一定要排在第一個位置
可以排在第二第三第五十......沒有限制(我覺得這項有跟沒有是一樣的)

以上是小弟個人拙見...至少我解題時是這樣解的...