YLL討論網

由 **小小軒** 於星期三三月 14, 2007 9:22 pm

#ed_op#DIV#ed_cl#那這樣第一個猜的人真可憐要把前面99人的帽子顏色總合加起來#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#加個半死之後他也只有1/3活命的機會= =#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#如果我是那個農夫就不會那麼閒了..呵呵#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl#

由 **aaddfg** 於星期四三月 01, 2007 10:50 pm

要恭喜所有有回覆的人吧....
靈感都是從他們那裡偷來的^^"

跟大家寫這題的感覺真的很好
尤其是看到期望值由66.67一直攀升到99.33...
大家一起腦力激盪
一方面互相幫助,一方面互相較競
好久沒有這種感覺了~~

由 **super king** 於星期四三月 01, 2007 10:29 pm

想不到有將多回復,因為我最近忙,沒什麼時間看清楚你們的答案
不過答案是99.33!!
算法最主要是三進位(看多少種顏色而定)
我的答案如下:
方法是由排最後一個的農夫回答...再來倒數第二個....等等等等.....最後回答的是排第一位的....
這問題的解法可以推廣至無限多人(任意N個)...無限多種帽子的顏色...永遠保證救到N-1個人....

就先以三種顏色...紅,黃,綠...和四個農夫 ( 這樣比較好懂...)

首先為任意三種顏色各設一個值
紅=0
黃=1
綠=2
(細心的讀者應該可以看出這是三進位的數值...如果今天有四種不同顏色...那就會是四進位"0,1,2,3"代入各一種顏色...)

在帽子戴上以後...每個農夫都要算出他前面看的到的帽子顏色的數字加總 (用三進位)
然後記得加總的最後一位數...再以顏色的方式報給前面的...

例:
[農夫]　甲　乙　丙　丁　
[帽子]　黃　綠　黃　紅　
[數值]　１　２　１　０　
甲乙丙丁，四人...由農夫丁在排最後一位先說話 (他有1/3的活命機會...)

丁看的到的是甲乙丙三人的帽子顏色...分別為黃+綠+黃...所以他就算1+2+1=4
4在三進位的表示是"11"...只看 "11" 最後一碼...也就是1...對應的是黃色...所以他回答 "黃"!

運氣背的農夫丁被砍頭後, 輪到農夫丙回答...丙看的到的是甲乙兩人的帽子顏色....
黃+綠=1+2=3
(三進位中 3 = "10", 只看"10" 最後一碼...也就是0...)

可是剛剛被砍頭的農夫丁有回答黃...

所以丙就推算:
甲＋乙　　＝０                        (農夫丙算他前面的人的尾碼加總)
甲＋乙＋丙＝１                        (農夫丁死前報的 "黃!"...相對應尾碼１)

所以...
０＋丙＝１
丙＝１

丙頭上的帽子＝１, 或者作黃色...

現在丙正確地回答 "黃" 以後(國王信守諾言的話...他平安地被釋放)...輪到農夫乙說話...

乙的推算:
甲　　　　＝１                        (農夫乙自己算的...只剩前面一個甲...算起來也沒啥難)
丙　　　　＝１                        (安全過關的丙的回答)
甲＋乙＋丙＝１                        (農夫丁死前報的 "黃!"...相對應尾碼１)

所以...
１＋乙＋１＝１
乙＝２

乙頭上的帽子＝２, 也就是綠色...
(記得都是三進位的運算...只看最後一碼...進位的數字通通不要管)

剩下甲...

丙　　　　＝１
乙　　　　＝２
甲＋乙＋丙＝１

所以...
甲＋２＋１＝１
甲＝１ (黃)

以此類推...五個農夫的時候...或六個七個八個...(用簡單的數學歸納法可證農夫數目可以不斷加上去...沒有限制)
若四種不同顏色的帽子的話就用四進位...也可以多到無限多...反正一種顏色對應一個 "個位數字" 的數值...

只是...越後面回答的人..就要把之前每個農夫的回答通通記住...  ...如...一千人的話...最後一個回答的農夫要記住之前999人的回答....只是理論上可行的 !
恭喜aaadfg答對!

由 **G@ry** 於星期四三月 01, 2007 6:56 pm

小弟其實初到貴境...#ed_op#br#ed_cl#不過看到大家這麼熱烈地研究出這麼驚人的成績實在興奮之極....#ed_op#br#ed_cl#66.666=> 99.333 超強....#ed_op#br#ed_cl#小弟其實不想沾任何水(便宜)....#ed_op#br#ed_cl#不過......如果要看著表(農夫未必很會計數)才能對出數來....好像仍然頗困難.....小弟不才....嘗試簡化一下記&算的方法....大家看看可行嗎？...#ed_op#br#ed_cl##ed_op#br#ed_cl##ed_op#br#ed_cl#1. 既然紅綠黃中大家都只用紅色和綠色來記認，不如把站在最尾犧牲的人發出的代號安排如下：#ed_op#br#ed_cl#紅：紅比綠少1：R0G1, R1G2, R2G0;  2>1>0>2....#ed_op#br#ed_cl#綠：綠比紅少1：R1G0, R2G1, R0G2;  2>1>0>2....#ed_op#br#ed_cl#黃：紅綠一樣多：R0G0, R1G1, R2G2#ed_op#br#ed_cl#   由於總數有98人, 所以簡易地設代號只有兩個1，再把黃色位加上去：#ed_op#br#ed_cl#最後記法：紅：取R0G1 => 011, 綠：取R1G0=>101, 黃：取R1G1=> 110#ed_op#br#ed_cl#即是：#ed_op#span style="font-weight: bold;"#ed_cl#「代號那一個零那一個」-R:011, G:101, Y:110#ed_op#/span#ed_cl##ed_op#br#ed_cl#就是，犧牲的人叫「紅」所有人就記著「011」便行 (算法後續)#ed_op#br#ed_cl#這樣的代表法比較容易記#ed_op#br#ed_cl##ed_op#br#ed_cl#2. 所有人都只需記著一個3位的代號便行：000, 001, 002, 010, ... ,221,  222#ed_op#br#ed_cl#(記多錯多...只要記得這最重要的3位數字便行...要知道所有你看到的人也是等著你正確的顏色代號才能活下去的...你的一次錯誤會令至少多一位同伴死亡)#ed_op#br#ed_cl#每當有人叫顏色便把那個位的數字減去一  2>1>0>2>1...#ed_op#br#ed_cl#e.g.　紅　紅　黃　綠　黃　黃　綠　紅　黃　紅...#ed_op#br#ed_cl#010->210 110 112 102 101 100 120 020 022 222...#ed_op#br#ed_cl#容易吧....#ed_op#br#ed_cl##ed_op#br#ed_cl#3. 好了到自己的回合了，把自己現在所得的代號唸三遍(當然是在心裏唸呀！唸出聲就大家也死定了!!!!!!!!!)現在才去計算一下你面前的人的帽子代號：#ed_op#br#ed_cl#e.g. 4R8G2Y => 482 => 122    這個忘了不要緊...你可以再數過....#ed_op#br#ed_cl#但你還記得剛才唸了三遍的代號嗎？...這個你可不要忘了....剛剛才唸了三遍...不會忘了吧～～....現在你有兩個代號.......到了對比的重要時刻了～～～.....#ed_op#br#ed_cl##ed_op#br#ed_cl#4. 過了這一關你就沒事了...很緊張吧...不要緊...對比是非常簡單的：#ed_op#br#ed_cl#假設你剛巧兩個數字當中只有一個位不同而且是相差1的，恭喜，你只需要吧該位置代表的顏色叫出來便行了！... e.g. 101, 111 大叫「綠」; 210, 010 大叫「紅」....#ed_op#br#ed_cl#假如你剛剛不巧，兩個數字風馬牛不相及：e.g. 121, 000; 022, 111, e.t.c....#ed_op#br#ed_cl#不要緊，你只需要將其中一個數字中所有位也加上1, 如果還是不行，再加多1便行了...放心，只有一個組合是相差一個位的：e.g. 121->202->010 :: 000=>綠#ed_op#br#ed_cl#e.g.2: 022->100->211 :: 111=>紅#ed_op#br#ed_cl##ed_op#br#ed_cl##ed_op#br#ed_cl#5. 還有...#ed_op#br#ed_cl#還有甚麼嗎？...沒了，就是完了....非常簡單的系統吧.... ^^#ed_op#br#ed_cl##ed_op#br#ed_cl##ed_op#br style="font-weight: bold;"#ed_cl##ed_op#span style="font-weight: bold;"#ed_cl#資料來源：#ed_op#/span#ed_cl##ed_op#br#ed_cl##ed_op#span id="convert155372"#ed_cl##ed_op#span class="postbody"#ed_cl#aaddfg#ed_op#br#ed_cl##ed_op#/span#ed_cl##ed_op#/span#ed_cl##ed_op#span id="convert155372"#ed_cl##ed_op#span class="postbody"#ed_cl#asmobia#ed_op#br#ed_cl#Dr. p#ed_op#br#ed_cl#排名絕對跟字母先後....#ed_op#br#ed_cl##ed_op#br#ed_cl##ed_op#br#ed_cl#以上純粹上述帖子之資料整理與應用，內容與本人完全無關；版權所有，往#ed_op#span style="font-weight: bold;"#ed_cl#資料來源#ed_op#/span#ed_cl#查究#ed_op#br#ed_cl##ed_op#br#ed_cl##ed_op#font size="1"#ed_cl#....不關我的事....#ed_op#/font#ed_cl##ed_op#/span#ed_cl##ed_op#/span#ed_cl##ed_op#br#ed_cl#

由 **asmobia** 於星期四三月 01, 2007 2:45 pm

#ed_op#DIV#ed_cl#aaddfg 的一張餘數關係表就破解了本題; #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#演算法的強弱除了效能以外, 還包括簡潔度呀! 這個解答真是一個範本.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#樓主是不是可以宣告 aaddfg 的解答為正解了?#ed_op#/DIV#ed_cl#

由 p 於星期四三月 01, 2007 10:42 am

致asmobia&aaddfg兩人:
強!
你們救了99人.
依p的驗算, aaddfg的方法應該是正確的.

這一題, 值得放入資訊理論中, 作為經典範例.

由 **aaddfg** 於星期三二月 28, 2007 11:51 pm

OK...繼續上文
若是"紅紅"
則第98人可以知道第99人看到的是Ｒ０Ｇ１或Ｒ１Ｇ２或Ｒ２Ｇ０
則又可以依照上面"第一個人喊綠"的情況下去解
若是"黃黃"
則第98人可以知道第99人看到的是Ｒ１Ｇ０或Ｒ２Ｇ１或Ｒ０Ｇ２
還是可以依照上面"第一個人喊黃"的情況下去解.....
依此類推
都是這幾個在循環
如此一來
期望值可以高達99.333........
應該...不可能有更高的了...

由 **aaddfg** 於星期三二月 28, 2007 11:45 pm

大激動...
首先...我知道98.667很厲害....
不過剛剛再度借了asmobia的想法
這次只犧牲一個人!!
(不知道成不成功...還沒完全檢驗)
(底下Ｒ１代表紅色除以3餘1,Ｇ０代表綠色除以3餘0...以此類推)
第一個人喊紅代表Ｒ１Ｇ１或Ｒ２Ｒ２或Ｒ０Ｇ０
第99人看到可能的情況：
第９９人是紅色　Ｒ０Ｇ１　Ｒ１Ｇ２　Ｒ２Ｇ０
第９９人是綠色　Ｒ１Ｇ０　Ｒ２Ｇ１　Ｒ０Ｇ２
第９９人是黃色　Ｒ１Ｇ１　Ｒ２Ｇ２　Ｒ０Ｇ０
由此可以判斷...原因等一下再講...先把所有的寫完
第一個人喊綠代表Ｒ１Ｇ２　Ｒ２Ｇ０　Ｒ０Ｇ１
第９９人是紅色　Ｒ０Ｇ２　Ｒ１Ｇ０　Ｒ２Ｇ１
第９９人是綠色　Ｒ１Ｇ１　Ｒ２Ｇ２　Ｒ０Ｇ０
第９９人是黃色　Ｒ１Ｇ２　Ｒ２Ｇ０　Ｒ０Ｇ１

第一個人喊黃代表Ｒ１Ｇ０　Ｒ２Ｇ１　Ｒ０Ｇ２
第９９人是紅色　Ｒ０Ｇ０　Ｒ１Ｇ１　Ｒ２Ｇ２
第９９人是綠色　Ｒ１Ｇ２　Ｒ２Ｇ０　Ｒ０Ｇ１
第９９人是黃色　Ｒ１Ｇ０　Ｒ２Ｇ１　Ｒ０Ｇ２
先發文...等一下再發一文解釋....
快速回覆欄太小沒辦法看全部很辛苦...XD

由 **asmobia** 於星期三二月 28, 2007 10:41 pm

#ed_op#DIV#ed_cl#定理A:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#已知一個農夫可以看到他前面所有的人, 也可以聽到他背後所有的人的回答.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若他背後所有人的回答皆正確的話, 則該農夫就知道除了他以外所有人的狀況.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#定理B:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若一農夫知道了除了他以外所有人的狀況, 同時又知道三種顏色各出現多少次;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#那他就可以推測出自己帽子的顏色.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#定理C:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#假設一農夫知道了除了他以外所有人的狀況, 在該狀況中;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#令( 紅, 綠, 黃 )三個顏色出現次數各為( R, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#那包括該農夫自己, 紅, 綠, 黃三個顏色出現次數可能為:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#( R+1, G, Y ), ( R, G+1, Y ) 或 ( R, G, Y+1 ) 其中之一.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#本次解法試圖犧牲最後兩個農夫, 以挽救其他九十八個農夫.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設前面九十八個人裡有偶數個紅色, 則第一百個人猜紅.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#假設前面九十八個人裡有奇數個紅色, 則第一百個人猜綠.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#假設前面九十八個人裡有偶數個綠色, 則第九十九個人猜紅.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#假設前面九十八個人裡有奇數個綠色, 則第九十九個人猜綠.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#也就是說:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#"紅紅" => 紅色與綠色出現次數都是偶數#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#"紅綠" => 紅色出現次數是偶數, 綠色出現次數是奇數#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#"綠紅" => 紅色出現次數是奇數, 綠色出現次數是偶數#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#"綠綠" => 紅色與綠色出現次數都是奇數#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#首先假設一個農夫他所聽到的背後所有人的回答都是正確的.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據定理A, 他能夠知道除了他自己以外所有人的狀況;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假定在該狀況中, 三個顏色( 紅, 綠, 黃 )的分配為( R, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#則依據定理C, 包括該農夫自己, 三個顏色( 紅, 綠, 黃 )的出現次數可能為:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#( R+1, G, Y ) , ( R, G+1, Y ) 或 ( R, G, Y+1 ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#又經由最後兩位農夫的犧牲, 大家知道紅與綠的出現次數是奇數還是偶數.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#將這個奇偶性質和上文中的 R 與 G 作比較:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若是 R 的奇偶性質不符合兩位犧牲者的情報, 那包括該農夫自己, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#三個顏色( 紅, 綠, 黃 )出現次數應是( R+1, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#若是 G 的奇偶性質不符合兩位犧牲者的情報, 那包括該農夫自己, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#三個顏色( 紅, 綠, 黃 )出現次數應是( R, G+1, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#若是 R 與 G 的奇偶性質都符合兩位犧牲者的情報, 那包括該農夫自己, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#三個顏色( 紅, 綠, 黃 )出現次數應是( R, G, Y+1 ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#總而言之每個人都可以算出全部九十八人中, 三種顏色的出現次數;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#進而利用定理B算出自己帽子的顏色.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#然而我之前有假設"一個農夫他所聽到的背後所有人的回答都是正確的" 這話.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#現在看看這個假設是否成立.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#首先, 第九十八人看的見其他所有人,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以算得出除了自己以外的( R, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#再由奇偶性質求出全體三種顏色的正解, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#進而利用定理B算出自己帽子的顏色, 回答出正確答案.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若以上為真, 那第九十七人所聽到的背後所有人的回答都是正確的,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#所以算得出除了自己以外的( R, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#再由奇偶性質求出全體三種顏色的正解, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#進而利用定理B算出自己帽子的顏色, 回答出正確答案.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#若以上為真, 那第九十六人所聽到的背後所有人的回答都是正確的,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#所以算得出除了自己以外的( R, G, Y ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#再由奇偶性質求出全體三種顏色的正解, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#進而利用定理B算出自己帽子的顏色, 回答出正確答案.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#..........................以下循環.....................#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#<正式的證明請用數學歸納法格式>#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#答: 確定九十八人獲救, 另兩人有三分之一的機會矇對.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#      期望值為 98 + 2/3 = 98.66666#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl#

由 p 於星期三二月 28, 2007 9:08 pm

承asmobia, 犧牲5個農夫,造福95人.

以N代表紅色
以 M代表綠色
N + M <= 95
令 P = 2 * N + M, 則 P <= 190
5個三進位bit, 3^5=243 即足夠表示190

第95人計算前面94人的帽子顏色紅色有 e個, 綠色有 f 個黃色有 g 個
如果2*e+f=p 則為黃色
如果2*e+f=p-1 則為綠色
如果2*e+f=p-2 則為紅色

由 p 於星期三二月 28, 2007 7:22 pm

asmobia&aaddfg 太厲害了,
能夠想到, 使用三進位來表達顏色總數.
佩服佩服, 我的動態決策法瞠乎其後.
尤其這"93 + 7/3 = 95.333333" 太厲害了. 用三進位法我還只想得到用8人造福92人的方法.

由 **asmobia** 於星期三二月 28, 2007 5:24 pm

#ed_op#DIV#ed_cl#定理甲:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#如果知道每種顏色有幾個,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#那麼農夫們可以從隊伍的最後一個開始猜, 猜完再換前一個人猜, 最後是全活. #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#如果對於以上敘述有疑問, 請參照20~21樓拙作.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以關鍵是農夫們要犧牲幾個人來打信號, 讓其他農夫知道每種顏色有幾個.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#現在再來看一個衍伸的定理乙:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#"對隊伍中的一個農夫而言, 要是他背後所有人的答案都是正確的,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#那他就算不知道每個顏色有幾個, 他對每個顏色數量的猜測誤差值最多只有1"#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#這個定理乙簡直不必證明; 請看下面:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若是我背後所有人的答案都是正確的, 那等於我回頭看了嘛!#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我回頭看看, 再向前看看, 唯一看不到的就是自己;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以若硬是叫我猜每種顏色共有幾個, 誤差值最多是1, 我自己.#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#這次的計畫是打算犧牲七個農夫, 利用 aaddfg 的演算法造福剩下九十三個人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設九十三人中紅色有 N 個, 綠色有 M 個;  N + M < 93 且 N 與 M 均為非負整數.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#令 P = 10 * N + M 則 0 <= P <= 930#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我打算用那七個犧牲者來表示出 P; #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#每一個犧牲者代表三進位的數字中的一位, 足夠表達 0 到 1000 的所有整數.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#後面的九十三位獲救者可以依據前面七人的回答算出 P 值.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#但是知道 P 值不代表知道 N 與 M, 而只是知道幾組可能的( N#ed_op#SUB#ed_cl#i #ed_op#/SUB#ed_cl#, M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl# ).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以後面的九十三人要猜想一個合理的 N#ed_op#SUB#ed_cl#i #ed_op#/SUB#ed_cl# 與 M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl#,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#然而, 任意兩個 M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl# 值的差距至少是 10, 依據定理乙:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#**************************************************#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#對隊伍中的一個農夫而言, 要是他背後所有人的答案都是正確的,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#那他就算不知道每個顏色有幾個, 他對每個顏色數量的猜測誤差值最多只有1.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#**************************************************#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以該農夫一定能夠選出正確的 M, 並求出 N.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#當然, 我們要假定"背後所有人的答案都是正確的", 這可以簡單證明:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#首先, 第九十三人看的見前面所有九十二個人, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以第九十三人對顏色的猜測誤差值最多只有1;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#又因為任意兩個 M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl# 值的差距至少是 10, 所以他一定會猜對M.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#猜對M就猜出N, 也就知道紅色與綠色的數量, 同時可以算出黃色的數量.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據定理甲, 第九十三人必能答出自己的顏色.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若是以上敘述為真, 那第九十二個人的背後所有人的答案都是正確的, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以第九十二個人對顏色的猜測誤差值最多只有1;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#又因為任意兩個 M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl# 值的差距至少是 10, 所以他一定會猜對M.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#猜對M就猜出N, 也就知道紅色與綠色的數量, 同時可以算出黃色的數量.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據定理甲, 第九十二人必能答出自己的顏色.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#若是以上敘述為真, 那第九十一個人的背後所有人的答案都是正確的, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#所以第九十一個人對顏色的猜測誤差值最多只有1;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#又因為任意兩個 M#ed_op#SUB#ed_cl#i#ed_op#/SUB#ed_cl# 值的差距至少是 10, 所以他一定會猜對M.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#猜對M就猜出N, 也就知道紅色與綠色的數量, 同時可以算出黃色的數量.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據定理甲, 第九十一人必能答出自己的顏色.#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#...........#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#想寫的專業一點就用數學歸納法吧!#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#總而言之, 所有九十三人都能由 P 值算出正確的 M, 進而算出 N.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#知道了紅色與綠色的數量, 黃色也算出來了.#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#依據定理甲, 所有人都活了.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#答: 確定 93 人, 期望值 93 + 7/3 = 95.333333#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl#

由 **super king** 於星期三二月 28, 2007 4:09 pm

抱歉,asmobia的答案是否在說農夫在戴帽子前知道什麼顏色一共有多少個帽子?
可是題目沒說明啊...

由 **asmobia** 於星期三二月 28, 2007 4:05 pm

aaddfg 寫到:這個想法是從asmobia改過來的...#ed_op#BR#ed_cl#根據asmobia的說法#ed_op#BR#ed_cl#"如果 x 個農夫知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽,#ed_op#BR#ed_cl#那他們從隊伍最末一個人開始猜自己的顏色, 猜完再讓前一個人猜,#ed_op#BR#ed_cl#最後的下場是人人都獲救."#ed_op#BR#ed_cl#所以我讓前面13位農夫當犧牲者#ed_op#BR#ed_cl#讓他們算出另外87位農夫有幾頂紅帽幾頂黃帽幾頂綠帽#ed_op#BR#ed_cl#將頂數擺在一起成一個六位數#ed_op#BR#ed_cl#再把這個六位數轉成三進制有13位#ed_op#BR#ed_cl#在約定好#ed_op#BR#ed_cl#紅代表0黃代表1綠代表2#ed_op#BR#ed_cl#用13個人說出來讓另外87個人知道#ed_op#BR#ed_cl#如此便可以讓那87位農夫知道他們有帽子各有幾頂了#ed_op#BR#ed_cl##ed_op#BR#ed_cl#例如71頂紅帽6頂黃帽10頂綠帽就成了#ed_op#BR#ed_cl#710610#ed_op#BR#ed_cl#再把這個數改為三進位#ed_op#BR#ed_cl#變成#ed_op#BR#ed_cl#1100002202220#ed_op#BR#ed_cl#13位....#ed_op#BR#ed_cl#如此期望值可以變成#ed_op#BR#ed_cl#87+13/3=91.33 #ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl#

#ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#aaddfg 偉大的想法! 這種文章不推不行!#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#但是其實只要四位數就夠了, #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#兩位數是紅色的數量, 兩位數是綠色的數量.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#黃色用減去法就知道了.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們犧牲九個人, 剩下九十一個人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#九十一個人所能造出最大的四位數是9100( 91個人通通紅色, 0個綠色).#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#9100的三進位是 110111001, 共九位, 所以我們需要九個犧牲者.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#犧牲者喊紅代表 2, 喊綠代表 1, 喊黃代表 0.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#九個犧牲者代表九個不同的位數....#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#91 + 9/3 = 94#ed_op#/DIV#ed_cl#

由 **super king** 於星期三二月 28, 2007 4:02 pm

回aaadfg大大:
此方法雖然很...
但只要理論上行得通就可以了
不用說擔心農夫可以把心算很難記得
還可以有更好的辦法噢!

由 **super king** 於星期三二月 28, 2007 3:54 pm

如果題意是p大大所說的,我就先說聲抱歉
因為我第一次看題目時,覺得最後面的人回答先,然後到下一位,而答案也確實是
如此是最後一個答先,然後到下一位回答!!!

由 **aaddfg** 於星期三二月 28, 2007 3:46 pm

不過這個方法很...
要用心算把十進制六位數改成三進制13位數還蠻難的...XD

由 **aaddfg** 於星期三二月 28, 2007 3:43 pm

這個想法是從asmobia改過來的...#ed_op#BR#ed_cl#根據asmobia的說法#ed_op#BR#ed_cl#"如果 x 個農夫知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽,#ed_op#BR#ed_cl#那他們從隊伍最末一個人開始猜自己的顏色, 猜完再讓前一個人猜,#ed_op#BR#ed_cl#最後的下場是人人都獲救."#ed_op#BR#ed_cl#所以我讓前面13位農夫當犧牲者#ed_op#BR#ed_cl#讓他們算出另外87位農夫有幾頂紅帽幾頂黃帽幾頂綠帽#ed_op#BR#ed_cl#將頂數擺在一起成一個六位數#ed_op#BR#ed_cl#再把這個六位數轉成三進制有13位#ed_op#BR#ed_cl#在約定好#ed_op#BR#ed_cl#紅代表0黃代表1綠代表2#ed_op#BR#ed_cl#用13個人說出來讓另外87個人知道#ed_op#BR#ed_cl#如此便可以讓那87位農夫知道他們有帽子各有幾頂了#ed_op#BR#ed_cl##ed_op#BR#ed_cl#例如71頂紅帽6頂黃帽10頂綠帽就成了#ed_op#BR#ed_cl#710610#ed_op#BR#ed_cl#再把這個數改為三進位#ed_op#BR#ed_cl#變成#ed_op#BR#ed_cl#1100002202220#ed_op#BR#ed_cl#13位....#ed_op#BR#ed_cl#如此期望值可以變成#ed_op#BR#ed_cl#87+13/3=91.33 #ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl#

由 **asmobia** 於星期三二月 28, 2007 2:55 pm

#ed_op#P#ed_cl#

p 寫到:#ed_op#/P#ed_cl##ed_op#P#ed_cl#我提出的動態決策法, 盡最大可能利用顏色分配連續的優點, 應該是強化樓二66.66人的好策略. #ed_op#/P#ed_cl##ed_op#P#ed_cl#

#ed_op#/P#ed_cl##ed_op#DIV#ed_cl#向 p 大報告: #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#小弟的版本一(樓二)是 50 + 50/3 = 66.66#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#DIV#ed_cl#小弟的版本二(樓12)是  66 + 34/3 = 77.33#ed_op#/DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#小弟的版本三(樓21)是 70 + 30/3 = 80#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#如果小弟的解法沒錯, 請 p 大的動態決策法能針對"版本三"作強化,#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#以免浪費時間.#ed_op#/DIV#ed_cl#

由 **asmobia** 於星期三二月 28, 2007 2:47 pm

#ed_op#DIV#ed_cl#前提:#ed_op#BR#ed_cl#連續 x 個農夫排成一隊, 每個農夫都看得見自己前面的所有的人, 也聽得到每個人的說話.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設:#ed_op#BR#ed_cl#每個農夫都知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#策略:#ed_op#BR#ed_cl#假設每個人都知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#BR#ed_cl#同時每個人都可以看見自己前方所有的人, 也可以聽見自己後方所有的回答;#ed_op#BR#ed_cl#所以對每一個農夫而言, 只要他後方的回答全部都是對的, 那他就可以推算出自己的顏色了.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們從隊伍中的最後一個人開始猜, 最後一個人能夠看到其他所有人, 所以他不會錯.#ed_op#BR#ed_cl#如果上一句為真, 對倒數第二人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#BR#ed_cl#如果上一句為真, 對倒數第三人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#BR#ed_cl#..........................................#ed_op#BR#ed_cl#如果上一句為真, 對倒數第 x 人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#結論甲:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#"如果 x 個農夫知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽,#ed_op#BR#ed_cl#那他們從隊伍最末一個人開始猜自己的顏色, 猜完再讓前一個人猜,#ed_op#BR#ed_cl#最後的下場是人人都獲救."#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#所以說, 我的想法是犧牲 n 個農夫, 用她們的回答來作暗號;#ed_op#BR#ed_cl#好讓接下來的 m 個農夫知道她們之間一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#BR#ed_cl#我稱那 n 個農夫為犧牲者, 那 m 個農夫為獲救者.#ed_op#BR#ed_cl#犧牲者在隊伍的後面, 所以她們看到的資訊比較多; 獲救者排在隊伍的前面.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設 n 為 3, 那麼這三個犧牲者一共可以產生五種暗號:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#三個全同 => 例: 紅紅紅#ed_op#BR#ed_cl#中間不同 => 例: 紅黃紅#ed_op#BR#ed_cl#尾巴不同 => 例: 紅紅黃#ed_op#BR#ed_cl#前頭不同 => 例: 黃紅紅#ed_op#BR#ed_cl#全不同     => 例: 紅黃綠#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設 m 為 7, 那麼這七個獲救者的帽子的各種顏色數量一共有八種組合:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#              顏色一  顏色二  顏色三  ( 下面數字為該顏色出現次數 )#ed_op#BR#ed_cl#-------------------------------------------------------------------------#ed_op#BR#ed_cl#組合一  7            0            0#ed_op#BR#ed_cl#組合二  6            1            0#ed_op#BR#ed_cl#組合三  5            2            0#ed_op#BR#ed_cl#組合四  5            1            1#ed_op#BR#ed_cl#組合五  4            3            0#ed_op#BR#ed_cl#組合六  4            2            1#ed_op#BR#ed_cl#組合七  3            3            1#ed_op#BR#ed_cl#組合八  3            2            2#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據結論甲的暗示, 我們要想方法用五種暗號來代表八種組合.#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#組合六( 4, 2, 1 )可以用"全不同"來代表.#ed_op#BR#ed_cl#組合七( 3, 3, 1 )可以用"尾巴不同"來代表.#ed_op#BR#ed_cl#組合八( 3, 2, 2 )可以用"前頭不同"來代表.#ed_op#BR#ed_cl#組合一( 7, 0, 0 )與組合四( 5, 1, 1 )可以用"三個全同"來代表.#ed_op#BR#ed_cl#組合二( 6, 1, 0 ),組合三( 5, 2, 0 )與組合五( 4, 3, 0 )可以用"中間不同"來代表.#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#1. 用"全不同"的暗號( 例:紅黃綠 )來處理組合六( 4, 2, 1 ): #ed_op#BR#ed_cl#最前面的( 例:紅 )出現四次, 中間的( 例:黃 )出現兩次, 最後面的( 例:綠 )出現一次.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#2. 用"尾巴不同"的暗號( 例:紅紅黃 )來處理組合七( 3, 3, 1 ): #ed_op#BR#ed_cl#最後面的( 例:黃 )代表出現一次的顏色, 前面兩個暗號是紅還是綠都沒差.#ed_op#BR#ed_cl#也就是說, "紅紅黃" 與 "綠綠黃" 是一樣的, 反正紅與綠都出現三次, 只有黃比較特別.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#3. 用"前頭不同"的暗號( 例:黃紅紅 )來處理組合八( 3, 2, 2 ): #ed_op#BR#ed_cl#最前面的( 例:黃 )代表出現三次的顏色, 後面兩個暗號是紅還是綠都沒差.#ed_op#BR#ed_cl#也就是說, "黃紅紅" 與 "黃綠綠" 是一樣的, 反正紅與綠都出現兩次, 只有黃比較特別.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#4. 用"三個全同"的暗號( 例:紅紅紅 )來處理組合一與組合四:#ed_op#BR#ed_cl#當然, "紅"代表組合一( 7, 0, 0 )裡的 7 或是組合四( 5, 1, 1 )裡的 5.#ed_op#BR#ed_cl#這裡有一個新問題是, 獲救的七個人要如何區分現在是組合一還是組合四?#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#其實不難; 組合四( 5, 1, 1 )裡有兩個不是紅色的帽子:#ed_op#BR#ed_cl#若妳本身是紅色的, 那妳肯定會看到不是紅色的帽子或是聽到不是紅色的回答;#ed_op#BR#ed_cl#若妳本身不是紅色, 妳也會看到另一個不是紅色的帽子或聽到另一個不是紅色的回答.#ed_op#BR#ed_cl#所以對每一個獲救者而言, 若是他看到與聽到的都是紅色, 那就是組合一.#ed_op#BR#ed_cl#不然, 他一定會看見或聽見一個以上不是紅色; 那就是組合四.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5. 用"中間不同"的暗號( 例:紅黃紅 )來處理組合二, 組合三與組合五:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#5.1. 先討論組合二( 6, 1, 0 )與組合五( 4, 3, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們用這三個暗號( 例:紅黃紅 )的頭尾( "紅" )代表多的那個顏色,#ed_op#BR#ed_cl#也就是組合二的 6 與組合五的 4.#ed_op#BR#ed_cl#然後用這三個暗號( 例:紅黃紅 )中間的暗號( "黃" )代表少的那個顏色,#ed_op#BR#ed_cl#也就是組合二的 1 與組合五的 3.#ed_op#BR#ed_cl#那獲救的七個人要如何區分現在是組合二還是組合五?#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#其實不難; 組合二裡只有一個"黃", 所以不可能有人看到加聽到超過一個"黃";#ed_op#BR#ed_cl#而組合五裡有三個黃, 所以就算自己是"黃", 也至少看到加聽到另外兩個"黃".#ed_op#BR#ed_cl#所以對每一個獲救者而言, 若是他看到與聽到的超過一個"黃", 那就是組合五.#ed_op#BR#ed_cl#不然就是組合二; #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5.2. 再討論組合三( 5, 2, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們用三個暗號( 例:紅黃紅 )的頭尾( "紅" )代表多的那個顏色,#ed_op#BR#ed_cl#也就是組合三的 5.#ed_op#BR#ed_cl#然後用三個暗號( 例:紅黃紅 )中間的暗號( "黃" )代表"沒出現"的那個顏色,#ed_op#BR#ed_cl#也就是組合三的 0.#ed_op#BR#ed_cl#請注意, 在這個例子裡, 暗號裡面沒有"綠", 但是綠色帽子有兩個( 組合三的 2 ),#ed_op#BR#ed_cl#所以就算自己的帽子是"綠", 自己也一定會向前看到或從後面聽到另一個"綠"色;#ed_op#BR#ed_cl#也就是說, 沒有人會"看不到也聽不到"綠色, 縱然暗號裡沒有"綠".#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5.3. 綜合討論組合二( 6, 1, 0 ),組合三( 5, 2, 0 )與組合五( 4, 3, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#當一個獲救者聽到 "中間不同" 的暗號( 例:紅黃紅 )時;#ed_op#BR#ed_cl#他首先看看那個三個暗號( 例:紅黃紅 )中都沒有提到的顏色( "綠" ),#ed_op#BR#ed_cl#有沒有出現在前面其他人的頭上或是背後的人的回答裡;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若是有, 那就是組合三( 5, 2, 0 ): 五紅二綠.#ed_op#BR#ed_cl#若是沒有, 那他要看看三個暗號( 例:紅黃紅 )中間的暗號( "黃" ),究竟出現了幾次;#ed_op#BR#ed_cl#若是超過一次, 那就是組合五( 4, 3, 0 ): 四紅三黃.#ed_op#BR#ed_cl#若不超過一次, 那就是組合二( 6, 1, 0 ): 六紅三黃.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#五種暗號可以完全代表八種顏色數量組合;#ed_op#BR#ed_cl#而依據之前的結論甲, 知道顏色數量組合就可以保證大家都活;#ed_op#BR#ed_cl#所以三個犧牲者可以拯救七個人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#100/(3+7) = 10#ed_op#BR#ed_cl#10*7 = 70  一共有七十人必活.#ed_op#BR#ed_cl#(10*3) / 3 = 10  另外三十人有三分之一的機率矇對.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#答: 70人必活, 期望值80人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl#

YLL討論網

發表回覆

+ / -檢視主題

[數學]..............

[討論]搭訕的終極簡化

[討論]98 + 2/3 = 98.66666

[討論]93 + 7/3 = 95.333333

[討論]版本三 70 + 30/3 = 80

(請將產生的程式碼，剪貼至上方文章區！)
[quote="asmobia"]#ed_op#DIV#ed_cl#前提:#ed_op#BR#ed_cl#連續 x 個農夫排成一隊, 每個農夫都看得見自己前面的所有的人, 也聽得到每個人的說話.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設:#ed_op#BR#ed_cl#每個農夫都知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#策略:#ed_op#BR#ed_cl#假設每個人都知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#BR#ed_cl#同時每個人都可以看見自己前方所有的人, 也可以聽見自己後方所有的回答;#ed_op#BR#ed_cl#所以對每一個農夫而言, 只要他後方的回答全部都是對的, 那他就可以推算出自己的顏色了.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們從隊伍中的最後一個人開始猜, 最後一個人能夠看到其他所有人, 所以他不會錯.#ed_op#BR#ed_cl#如果上一句為真, 對倒數第二人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#BR#ed_cl#如果上一句為真, 對倒數第三人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#BR#ed_cl#..........................................#ed_op#BR#ed_cl#如果上一句為真, 對倒數第 x 人而言, 他後方的答案是一定對的, 所以他也不會錯.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#結論甲:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#"如果 x 個農夫知道全部一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽,#ed_op#BR#ed_cl#那他們從隊伍最末一個人開始猜自己的顏色, 猜完再讓前一個人猜,#ed_op#BR#ed_cl#最後的下場是人人都獲救."#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#所以說, 我的想法是犧牲 n 個農夫, 用她們的回答來作暗號;#ed_op#BR#ed_cl#好讓接下來的 m 個農夫知道她們之間一共有幾頂紅帽, 幾頂黃帽, 幾頂綠帽.#ed_op#BR#ed_cl#我稱那 n 個農夫為犧牲者, 那 m 個農夫為獲救者.#ed_op#BR#ed_cl#犧牲者在隊伍的後面, 所以她們看到的資訊比較多; 獲救者排在隊伍的前面.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設 n 為 3, 那麼這三個犧牲者一共可以產生五種暗號:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#三個全同 => 例: 紅紅紅#ed_op#BR#ed_cl#中間不同 => 例: 紅黃紅#ed_op#BR#ed_cl#尾巴不同 => 例: 紅紅黃#ed_op#BR#ed_cl#前頭不同 => 例: 黃紅紅#ed_op#BR#ed_cl#全不同     => 例: 紅黃綠#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#假設 m 為 7, 那麼這七個獲救者的帽子的各種顏色數量一共有八種組合:#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#              顏色一  顏色二  顏色三  ( 下面數字為該顏色出現次數 )#ed_op#BR#ed_cl#-------------------------------------------------------------------------#ed_op#BR#ed_cl#組合一  7            0            0#ed_op#BR#ed_cl#組合二  6            1            0#ed_op#BR#ed_cl#組合三  5            2            0#ed_op#BR#ed_cl#組合四  5            1            1#ed_op#BR#ed_cl#組合五  4            3            0#ed_op#BR#ed_cl#組合六  4            2            1#ed_op#BR#ed_cl#組合七  3            3            1#ed_op#BR#ed_cl#組合八  3            2            2#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#依據結論甲的暗示, 我們要想方法用五種暗號來代表八種組合.#ed_op#BR#ed_cl#=========================================================#ed_op#BR#ed_cl#組合六( 4, 2, 1 )可以用"全不同"來代表.#ed_op#BR#ed_cl#組合七( 3, 3, 1 )可以用"尾巴不同"來代表.#ed_op#BR#ed_cl#組合八( 3, 2, 2 )可以用"前頭不同"來代表.#ed_op#BR#ed_cl#組合一( 7, 0, 0 )與組合四( 5, 1, 1 )可以用"三個全同"來代表.#ed_op#BR#ed_cl#組合二( 6, 1, 0 ),組合三( 5, 2, 0 )與組合五( 4, 3, 0 )可以用"中間不同"來代表.#ed_op#BR#ed_cl#=========================================================#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#1. 用"全不同"的暗號( 例:紅黃綠 )來處理組合六( 4, 2, 1 ): #ed_op#BR#ed_cl#最前面的( 例:紅 )出現四次, 中間的( 例:黃 )出現兩次, 最後面的( 例:綠 )出現一次.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#2. 用"尾巴不同"的暗號( 例:紅紅黃 )來處理組合七( 3, 3, 1 ): #ed_op#BR#ed_cl#最後面的( 例:黃 )代表出現一次的顏色, 前面兩個暗號是紅還是綠都沒差.#ed_op#BR#ed_cl#也就是說, "紅紅黃" 與 "綠綠黃" 是一樣的, 反正紅與綠都出現三次, 只有黃比較特別.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#3. 用"前頭不同"的暗號( 例:黃紅紅 )來處理組合八( 3, 2, 2 ): #ed_op#BR#ed_cl#最前面的( 例:黃 )代表出現三次的顏色, 後面兩個暗號是紅還是綠都沒差.#ed_op#BR#ed_cl#也就是說, "黃紅紅" 與 "黃綠綠" 是一樣的, 反正紅與綠都出現兩次, 只有黃比較特別.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#4. 用"三個全同"的暗號( 例:紅紅紅 )來處理組合一與組合四:#ed_op#BR#ed_cl#當然, "紅"代表組合一( 7, 0, 0 )裡的 7 或是組合四( 5, 1, 1 )裡的 5.#ed_op#BR#ed_cl#這裡有一個新問題是, 獲救的七個人要如何區分現在是組合一還是組合四?#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#其實不難; 組合四( 5, 1, 1 )裡有兩個不是紅色的帽子:#ed_op#BR#ed_cl#若妳本身是紅色的, 那妳肯定會看到不是紅色的帽子或是聽到不是紅色的回答;#ed_op#BR#ed_cl#若妳本身不是紅色, 妳也會看到另一個不是紅色的帽子或聽到另一個不是紅色的回答.#ed_op#BR#ed_cl#所以對每一個獲救者而言, 若是他看到與聽到的都是紅色, 那就是組合一.#ed_op#BR#ed_cl#不然, 他一定會看見或聽見一個以上不是紅色; 那就是組合四.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5. 用"中間不同"的暗號( 例:紅黃紅 )來處理組合二, 組合三與組合五:#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#5.1. 先討論組合二( 6, 1, 0 )與組合五( 4, 3, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們用這三個暗號( 例:紅黃紅 )的頭尾( "紅" )代表多的那個顏色,#ed_op#BR#ed_cl#也就是組合二的 6 與組合五的 4.#ed_op#BR#ed_cl#然後用這三個暗號( 例:紅黃紅 )中間的暗號( "黃" )代表少的那個顏色,#ed_op#BR#ed_cl#也就是組合二的 1 與組合五的 3.#ed_op#BR#ed_cl#那獲救的七個人要如何區分現在是組合二還是組合五?#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#其實不難; 組合二裡只有一個"黃", 所以不可能有人看到加聽到超過一個"黃";#ed_op#BR#ed_cl#而組合五裡有三個黃, 所以就算自己是"黃", 也至少看到加聽到另外兩個"黃".#ed_op#BR#ed_cl#所以對每一個獲救者而言, 若是他看到與聽到的超過一個"黃", 那就是組合五.#ed_op#BR#ed_cl#不然就是組合二; #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5.2. 再討論組合三( 5, 2, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#我們用三個暗號( 例:紅黃紅 )的頭尾( "紅" )代表多的那個顏色,#ed_op#BR#ed_cl#也就是組合三的 5.#ed_op#BR#ed_cl#然後用三個暗號( 例:紅黃紅 )中間的暗號( "黃" )代表"沒出現"的那個顏色,#ed_op#BR#ed_cl#也就是組合三的 0.#ed_op#BR#ed_cl#請注意, 在這個例子裡, 暗號裡面沒有"綠", 但是綠色帽子有兩個( 組合三的 2 ),#ed_op#BR#ed_cl#所以就算自己的帽子是"綠", 自己也一定會向前看到或從後面聽到另一個"綠"色;#ed_op#BR#ed_cl#也就是說, 沒有人會"看不到也聽不到"綠色, 縱然暗號裡沒有"綠".#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#5.3. 綜合討論組合二( 6, 1, 0 ),組合三( 5, 2, 0 )與組合五( 4, 3, 0 ):#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#當一個獲救者聽到 "中間不同" 的暗號( 例:紅黃紅 )時;#ed_op#BR#ed_cl#他首先看看那個三個暗號( 例:紅黃紅 )中都沒有提到的顏色( "綠" ),#ed_op#BR#ed_cl#有沒有出現在前面其他人的頭上或是背後的人的回答裡;#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#若是有, 那就是組合三( 5, 2, 0 ): 五紅二綠.#ed_op#BR#ed_cl#若是沒有, 那他要看看三個暗號( 例:紅黃紅 )中間的暗號( "黃" ),究竟出現了幾次;#ed_op#BR#ed_cl#若是超過一次, 那就是組合五( 4, 3, 0 ): 四紅三黃.#ed_op#BR#ed_cl#若不超過一次, 那就是組合二( 6, 1, 0 ): 六紅三黃.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#BR#ed_cl#五種暗號可以完全代表八種顏色數量組合;#ed_op#BR#ed_cl#而依據之前的結論甲, 知道顏色數量組合就可以保證大家都活;#ed_op#BR#ed_cl#所以三個犧牲者可以拯救七個人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#100/(3+7) = 10#ed_op#BR#ed_cl#107 = 70  一共有七十人必活.#ed_op#BR#ed_cl#(103) / 3 = 10  另外三十人有三分之一的機率矇對.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl# #ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl#答: 70人必活, 期望值80人.#ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl##ed_op#DIV#ed_cl##ed_op#/DIV#ed_cl# [/quote]