作者ACGfans (ACGfans)
看板puzzle
标题Re: [中译] Puzzleup 2019 (10) TWELVE BALLS
时间Sat Dec 21 20:49:45 2019
补充一下 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 颗球的方法
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.38.102.222 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1576932588.A.B72.html
1F：推 DreamYeh: good 12/22 12:07