海姑娘稱珍珠解答

文章來源: 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 在中間，則第二稱有假，假珍珠在第三小組。

再稱兩次能找到假珍珠.還能算出假珍珠的重量。