证明硬币的重量

问题描述:你有\(n\)枚重量不同但外观相同的硬币和一架托盘天平,你清楚地知道每枚硬币的重量是多少,而你的朋友只知道硬币的重量分别为\(1,2,…,n\),不知道哪枚硬币对应哪个重量值。现在你希望用这架天平向你的朋友证明每枚硬币的重量,并最小化你使用天平次数的复杂度。

你的朋友是绝对聪明的,若某一时刻只有唯一的硬币与重量值的对应关系能满足所有已有的称量结果,他会立即反应过来并确认你给出的结果。

这个问题与很多经典的硬币称重问题的不同之处在于,你很清楚最后的结果,只是需要对别人做一个证明,这有点像在传统的硬币称量问题背景下,询问运气最好的时候的最少次数,其解法也是充满了启发性。

解法一:\(O(n)\)

我们只需要依次称量重量为\(i-1\)和\(i\)的硬币即可(\(2\leq i\leq n\)),总共\(n-1\)次称量,复杂度为\(O(n)\)。

这种方法只利用了硬币重量互不相同这一点,却完全没有利用硬币的重量分别为\(1,2,…,n\)这个性质,故还有很大优化空间。

解法二:\(O(\sqrt n)\)

首先我们找到一个正整数\(k\)使得它是满足\(1+2+…+k\leq n\)的最大正整数,假设\(m=1+2+…+k\),我们将重量为\(1,2,…,k\)的硬币和重量为\(m\)的硬币分别放在天平两边证明这个等式。

接下来,我们用天平依次称量重量为\(1\)和\(2\);\(2\)和\(3\);…;\(k-1\)和\(k\)的硬币,以此来证明他们的重量单调递增,且这一步总称量次数是\(O(\sqrt n)\)的。

根据\(k\)的选取,我们知道\(n-k\leq m\leq n\),那么用天平依次称量重量为\(m\)和\(m+1\)、\(m+1\)和\(m+2\)、…、\(n-1\)和\(n\)的硬币,以此来证明它们的重量单调递增,且这一步总称量次数是\(O(\sqrt n)\)的。

现在,你聪明的朋友已经能够推断出重量为\(1,2,..,k\)的硬币重量值是多少了。稍作分析,你告诉了朋友有\(k\)枚硬币的重量之和还比另外\(n-m-1\)枚硬币轻,由于\(k\)的选取,这种硬币组合是唯一的,而你又证明了它们之间的相对大小,故可以推断出这\(k\)枚硬币具体的重量值。知道了这些硬币的重量之后,重量在\(m\)和\(n\)之间的硬币也就确定下来了。

一个经典而简单的结论是,用重量为\(1,2,…,k\)的硬币可以直接或间接表示出\(1,2,…,m\)中所有重量值。接下来我们把重量为\((1,m-1)\)和\(m\);\((1,m-2)\)和\(m-1\);…;\((1,n-\left\lfloor\sqrt n\right\rfloor)\)和\(n-\left\lfloor\sqrt n\right\rfloor+1\)的硬币分别放在天平两侧进行称量,这样操作之后就可以证明重量在\(n-\left\lfloor\sqrt n\right\rfloor\)和\(n\)之间的硬币的重量值了,且这一步的总称量次数是\(O(\sqrt n)\)的。不难证明,确定了这些硬币的重量,我们可以直接或间接表示出\(1\)到\(n\cdot\left\lfloor\sqrt n\right\rfloor\)中所有的重量值。

我们把重量大于\(k\)小于\(m\)的硬币按重量从小到大排序后每\(\left\lfloor\sqrt n\right\rfloor\)枚分为一组,这样组数和硬币数都是\(O(\sqrt n)\)的。根据前述结论,我们可以用已知重量的硬币表示出每组硬币的重量之和,此时最轻的一组的重量只要给出后,由于前面的过程证明了该组内没有重量为\(1,2,…,k\)的硬币,你的朋友就能够知道这组内具体有哪些硬币。以此类推,反复使用这个结论,你的朋友事实上能够推断出每组中具体有哪些硬币,且这一步的总称量次数是\(O(\sqrt n)\)的。

接下来,我们依次把每组中最轻的、第二轻的、…、最重的硬币取出来并表示出他们的重量之和。由于你的朋友已经知道了每组中有哪些硬币,故你在表示每组最轻的硬币的重量之和时,他就能知道这里面每枚硬币具体的重量是多少。依次类推,当你完成所有的称量后,你的朋友也就知道了所有硬币的重量,且这一步的总称量次数是\(O(\sqrt n)\)的。

综上所述,得到了一个仅需\(O(\sqrt n)\)次称量的办法可以解决这个问题。

解法三:\(O(\log n)\)

首先我们将重量为\(1\)和\(2\)的硬币分别放在天平两边,接下来分别在天平两边放上下列等式两边出现的重量的硬币:$$1+2=3$$$$1+2+3=6$$$$1+2+3+6=12$$$$……$$$$1+2+3+…+3\cdot 2^{\lambda-1}=3\cdot 2^\lambda$$\(\qquad\)其中\(\lambda\)是使得\(3\cdot 2^\lambda\)不大于\(n\)的最大正整数,这一步一共使用了\(O(\log n)\)次天平,且如果重量为\(1,2\)的硬币能够被证明的话,你的朋友就会马上得知所有重量形如\(3\cdot 2^\lambda\)的硬币的实际重量值。

我们把重量为\(1\)、\(2\)和形如\(3\cdot 2^\lambda\)的硬币称为基础硬币。此时最理想的情况是\(n=3\cdot 2^\lambda\),则无需任何额外操作你聪明的朋友就能确信所有基础硬币的重量。如果\(n\neq 3\cdot 2^\lambda\),则我们可以选一些基础硬币使得它们的重量之和为\(n\)(易证这是能做到的),由于你选择的基础硬币是能够满足上述所有等式的重量最小的一组硬币,所以你的朋友也可以据此判断出所有基础硬币的重量。

接下来把非基础硬币从小到大排序,然后将它们分成连续的三段,使得第一段的硬币数量大于第三段,且三段硬币重量尽可能接近(最重的一段硬币与最轻的一段硬币重量之差尽可能小)。由于没有硬币的重量超过\(n\),因此这样分组以后两段硬币重量之差不可能超过\(n\)。现在将第一段和第三段放在天平的两侧,再添加一些基础硬币使天平平衡,我们就得到了一个新的等式。

事实上,这个分段是卡得很死的,由于你的朋友知道第一段和第三段硬币的数量,又知道它们之间重量的差值,他可以据此判断出第一段硬币就是非基础硬币中最轻的那些硬币,而第三段硬币就是非基础硬币中最重的那些硬币。这可以通过反证法来完成:将第一段或者第三段硬币中的一枚换成第二段中的某些硬币或者对换第一段和第三段的某枚硬币,这个重量之差一定会更大。由此,你的朋友可以判断出你分出的三段硬币中每一段具体有哪些硬币。

递归进行以上操作,即将每一段再分成三段并将第一段和第三段进行称量,并使用基础硬币使天平平衡,直到某一段只剩下一枚硬币。根据刚才的论断,你的朋友可以通过称量结果知道每一段中具体有哪些硬币,那么也就能在某一段只有一枚硬币时直接判断出这枚硬币的重量值。

现在来考虑这样做的复杂度,我们不妨假设去掉基础硬币后每段硬币的重量仍然是连续的,并将第一段硬币的重量之和看作所有硬币总重量之和的\(\frac{1}{3}\),则易知第一段硬币的数量约为硬币总数的\(\sqrt\frac{1}{3}\),所以总的时间复杂度不超过\(O(\log_\sqrt{3}n)\),即我们得到了一个仅需\(O(\log n)\)次称量的办法。

发表评论

电子邮件地址不会被公开。 必填项已用*标注