Re: [問題] 有十瓶藥

[EIORU ()]

※ 引述《caryyrac (境界線上的平行線)》之銘言：
: 有10瓶裝有相同藥丸的瓶子
: 但不知有幾瓶其中每顆藥丸多了10毫克
: 請問如何只秤重一次就找出哪些瓶子是裝錯的(也就是裝的每顆藥丸每顆都是多10毫克的)

Conway-Guy sequence
OEIS: A005318
a[n] = 0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, ...

S(M) = { a[M]-a[0], a[M]-a[1], a[M]-a[2], ... , a[M]-a[M-1] }
** 在所有2^M個子集合總和彼此皆不相等 a[M]最小 (部分a[n]不一定最低)

ex. M=5, S(5) = { 13, 12, 11, 9, 6 }
    第一瓶13顆, 第二瓶12顆, ..., 第五瓶6顆
    {0} {6} {9} {11} {12} {13} {6+9} {6+11} {6+12} {6+13} {9+11}
    {9+12} {9+13} {11+12} {11+13} {12+13} {6+9+11} {6+9+12} {6+9+13}
    {6+11+12} {6+11+13} {6+12+13} {9+11+12} {9+11+13} {9+12+13}
    {11+12+13} {6+9+11+12} {6+9+11+13} {6+9+12+13} {6+11+12+13}
    {9+11+12+13} {6+9+11+12+13} 皆不相等
    假設秤出來是 75g/51顆 多24g 就可知道 24={11+13} 第1/3瓶錯
    假設秤出來是 85g/51顆 多34g 就可知道 34={9+12+13} 第1/2/4瓶錯

ANS1 M=10, S(10) = { 309, 308, 307, 305, 302, 296, 285, 265, 225, 148 }
ANS2               { 512, 256, 128,  64,  32,  16,   8,   4,   2,   1 }

在藥瓶裝的數量有最大值時 EX.每罐只有500顆 使用ANS1方案


: 要如何把長寬13cm*13cm色紙剪下拼成8cm*21cm的長方形，且不遺棄任何的色紙

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.249.82.252 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1596523883.A.CE7.html
推 arthurduh1: 推推，原來有這樣的結果！
→ arthurduh1: 是說應該是 2^M 個子集合XD
推 caryyrac: 所有1024個子集合是什麼意思
※ 編輯: EIORU (106.107.209.7 臺灣), 08/04/2020 22:54:14