作者buffalobill (水牛比爾)
看板puzzle
標題[中譯] Puzzleup 2019 (10) TWELVE BALLS
時間Thu Sep 26 09:06:58 2019
題目網址:
http://www.puzzleup.com/2019/
http://www.puzzleup.com/2019/puzzle/?10
答題時限: 09月26日７ＰＭ－比賽結束
加分時限: 09月26日７ＰＭ－10月2日６：５９ＰＭ
答對可得基本分１００分。答案可上傳５次，每改１次答案從基本分扣２０分。
比賽期間內可隨時上傳答案，加分時限內答對第ｎ天加（６－ｎ）分
另依題目的難易有額外加分（如有８０％的人這題答錯，答對者加８０分）
◆TWELVE BALLS
There are 12 balls with all different weights. You want to sort these
balls by weight. You have a friend who will help you with the ordering
process. In each step, you give any 4 balls to your friend and your
friend returns their exact weight order without telling their actual
weight.
What is the minimum number of measurements do you need in order to
guarantee to sort the balls correctly by weight?
有十二顆重量都不一樣的球。你要根據重量來排序這些球。有位朋友會幫忙排序。
每一步，你交給朋友4顆球，你朋友會依重量將這四顆球排序好，但是不告訴你每
顆球有多重。
問至少要經過幾次這樣的測量，才能保證這些球能按照重量排序。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1569460021.A.118.html
1F：推 ACGfans: 這題好難.. 09/26 19:04
2F：→ buffalobill: 我也想不出要怎麼算or寫程式 09/26 20:20
3F：推 Mathmaster: 我覺得這題有歧異，12顆球是有編號的還是外觀相同的 09/27 00:01
4F：→ Mathmaster: 如果外觀相同，朋友排序的時候如果不會讓你看到過程 09/27 00:02
5F：→ Mathmaster: 那麼，後面的詢問會遺失前面詢問得到的資訊。 09/27 00:03
6F：推 ACGfans: 就我的理解 應該是類似有編號吧 09/27 00:36
7F：→ buffalobill: 我也是當作有編號在算的 09/27 10:08
8F：→ zx7353186: 問一下各位大大，填入答案後，如果出現粗體代表什麼意 09/27 18:50
9F：→ zx7353186: 思？ 09/27 18:50
10F：→ ACGfans: 應該沒特別的意思吧? 只有最後的結算才能知道某題對或錯 09/28 14:49
12F：推 ACGfans: 看樓上那篇論文 最後結論也是不確定是否有更少的次數 09/30 15:09
13F：→ ACGfans: 我目前也是卡在這邊 09/30 15:09