Puzzleup 2019 (10) TWELVE BALLS - 拼圖

補充一下 10 次的測法

也請大家幫忙看一下有沒有問題

文章有點長

----

第 1,2,3 次: 將 12 顆球分成三組 a b c

a1 > a2 > a3 > a4
b1 > b2 > b3 > b4
c1 > c2 > c3 > c4


第 4 次: [a2,b2,c2] + 任意一顆

可假設 a2 > b2 > c2

此時我們可以 b2 作為分界點分成兩個群組 G1,G2

G1 全大於 b2, 共有 3 顆球 (a1 > a2, b1)
G2 全小於 b2, 共有 5 顆球 (c2 > c3 > c4, b3 > b4)

當然 G1 的每個成員也都大於 G2
剩下 a3,a4,c1 還不清楚和 b2 的關係


第 5 次: [b2,a3,a4,c1]

比較之後就可以將 a3,a4,c1 分到 G1,G2

G1 的總數為 3+X
G2 的總數為 5+Y
X+Y = 3 (即為 a3,a4,c1)

為了方便我們將 a3,a4,c1 重新命名為 d1>d2>d3


經過這 5 次測量後
我們以 b2 為分界分成 G1,G2
接下來只要分別將 G1,G2 內部自己排序好即可

此時總共有四種 case
X=0 Y=3 (Y: d1>d2>d3)
X=1 Y=2 (X: d1, Y: d2>d3)
X=2 Y=1 (X: d1>d2, Y:d3)
X=3 Y=0 (X: d1>d2>d3)

case 1: X=0 Y=3 (Y: d1>d2>d3)
G1=3 G2=8
G1 需要量 1 次
G2 需要量 4 次
總共 5+1+4 = 10 次

case 2: X=1 Y=2 (X: d1, Y: d2>d3)
G1=4 G2=7
G1 需要量 1 次
G2 需要量 4 次
總共 5+1+4 = 10 次

case 3: X=2 Y=1 (X: d1>d2, Y:d3)
G1=5 G2=6
G1 需要量 2 次
G2 需要量 3 次
總共 5+2+3 = 10 次

case 4: X=3 Y=0 (X: d1>d2>d3)
G1=6 G2=5
G1 需要量 3 次
G2 需要量 2 次
總共 5+3+2 = 10 次

因此這四種 case 皆為 10 次完成排序

----

接下來比較容易有問題的在於 case 1 的 G2
8 顆球要怎麼在 4 次內排序完?

正常來說 8 顆球應該要 5 次
不過經過前面的排序後 可以得知以下關係
c2>c3>c4, b3>b4, d1>d2>d3
為了方便說明, 重新命名為
e1>e2>e3, f1>f2>f3, g1>g2

第 1 次: [e2,f2,g1,g2]

可假設 e2>f2

此時總共有四種 case (其餘case為鏡射可略過)

e2 > f2 > g1 > g2
e2 > g1 > f2 > g2
g1 > e2 > f2 > g2
e2 > g1 > g2 > f2

和前面的方法類似
要找到中間球 M, 分成兩組 G3,G4 使得 G3>M>G4

case 1: e2 > f2 > g1 > g2, 中間球 M 為 f2
(G3: e1>e2, f1) (G4: g1>g2, f3)
第 2 次: [f2, e3] + 任意兩顆
G3 = 3+X
G4 = 3+Y
X+Y = 1 (e3)
G3 需要量 1 次
G4 需要量 1 次
總共 2+1+1 = 4 次

case 2: e2 > g1 > f2 > g2, 中間球 M 為 g1
(G3: e1>e2) (G4: f2>f3, g2)
第 2 次: [g1, e3, f1] + 任意一顆
G3 = 2+X
G4 = 3+Y
X+Y = 2 (e3,f1)
if (X=0 Y=2)
G3 需要量 0 次 (已知 e1>e2 不用量)
G4 需要量 2 次
else
G3 需要量 1 次
G4 需要量 1 次
總共 2+0+2=4 or 2+1+1=4 次

case 3: g1 > e2 > f2 > g2, 中間球 M 為 e2,f2
(G3: g1,e1) (G4: g2,f3)
第 2 次: [e2,f2,e3,f1]
G3 = 2+X
G4 = 2+Y
X+Y = 2 (e3,f1)
G3 需要量 1 次
G4 需要量 1 次
總共 2+1+1 = 4 次

case 4: e2 > g1 > g2 > f3, 中間球 M 為 g1,g2
(G3: e1>e2) (G4: f3>f4)
第 2 次: [g1,g2,e3,f1]
G3 = 2+X
G4 = 2+Y
X+Y = 2 (e2,f1)
G3 需要量 1 次
G4 需要量 1 次
總共 2+1+1 = 4 次

因此這四種 case 皆為 4 次完成排序

----

其他一些比較細節的地方就不列了

以上就是 10 次排序完 12 顆球的方法

--