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

上鎖的手提箱其他謎題

答對率:75%
有一個奇妙的手提箱,說明書上面寫著操作的方法:
本手提箱上面一共有8個用來開鎖的按鈕。
8個按鈕中,有4個是「正確的按鈕」、另外4個則是「錯誤的按鈕」。
每一次操作必須要先後按下2個不同的按鈕,
只有在這2個按鈕都是「正確的按鈕」時才能打開手提箱,
其他時候(也就是按下了至少1個錯誤的按鈕)不會有任何反應。

此外,手提箱具有自動隨機重置的防盜裝置,
當每一輪操作達到一定次數後,「正確的按鈕」就會進行更換。
請問:
箱子被操作了幾次以後會發生重置呢?
要如何操作才能必定打開這個箱子呢?

(圖片來源:https://www.flaticon.com/free-icon/briefcase_149018)
iamfelix2018-12-28提供(2019-05-15修改)
來源:於答案中公布
看答案
7次。
箱子按鈕會重置的操作次數,指的是符合以下兩點的次數:
  1. 「使用最佳策略」的最少次數:可以7次打開,就不需要操作到第8次才重置
  2. 「最壞的情況下」的最多次數:要保證可以打開手提箱,如果操作6次無法保證打開,那就必須要到7次才重置。
將八個按鈕用任何方式分為3個、3個、2個共三組,7次分別按以下方式操作即可:
  • 第1~3次:第一組3個按鈕互相兩兩操作(AB-BC-AC)。
    推論:如果沒有成功,代表ABC之中不存在2個正確的按鈕(只有0或1個正確的按鈕),也就是至少有2個錯誤的按鈕。
  • 第4~6次:第二組3個按鈕互相兩兩操作(DE-EF-DF)。
    推論:如果沒有成功,代表DEF之中也不存在2個正確的按鈕(只有0或1個正確的按鈕),也就是至少有2個錯誤的按鈕。
  • 第7次:GH
    推論:若到此都還沒有成功,則由上推論可知,因為總共只有4個錯誤的按鈕,必定是ABC之中有2個錯誤的按鈕、DEF之中也有2個錯誤的按鈕,意即剩下的GH會是正確的按鈕。
題目來源:https://www.youtube.com/watch?v=BSF9s0gbJ2M

解析

我要編輯
由於答案已提供了保證可以在7次開鎖的方法,解析將使用離散數學中的「圖論」證明6次無法保證開鎖,以及答案所使用的方法是唯一做法,留給有興趣的網友閱讀。
「圖」(Graph)是一種表示關係的結構。想像在一平面上有8個點(Node/Vertex),代表著8個按鈕;當我們進行了一次操作(例如按下了AB兩個按鈕),就用一條直線(邊,Edge)把代表A按鈕的點和代表B按鈕的點連起來,經過了6(或7)次操作以後這8個點之間就會有6(或7)條邊。
雖然在遊戲內的按鈕有被編號為A~H,不過其實重要的並非這些按鈕實際的編號為何,正如「圖」是一種表達關係的結構,重點是我們按下的這些按鈕之間的關係--分成BCD、EFG、AH的操作在本質上和答案的ABC、DEF、GH是一模一樣的。

8個按鈕中有4個正確的按鈕和4個錯誤的按鈕,可以想像成這8個點中有4個是紅色的點(代表錯誤的按鈕)、另外4個是藍色的點(代表正確的按鈕),如果成功開鎖就代表有一次操作(一條邊)連在兩個藍色的點上。我們要找到一個「必定開鎖」的方式,指的是「不管這8個按鈕中哪4個是正確的按鈕,透過N次操作,一定能保證有一次操作會按到2個正確的按鈕」;當我們把操作變成了一張「圖」(更精確來說是一張無向簡單圖,因為同一個操作做二次以上很明顯不會對達成目標有所幫助,只需要討論沒有重邊的圖即可)以後,前述要證明的命題就變成了以下的形式:
  1. 不管這個有8個節點、6條邊的圖長成怎樣,都一定能找到一種點的顏色分布使得沒有一條邊是連在兩個藍色的點之上(也就是6次操作無法保證開鎖,因為一定可以出現某種按鈕的組合造成沒有成功開鎖的情況)
  2. 除了解答中3-3-2這一種圖的長相以外,其餘有8個節點、7條邊的圖都一定能找到一種點的顏色分布,使得沒有一條邊是連在兩個藍色的點之上(也就是答案使用的7次操作方式是唯一解,其他方式也都可以出現某種按鈕的組合造成沒有成功開鎖的情況)

接下來我們要將「圖的長相」分為11種,並逐一進行分析(也就是Proof by cases)。
我們將使用「連通元件」(Connected Component)的概念對圖的長相進行分類。連通元件的概念十分簡單,當我們從一個點經過數條邊可以走到另一個點,就代表這兩個點之間是「連通」(Connected)的,而一張圖可能不會所有的點都連通在一起,每一組連通在一起的數個點就是一個連通元件。更直白地說就是「一坨被邊連在一起的點就是一個連通元件」。

我們先根據連通元件的「總數」分成四類:4個以上、3個、2個、和1個。對於3個連通元件的情形,因為總共有8個節點,一共有5種分組方法:(116)(125)(134)(224)(233)。2個連通元件的情形則有4種方法:(44)(35)(26)(17)
  1. 如果有4個以上的連通元件,那就只要在每一個元件都挑一個點塗上藍色,就達成目標了。
  2. 如果3個連通元件的節點數量為(116),代表6個節點的元件上會有6(或7)條邊。注意如果這6個節點中任意2個節點都要有一條邊,則總共必須要有C6取2(組合數)=15>7條邊,因此我們一定能找到兩個節點沒有一條邊將其連起來。挑選1、1、以及這兩個節點塗上藍色就達成目標了。
  3. 如果3個連通元件的節點數量為(125),代表5個節點的元件上會有5(或6)條邊。同上,因為C5取2=10>6條邊,因此我們可以在1、2的元件上各挑一個點,5個節點的元件上挑2個沒有連在一起的點塗上藍色。
  4. 如果3個連通元件的節點數量為(134),則3個節點的元件會有至少2或3條邊,4個節點的元件則相對來說會有6-2=4、6-3=3(或7-2=5、7-3=3)條邊。不管是哪一種情況,因為C4取2=6>5條邊,因此我們可以在1、3的元件上各挑一個點,4個元件上挑2個沒有連在一起的點塗上藍色。
  5. 如果3個連通元件的節點數量為(224),代表4個節點上的元件會有4(或5)條邊,同上,因為C4取2=6>5,所以我們至少會找到其中有兩個點沒有用一條邊連在一起。在2、2的元件上各挑一個點,4的元件上挑兩個點塗上藍色即可。
  6. 如果3個連通元件的節點數量為(233),在6條邊的情況下兩個3個節點的元件分別會有2、3條邊,因此可以在有2條邊的元件上選兩個不相鄰的點、另外兩個元件各選一個點塗上藍色。7條邊的情況就是答案的操作,三個元件都只能選擇一個點,因此選擇第四個點一定會出現兩個藍色的點被連起來。
在討論只有2個元件的一些可能性之前,必須先再介紹一種圖的類別--「」(Tree),樹是一種所有節點全部連通、但邊數=節點數-1的結構,或者說從樹上每一個節點到達其他的點都只有唯一的路徑。根據這個性質可以再推導出樹是「二分圖」(Bipartite graph)的性質:因為從任意一個節點開始,到其他的節點都只會經過固定數量的邊,因此每一個節點距離選定的起點可以分成奇數步或偶數步。把距離自己奇數步的點變成三角形、距離自己偶數(包含自己)步的點變成正方形,則樹中的任何一條邊都剛好連在一個三角形和一個正方形上

  1. 如果2個連通元件的節點數量為(44),6條邊時兩個元件上都有3條邊(都是樹)、7條邊時一個元件有3條邊、另一個有4條邊。因為C4取2=6>4,所以我們可以在兩個元件上都挑2個沒有連在一起的點塗上藍色。
  2. 如果2個連通元件的節點數量為(35),6條邊時3個節點的元件上有2條邊、5個節點的元件上有4條邊(也都是樹)。我們一樣可以在兩個元件上都挑2個沒有連在一起的點塗上藍色。
    7條邊的情況要記得圖的長相會是其中一棵樹上面再加上一條邊(此時他就不是樹了)。如果這條邊加在5個節點的元件上,則情形跟6條邊時一樣,因為C5取2=10>5,所以兩個元件都可以挑2個點塗上藍色;如果這條邊加在3個節點的元件上,則3個節點的元件就只能挑出1個點了。但因為5個節點的元件仍然是一棵樹,根據剛剛提到的二分圖性質,至少會有3個點都是正方形或都是三角形,那麼由於沒有一條邊連在相同的形狀上,我們就能取這3個點和另1個點塗上藍色。
  3. 如果2個連通元件的節點數量為(26),則6個節點的元件上會有5(或6)條邊。同上,由於5條邊時他會是一棵樹,同上我們一定能挑出3個兩兩之間都沒有邊連起來的點,再從2個節點的元件上挑出1個點塗上藍色。6條邊的情況可以想像成是一棵樹再加上一條邊。此時的情況稍為複雜一些:想像這6個點可能有(15)(24)或(33)個A形狀與B形狀,在(33)的情況不管加上的邊會連在哪一種形狀上,另一個形狀都還維持有3個點且兩兩之間沒有邊連起來。(15)、(24)的情況上如果在4(或5)個相同形狀的地方連上一條邊,也都還有4-1=3個兩兩之間沒有邊連起來得點可以選,也就是無論哪一種情況都可以選出3個兩兩之間沒有邊連起來的點,再從2個節點的元件挑1個點出來塗上藍色就好了。
  4. 如果2個連通元件的節點數量為(17),同上,7個節點的元件上會有6(或7)條邊。6條邊的情況是一棵樹,我們可以找出3個兩兩之間都沒有連起來的點;7條邊的情況是一棵樹加上一條邊,不論是(16)(25)(34)個A形狀與B形狀的哪一種情況,我們都仍然可以找出3個兩兩之間都沒有連起來的點,加上1個點的元件塗上藍色即可。
  5. 最後,只有1個連通元件的情況,只會發生在有7條邊時,此時他是一棵樹,因為總共有8個點,我們一定能找出4個都是三角形或都是正方形的點,塗上藍色即可。
以上討論的11種情況涵蓋了所有圖的長相,因此我們可以得知如果只有6條邊(6次操作)一定能找到四個沒有被連起來的藍色的點,也就是無法保證開鎖;7條邊(7次操作)的情況也只有答案所使用的233的方式可以保證開鎖。
2,582
上一道精選其他謎題
下一道精選其他謎題