Re: [同樂] 贈美麗的冰魔1 加碼 悲傷的亡魂2

[ihady (艾和狄)]

=============================================================================

加碼贈送悲傷的亡魂2。

那麼問題是：

如果現在有100個重量未知的物體，你想要知道它們的前10重的是哪10個(順序不管)

但是手邊只有一個詭異的秤重器具，可以放上最多10個物體，

測量結果除了放上去的10個物體的重量順位之外，什麼都不知道。

問：最少要測量幾次才能得知？



我無法證明我的方法是次數最少的，但我能證明我的方法是正確的

我的答案：對於n*n的物體，只要2*n次秤重就可以找出前n重的物品

證明手段為「除去那些不是前n重的物體」

將n*n個重量未知的物體分成n堆，每堆n個去秤重(秤了n次)
我們得到每堆由重到輕的排序，將每堆最重的標為1，依序2,3,4...最輕的標為n，
然後把每堆最重的物體拿出來秤重(第n+1次)，
一樣作排序，最重的那標為A，依序B,C,D...N

如此得到下列陣列

　　A1→B1→C1→D1→…　…→X1→Y1→N1
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A2　B2　C2　D2　…　…　X2　Y2　N2
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A3　B3　C3　D3　…　…　X3　Y3　N3
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A4　B4　C4　D4　…　…　X4　Y4　N4
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　An　Bn　Cn　Dn　…　…　Xn　Yn　Nn

A1毋庸置疑，是所有物體中最重的
n*n中前n重的物品們，一定有A1一份

將那些已經有N個以上比它重的物品們劃去，我們剩下：


　　A1→B1→C1→D1→…　…→X1→Y1→N1
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A2　B2　C2　D2　…　…　X2　Y2　N2
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A3　B3　C3　D3　…　…　X3　Y3　N3
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A4　B4　C4　D4　…　…　X4　Y4　N4
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　An　Bn　Cn　Dn　…　…　Xn　Yn　Nn


一個等邊三角形的的陣列，第一部份結束，總共秤重了(n+1)次
接下來進入第二部份：

對這一排n個最尾端的作秤重 (第n+2次)

　　A1→B1→C1→D1→…　…→X1→Y1→N1
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A2　B2　C2　D2　…　…　X2　Y2　N2
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A3　B3　C3　D3　…　…　X3　Y3　N3
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A4　B4　C4　D4　…　…　X4　Y4　N4
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　An　Bn　Cn　Dn　…　…　Xn　Yn　Nn

這斜排總共有n個，我們可以得到一個排序，我只找出最重的那個物體
其他的物體，比這個最重的物體輕，又比之前n-1個物體輕(箭號)，
已經比n個物體輕了，所以不可能列入前n重的物體，全都消去

如此得到這一排最重的一個物體集合，S1(S1只有一個物體)

然後對這個集合S1與，下一排n-1個物體，總共n個物體作秤重(第n+3次)
要找出前兩重的物體

　　A1→B1→C1→D1→…　…→X1→Y1→N1
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A2　B2　C2　D2　…　…　X2　Y2　N2
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A3　B3　C3　D3　…　…　X3　Y3　N3
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A4　B4　C4　D4　…　…　X4　Y4　N4
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　…　…　…　…　★　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　An　Bn　Cn　Dn　…　…　Xn　Yn　Nn

這一排中，不是前兩重的物體們，都比這兩個物體輕，也比之前n-2個物體輕(箭號)
已經比n個物體輕了，所以不可能列入前n重的物體，全都消去

這兩個物體，稱為集合S2(S2有兩個物體，有可能不包含S1)

再把S2與下一排n-2個物體作秤重(第n+4次)，找出前3重的物體們，得到集合S3
再把S3與下一排n-3個物體作秤重(第n+5次)，找出前4重的物體們，得到集合S4
…
…
再把Sn-2與下一排2個物體作秤重(第2n次)，找出前n-1重的物體們，得到集合Sn-1
(N1那排作成的集合是S1，到了第n-1個B1這排作成的集合就是Sn-1)

　　A1→B1→C1→D1→…　…→X1→Y1→N1
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A2　B2　C2　D2　…　…　X2　Y2　N2
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A3　B3　C3　D3　…　…　X3　Y3　N3
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　A4　B4　C4　D4　…　…　X4　Y4　N4
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　　　　　　　　　　　　　　　　　　
　　…　…　…　…　…　…　…　…　…
　　↓　↓　↓　↓　　　　　↓　↓　↓
　　An　Bn　Cn　Dn　…　…　Xn　Yn　Nn


我證明了，除了Sn-1中n-1個物品，與左上角的A1之外，

其他所有的物品，都比至少n個物品還輕

那麼所有n*n個物品中，只剩下這n個物品，並沒有n個物品比它們重

所以前n重的物品，就是這集合 A1+集合Sn-1，這n個物品了


--
◆───────────── ◤◢"▼  ◢      ───────────────◆
│                         ◤ ▄▅▇     ▅▄▅▃▂▁_                      │
│  Ｋururugi Ｓuzaku         ▇▇◣    ◢    ▇▆▅▃■ █Ｋeep Ｋicking.█│
│                                     ▲                                   │
│                         ▁ _  ▼                                         │
◆──── ▅▃▂▃▄▅▆▁▂▁_      ▲ψquetzal ─────────────◆
--

--

     強者無心  智者無慮  愚者無憂  勇者無懼  仁者無敵



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.32.216.166
→ nahsnib:這實在不是適合在這裡討論的問題....拿去數學版問問看？
推 laicat:我直覺這題應該是腦筋急轉彎類型的...        ((分明想偷懶
推 mashiroro:是朱雀踢!!(X)
推 SILVERSELENE:........來這邊就不想去解數學題(懶惰)XD
→ SILVERSELENE:不過你去數學版應該立刻就解出了，這題我有印象國高
→ SILVERSELENE:中考過......算是有難度的題目
→ ihady:你們國高中考試也太難了！！
→ Pegasus99:是傳說中不管什麼場合都能亂入的朱雀踢!!
→ c19918043:......我是不是進錯板了(揉眼睛)