作者EIORU ()
看板puzzle
标题Re: [问题] 有十瓶药
时间Tue Aug 4 14:51:20 2020
※ 引述《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://webptt.com/cn.aspx?n=bbs/puzzle/M.1596523883.A.CE7.html
1F：推 arthurduh1: 推推，原来有这样的结果！ 08/04 15:18
2F：→ arthurduh1: 是说应该是 2^M 个子集合XD 08/04 15:19
3F：推 caryyrac: 所有1024个子集合是什麽意思 08/04 19:07
※ 编辑: EIORU (106.107.209.7 台湾), 08/04/2020 22:54:14