上一道精選其他謎題
下一道精選其他謎題

猜帽上數字其他謎題

答對率:49%
  十個聰明的小朋友按照號碼1~10順序先後站成一路縱隊,每一個小朋友只能看到站在自己前面(號碼比自己小)的每個人,而不能看到自己或自己後面的人。
  現在老師手上有十一頂貼有數字的帽子,上面的號碼為0~10,老師隨意地選取帽子戴在每個小朋友的頭上,然後老師宣布:大家要猜自己帽子上的數字,數字必須介在0~10之間,並且不能重複其他人猜過的數字。接著,老師從10號小朋友一路問到1號。
  玩了一次之後小朋友們做了些討論,老師聽見有人提出了一項策略。之後老師又帶著大家玩了好幾遍,發現每次其中至少會有九位小朋友能夠正確答出帽子上的數字。請問,這群小朋友是怎麼辦到的?
larry(岸輔 鷓)2013-06-17提供(2013-07-04修改)
來源:改編自IMO培訓題
看答案
  1. 每次都會有一頂帽子用不到,假想該數字排在1號的前方,形成0~10的排列。
  2. 排列是具有奇偶性的(見置換的奇偶性),大家約定好奇偶性後,每個人都要去選符合約定的數字。這樣的話,只有10號有可能答錯,剩下的人一定會答對。

舉例:
帽子上的數字是10123456789,而大家約定是偶排列

10號想:?123456789?
101234567890是個奇排列(換成012345678910要換奇數次),
012345678910才是偶排列,於是回答:0。

9號想:0?23456789?
012345678910是個偶排列,於是回答:1。

8號想:01?3456789?
012345678910是個偶排列,於是回答:2。

剩下以此類推

解析

我要編輯
iamfelix, metis...等 2 人共同編輯 | 歷史版本
本題的核心概念為:因為10號的小朋友能看到的視野最廣,即其他所有小朋友(1~9號)帽子上的數字,所以即使他完全無法確定自己的號碼為何,他必須使用自己的回答來暗示前方的人他們帽子上的數字。

根據題意,老師是從10號開始詢問一直問到1號。第10號小朋友對於自己的帽子完全沒有任何線索,因此他必定有可能答錯,那麼剩下的小朋友都必須要答對。而我們也知道問完10號小朋友以後,9號小朋友的視野比10號小朋友少了自己身上的帽子,因此9號小朋友獲得的暗示唯一來自於10號小朋友的回答;當我們假設9號小朋友正確回答自己的號碼時,8號小朋友可以確定的號碼就為自己的視野(1~7號小朋友所戴的帽子)以及9號小朋友所戴的帽子,這時10號小朋友的回答也變成另一引子,讓8號小朋友可以繼續進行正確的回答。

我們可以發現,在這樣的假設下,第10號小朋友雖然無法確知自己的號碼,他的回答將成為其他所有人回答的引子;而其他所有人可以確定8個號碼(自己看的到的號碼數量+自己之後一直到9號小朋友都正確回答得號碼),也就是任何時刻,實際上10號以外的小朋友都只需要抉擇「自己的號碼」以及「不為引子、也不為自己已確定是他人號碼的數字」兩種可能性中何者為正確答案;而10號小朋友則是決擇「自己要在沒看到的兩個號碼中選出哪一個做為回答,讓這個回答的號碼成為引子」。

所以我們必須要找出一個方法,證明這個方法可以讓10號小朋友正確的決定自己的回答(引子)為何,再證明使用這個方法,其他所有小朋友都可以在已知引子以及另外8個號碼下正確的回答,就會符合題目要求了。對於每次都只有兩種可能的分辨,在數學上最基礎的理論就是奇偶,奇偶性可以幫助我們判斷許多情形,在本題也是如此。

解答使用「數字排列的奇偶性」,詳細證明就請大家看解答附的維基網址自己思考了。對於該奇偶性的內容總結來說,我們所需要使用(基本了解)的性質有兩個:
  1. 一個原始數列A,B,C,D,E,F,G,H,I,J,K(因為題目總共有11頂帽子,這裡就列11項)會有非常多種不同的排列方式(諸如C,D,E,A,B,I,J,G,K,H,F、B,I,F,D,E,A,C,H,G,KJ等等,共有11!(階乘)種排法),但任何一種方式都會固定需要「交換奇數次」或「交換偶數次」才能置換回原始的序列A,B,C,D,E,F,G,H,I,J,K,而我們稱呼需要進行「將兩個元素位置交換」奇數次的排列為奇排列,反之需要交換偶數次的排列稱為偶排列。
     
  2. 固定排列中11項元素的其中9項,剩下兩個排列可以藉由交換1次來達到相同,因此兩個排列的奇偶性相反。舉例:我們固定B,C,D,E,F,G,H,I,J九個元素為第2~10項時,剩下的排列有兩種:
    (i)A,B,C,D,E,F,G,H,I,J,K→和原始序列相同,即需要交換0次,為偶排列。
    (ii)K,B,C,D,E,F,G,H,I,J,A→將A與K交換後得(i)的排列,即交換1次後為原序列,為奇排列。
     
  3. 如果我們再由性質2延伸推導一下:當10號小朋友訂定了現在所有人所處的奇偶排列時,剩下的小朋友在符合10號小朋友所見的情況下,排列奇偶性才會與10號小朋友相同。例如,當10號小朋友所見:
    《?,B,C,D,E,F,G,H,I,J,?》時,若自己是A(第一項為K),
    則排列《J,B,C,D,E,F,G,H,I,K,A》會比10號小朋友所見到的序列多交換一次(J/K),故此排列的奇偶性與剛剛10號小朋友回答的相反,為偶排列。
因此,根據性質2,我們就可以發現對於任何一個小朋友決定自己要回答號碼的情況,都會分成奇排列與偶排列兩種。而根據性質3,只要透過一個引子就可以得到「現在的排列情形」,所以小朋友們只要事先指定「原排列」以及「作為引子的排列奇偶性」,再由10號小朋友作為引子即可使1~9號小朋友得出正確的解答。

解答中的實際舉例以0~10作為戴帽的範例可能讓人產生誤解,這裡再舉另一個例子幫助大家了解。
  1. 原序列的選擇:對於這11頂帽子的排列,我們就選擇以「0,1,2,3,4,5,6,7,8,9,10」這一個最基礎的排列做為原序列就好,雖然對於任何排列皆可,但基礎的排列想起來比較不會傷腦。另外我們還先約好「第一項是指沒有用到的那頂帽子」,即「A沒用到的帽子,B第1位小朋友戴的帽子,C第2位小朋友戴的帽子,......,K第10位小朋友戴的帽子。
  2. 引子的排列奇偶性:解答中使用偶排列,這裡就用奇排列吧。
  3. 實際的戴帽情形:我隨便想了一個亂數排列:《8沒用到,5,4,2,0,9,7,10,3,1,6》
     
  4. 第10位小朋友開始使用這個法則:他先看到《?,5,4,2,0,9,7,10,3,1,?》,因為
    《6,5,4,2,0,9,7,10,3,1,8》可以按照0/6→1/5→2/4→3/4→4/6→5/9→6/7→7/10→8/10(置換9次,奇排列)的方式得到原排列,故10號小朋友回答:8。
    (《8,5,4,2,0,9,7,10,3,1,6》為偶排列)
     
  5. 第9位小朋友得到了引子以及自己的序列《?,5,4,2,0,9,7,10,3,?,8》,開始進行排列思考:
    《0,1,2,3,4,5,6,7,8,10,9》可以按照0/1→1/5→2/4→3/4→4/5→5/9→6/7→7/10→8/9→9/10(置換10次,為偶排列)的方式得到原排列,故不選擇此排列,選擇另一排列
    《6,5,4,2,0,9,7,10,3,1,8》(為奇排列),故9號小朋友正確回答:1。
     
  6. 第8位小朋友得到自己的序列《?,5,4,2,0,9,7,10,?,1,8》,開始進行排列思考:(下面的置換次數就不寫了,只要每一次都把前端尚未排列好的數字和原本那個位置的數字交換,就可以得出次數。)
    《3,5,4,2,0,9,7,10,6,1,8》是偶排列,
    《6,5,4,2,0,9,7,10,3,1,8》是奇排列,故第8位小朋友正確回答:3。
     
  7. 第7位小朋友得到自己的序列《?,5,4,2,0,9,7,?,3,1,8》,開始進行排列思考。
    《10,5,4,2,0,9,7,6,3,1,8》是偶排列,所以自己的答案不是6。
    《6,5,4,2,0,9,7,10,3,1,8》是奇排列,故第7位小朋友正確回答:10。
     
  8. 依此類推,如上述解析說明的,接下來每一位小朋友都會正確回答,所以全部只有第10位小朋友猜錯自己以及沒有用到的那頂帽子數字,總共答對了9個人。而在任何排列下,只要依照此約定,就可以有9個人以上答對,而我們也會知道第10位小朋友是否能夠正確回答關鍵在於他們所選定的奇偶性是否與老師放置的帽子排列奇偶性一致,一致的話第10號小朋友就會答對,反之就會與沒有用到的帽子弄混,但其他小朋友仍然會正確答對。
以上即為編解析者用自己的了解所做的說明,如果有任何問題請大家留言告知,謝謝大家。
8,178
上一道精選其他謎題
下一道精選其他謎題