寻找魔法豌豆

ob · 发表于 2006-3-25 09:34:00

小仙女Cinderella有n（n<=10000）个袋子，每个袋子里有无限的豌豆。n-1个袋子里的豌豆是正常的，每粒重一克；有一个特殊袋子里的豌豆是魔法豌豆，每个重两克。每次Cinderella可以用每个袋子里取出若干豌豆，然后放在一起称称有多重。由于她的秤坏了，不能正确称出大于1717克的东西，所以即使Cinderella选出的豌豆总重大于1717克，称量的结果将仍然是1717克（不过这并不会损坏秤）。请帮助她用10次称量找出装有魔法豌豆的袋子。

我的问题：

如果称最多称量100克的东西，给10次称量，最多可以在多少个袋子中找到那个装魔法豆子的袋子？（设有且仅有一个袋子中的豆子是魔法豆子）

constant · 发表于 2006-3-25 19:59:49

怎么觉得9次就够了？

constant · 发表于 2006-3-26 19:06:57

算错了，应该是10次。

constant · 发表于 2006-3-27 00:39:25

好像没错，就是9次。

constant · 发表于 2006-3-27 22:03:25

100克的称，称10次，应该可以称826袋。

勇敢的辛 · 发表于 2006-3-29 16:56:39

1。最后一次称找哪个袋子时，设最多可找m个袋子，第一个取1个豆子，第二个取2个，直至第m袋取m个豆子，总重量最大为m*(m+1)/2+m,须小于1716，易得m最大为57个。将58个袋子编为一个排，称前57个可以确定是否在它们之内，没有则在第58个袋子，所以每个排最多可含58个袋子；

2。倒数第二次称时要找出哪个排，设最多可以选p个排，一排每袋取1个，二排每袋2个，直至p排每袋p个，重量最大为58*p*(p+1)/2+p, 需小于1716，易得p最大为7。将8个排编为一个连，称前7个可以确定是否在它们之内，没有则在第8个排，所以每个连最多可含58×8＝464个袋子；

3。倒数第三次称时要找出哪个连，设最多可以选q个连，一连每袋取1个，二连每袋2个，直至q连每袋q个，重量最大为464*q*(q+1)/2+q ，需小于1716，易得q最大为2。将3个连编为一个营，称前2个可以确定是否在它们之内，没有则在第3个连，所以每个营最多可含464×3＝1392个袋子。

4。9999个袋子需分为6组一次一次称，最多称5次找出哪个组异常，每组（且称为旅）即便平均分最大值1667也大于1392，所以还要将异常旅分为小于1392的团，方法很多，简便起见分为一团1392，二团275，需多称1次。若一团异常，接上述第三步走到第一步。若二团，可直接接第二步。

综上，总共需9次。

如果限重100克，将上面1716换为99，可算出m,p分别为12，3，每班13个袋子，每排4个班共52个袋子，（前面粗心出了低级计算错误），找到排后需称2次，所以还有8次可用来找哪一排。如前，8次可找9个排，而且前7个排因为称重次数没用完8次，可以取99，所以最多可找99×7＋52×2＝797袋。请constant指正。

constant · 发表于 2006-3-29 17:46:20

称一次可以称13袋，这个大家都同意了。

两次可以称56袋：分成5堆，每堆分别有13，13，13，4，13袋。前4堆每袋分别取1，2，3，4颗豆，第5堆不取。共94颗豆。

三次可以称133袋：分成3堆，每堆分别有56，21，56袋。前2堆每袋分别取1，2颗豆，第3堆不取。共98颗豆。

再多就简单了，每称一次可以排除99袋，10次称99*7+133 = 826袋。

唯一问题是一颗豌豆没有1克，蚕豆还差不多。

勇敢的辛 · 发表于 2006-3-30 08:00:24

受教，大喜，谢谢。

倒数第二次以上我思维有惰性，没能将每次称重的效率用到极致。这样，8次可解。constant思路非常清楚，

，说9次估计是有低级计算错误。呵呵，高手也会出错。

一般而言，限重x＋1，限称p次，可这样经q次反推找到最接近x的y， y

最大寻找范围为：(p-q-1)x+2y+（x-y)/2取整

限重1716时，倒数三次可称重分别为58，475（＝58×7＋11＋58），1521（＝475×2＋96＋475），8次最多可称重1716×4＋（1521＋97）＋1521＝10033。

将9999分为1716，1716，1716，1716，1521，64，1521共七个组，

1。前4次从前四组1716个袋子里各拿一个豆子，重量异常就在该组，可简单从其中64个袋子里各拿1个，若重65则在此64袋里，略；否则在剩下1521袋中，接第三步；

2。若前四次没有，从第五组1521里每袋拿1个，从第六组64袋里每袋拿2个一起称重，若重1649则在剩下第七组的1521个袋子里，接第三步；重1650则在第五组里，也接第三步；重1651则在第六的64个袋子里，略；

3。找到异常的1521后，分为475，475，96，475四个小组，第一小组各拿1个，第二小组各拿2个，第三小组拿3个一起称重，若重1046在第四小组，重1047在第一小组，重1048在第二小组，1049在第三小组；

4。找到异常的475后，分为58，58，58，58，58，58，58，11，58九个小组，同上可找到异常的58个之内；

5。找到异常的58个袋子后，第一袋拿1个，第二袋拿2个，……直至57袋拿57个一起称重，比1653重多少就在哪一袋。正好1653克，在最后一袋。

constant · 发表于 2006-3-30 17:34:14

Nicely done.

constant · 发表于 2006-3-30 23:11:42

算的好象有错。称1，2，3，4次，最多应该能称58，474，1519，3136袋。8次称4*1716+3136=10000袋，多一袋都不行。

勇敢的辛 · 发表于 2006-3-31 11:37:44

我不光474算错，后面加法也莫名多加了30。

但是－－－－

老虎也会打盹啊

：

1519*1+97*2+2=1715<1716

1519+97+1519=3135

1716*4+3135=9999

"多一袋都不行"

这次是用计算器算的。回去读小学的话，都要挨批评。

这题目出得真绝。

constant · 发表于 2006-3-31 18:46:11

3136应该是对的。1519*1+98*2+2=1717。

		自动登录	找回密码
密码			立即注册

动态微博

寻找魔法豌豆

怎么觉得9次就够了？

算错了，应该是10次。[:>]

好像没错，就是9次。[:-T]

100克的称，称10次，应该可以称826袋。

已改错。9次即可，100克的秤称10次，我的答案最多找797袋。

826解法

[:-Q]茅塞顿开。如此，8次可解。

Nicely done. [:B]

回复：[:-Q]茅塞顿开。如此，8次可解。

咳，咳，我忍住不笑。老虎也打盹了。

3136应该是对的。15191+982+2=1717。