海姑娘称珍珠解答

文章来源: constant

1。海姑娘称珍珠

珍珠商海姑娘进了一批珍珠，珍珠装在口袋里，每袋20颗。但是其中有一袋是坏珍珠。好珍珠每颗重1克，坏珍珠每颗重2克。海姑娘向玲珑美女借秤称珍珠。玲珑美女的秤最多可以称100克，再多就坏了，而且玲珑美女只允许海姑娘称4次。海姑娘最多可以从多少袋中找出坏珍珠？

解答：称一次可以称13袋：每袋中分别取0，1，2，...，12颗豆，共78颗，结果比78克重几克就是第几袋。最大重量为78+12=90<100。

两次可以称56袋：把56袋分成5堆，每堆分别有13，13，13，13，4袋。5堆中每袋分别取0，1，2，3，4颗豆，共94颗豆。最大重量为94+4=98<100。

三次可以称133袋：分成3堆，每堆分别有56，56，21袋。每袋分别取0，1，2颗豆，共98颗豆，最大重量为98+2=100。

三次以上就简单了，每次称99袋中的99颗豆，至少可以排除99袋。4次共能称99+133 = 232袋。

从过程中可以看出，倒数第二次每堆不能超过13袋，倒数第三次每堆不能超过56袋，因此这个方法给出的结果是最佳的，每次都把秤的容量用到了极限。


2。海姑娘再称珍珠

海姑娘又进了一批珍珠，这次是每袋10颗。但是又有一袋是坏的。所有好珍珠重量相同，所有坏珍珠重量也相同，且坏珍珠比好珍珠重，但不知究竟重多少。海姑娘向丑女郎借了一个天平，这个天平可以显示哪边放的物品重以及重多少，每个盘子上可以放的重量没有限制。

丑女郎只允许海姑娘称三次。海姑娘能从最多多少袋中找出坏珍珠？

解答：设S为-10到10中的数组成的GCD=1的三元数组，例如（6，-8，9）属于S，（2，4，6）不属于S。这三个数中可以有0，例如（0。0，-1）属于S，（0，0，-2）不属于S。把（0，0，0）也加到S中。现在把S中每个三元数组分配给一个口袋。称的时候，如果数n>0，左边放n个球，如果n<0，右边放n个球，如果n=0，两边都不放。例如标有（3，-5，0）的一袋，第一次左边放3个，第二次右边放5个，第三次不放。称的结果约简之后得到S中的一个数组，该数组对应的口袋就是坏球。例如称的结果是（6，-8，12），约减之后得（3，-4，6），（3，-4，6）的口袋就是坏球。
现在计算|S|。S中不含0的正数组有10^3-5^3-3^3-2^2-1^3+1+1=841个。（这里减掉四个三次方是公约数为2，3，5，7的数组，加两个1是因为公约数为6和10的数组减了两遍。）含一个0的正数组有（100-25-9-4-1+1+1）*3=63个，含两个0的正数组有3个，总共加起来有841*8+63*4+3*2+1=7491个，所以可以称7491袋。


3。海姑娘三称珍珠

这次和二称差不多，但是事先不知道坏珍珠比好珍珠轻还是重，只知道不一样重：

海姑娘又进了一批珍珠，这次是每袋10颗。但是又有一袋是坏的。所有好珍珠重量相同，所有坏珍珠重量也相同，坏珍珠和好珍珠不一样重。海姑娘向丑女郎借了一个天平，这个天平可以显示哪边放的物品重以及重多少，每个盘子上可以放的重量没有限制。

丑女郎只允许海姑娘称三次。海姑娘能从最多多少袋中找出坏珍珠并且能知道坏珍珠比好珍珠轻还是重？

如果不要求知道坏珍珠比好珍珠轻还是重呢？如果事先有一个已知好珍珠呢？

解答：原题（已知坏球较轻）的解答用到-10到10中的数组成的GCD=1的三元数组S。S中每个数组对应一袋球，总共可以称|S| = 7491 袋球。现在我们要找S的子集T来标记球袋。因为不知坏球轻重，S中一个数组和它的对称组只能用一个，即如果用了（6，-8，9），就不能再用（-6，8，-9）。所以T最多只能是S的一半。另外一个条件是每次称时两边的球数要相等，也就是T中所有元素在每个坐标上的和必须是0。下面是一个构造方法。

把-10到10这21个数排成一圈。T中的数组（a, b, c) 满足下列条件之一：1）b 在 a 的顺时针方向的下半圈里，例如 a = 3, b 可以是 4 到 10，以及-10，-9，-8，不可以是 -7 到 2；2）当a= b时, c 在 a 的顺时针方向的下半圈里。这个T满足所需的两个条件，且有|T| = (|S|-3)/2=3744：三个常数组（0，0，0），（1，1，1），（-1，-1，-1）不在T中，S中剩下的数组有一半在T中。

用这个方法N最大可以是3744。如果另外有一个好球，数组（1，1，1）可以加到T中，称的时候用好球来平衡。如果不需要知道轻重，（0，0，0）也可以用上，总共可以有3746袋。


4。海姑娘4称珍珠

海姑娘有32颗珍珠, 外形一样。其中有一颗假珍珠, 其重量与真珍珠不一样，但差多少不知道。海姑娘向长发小妹租了一个秤。问至少要称几次才能保证找到假珍珠?

解答：最少要5次。31颗时可以算出真假珍珠重量。32颗时不一定。
首先把所有珍珠分为 4 组，8颗，8颗，8颗，8颗。
第一秤：称第一和第二组，共16颗，记下平均重量 a；第二秤：称第一和第三组，共16颗，记下平均重量 b。

如果 a=b，则假珍珠在第一组或第四组。把这两组分为四个小组：4颗+4颗，4颗+4颗。第三秤：称第1，3小组，得平均重量 c。

如果a=c，则它就是真珍珠的重量，假珍珠在第四小组里，再称两次能找到假珍珠。如果第四小组只有3颗（总数是 31 颗的情况），还能算出假珍珠的重量。

如果a，c不等，则假珍珠在前三个小组里。把这三小组分为六对：2+2，2+2，2+2。称第1，3，5对，得平均重量d。

如果 a=d，则第一次和第四次称的全是真的，假的在第六对里；如果 c=d, 则第三次和第四次称的全是真的，假的在第四对里；如果a，c，d彼此不相等，计算e=(16a-8c)/8，f=(16a-6d)/10，g=(8c-6d)/2。则有如下四种互不相容的情况：
1.假珍珠在第一对里，三次都称了假珍珠。则 e=f=g；
2.假珍珠在第二对里，第一次和第三次称了假珍珠。则 e=d；
3.假珍珠在第三对里，第一次和第四次称了假珍珠。则 f=c；
4.假珍珠在第五对里, 第三次和第四次称了假珍珠。则 g=a。
而且可算出真假珍珠的重量。

因为已知真假珍珠的重量以及假珍珠在哪一对里，再称一次就可以找到假珍珠。

如果 a，b 不等，则假珍珠在第二组或第三组。把这两组分为四个小组：4颗+4颗，4颗+4颗。第三秤称第1，3小组(8颗)，得平均重量 c。

如果a=c, 则它就是真珍珠的重量，假珍珠在第四小组里；如果b=c，则它就是真珍珠的重量，假珍珠在第二小组里；如果a，b，c彼此不等，则第三称必然有假（因为a，b中有一个为真珍珠的重量），假珍珠在第一或第三小组里。把a，b，c 由小到大排列，中间的那个(a或b)含有假珍珠。如果 a 在中间，则第一称有假，假珍珠在第一小组；如果 b 在中间，则第二称有假，假珍珠在第三小组。

再称两次能找到假珍珠.还能算出假珍珠的重量。