数学杂谈：残次品的无砝码天平定位问题

本文主要是介绍数学杂谈：残次品的无砝码天平定位问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 数学杂谈：残次品的无砝码天平定位问题
  • 1. 问题描述
  • 2. 问题解答
  • 3. 问题拓展
    • 1. 引理1
    • 2. 引理2
    • 3. 引理3
    • 4. 推论1
    • 5. 推论2

1. 问题描述

给出问题如下：

12个乒乓球，有一个次品，不知轻重，用一台无砝码天平称三次，找出次品，告知轻重?

这个题目是我在票圈偶然看到的，号称是清北智商线。

emmmm，虽然我是没考上清北啦，不过这个题还是可以玩玩的（手动狗头）……

2. 问题解答

首先，我们将12个小球分为3份，每份均为4个，分别记作 { a 1 , ⋯ , a 4 } \{a_1, \cdots, a_4\} {a1​,⋯,a4​}, { b 1 , ⋯ , b 4 } \{b_1, \cdots, b_4\} {b1​,⋯,b4​}， { c 1 ⋯ c 4 } \{c_1 \cdots c_4\} {c1​⋯c4​}。

然后，我们取前两组进行称重：

• 左侧： { a 1 , ⋯ , a 4 } \{a_1, \cdots, a_4\} {a1​,⋯,a4​}
• 右侧： { b 1 , ⋯ , b 4 } \{b_1, \cdots, b_4\} {b1​,⋯,b4​}

然后任取两组进行第一次天平测量。

下面，我们进行分类讨论：

1. 两堆小球重量一样

   此时，有问题的小球必然在第三堆当中，记 { c 1 ⋯ c 4 } \{c_1 \cdots c_4\} {c1​⋯c4​}，而$A,B$两堆小球必然均为好球。

   然后，我们进行第二次测量：

   • 左侧：$c_1,c_2$
   • 右侧：$c_3,a_1$

   此时有三种情况：

   1. 左侧重

      此时，只有两种可能性：

      • $c_1,c_2$当中有一个次品，且偏重
      • $c_3$为次品，且偏轻

      因此，我们进行第三次测量：

      • 左侧：$c_1+c_3$
      • 右侧：$a_1+a_2$

      此时，有三种情况：

      1. 左侧轻
         • $c_3$为次品，且偏轻
      2. 左侧重
         • $c_1$为次品，且偏重
      3. 一样重
         • $c_2$为次品，且偏重

   2. 左侧轻

      左侧轻与左侧重的情况完全一样，只是结论相反，即：

      • $c_1,c_2$当中有一个次品，且偏轻
      • $c_3$为次品，且偏重

      同样，我们进行第三次测量：

      • 左侧：$c_1+c_3$
      • 右侧：$a_1+a_2$

      此时，有三种情况：

      1. 左侧轻
         • $c_1$为次品，且偏轻
      2. 左侧重
         • $c_3$为次品，且偏重
      3. 一样重
         • $c_2$为次品，且偏轻

   3. 一样重

      此时次品一定是$c_4$,我们只需要对其确定轻重即可，因此我们只需要将其与任意一个好球，比如说$a_1$，进行比较即可：

      • 若$c_4>a_1$，则偏重；
      • 若$c_4<a_1$，则偏轻；

2. 两堆小球重量不一样

   此时，显然$C$堆一定都是好的，而由于我们不确定次品是偏重还是偏轻，因此我们不确定$A$堆和$B$堆哪一堆有问题。不妨设$A$堆为较轻的一堆，而$B$堆为较重的一堆，那么只可能有以下两种情况：

   • $A$堆当中有一个球为次品，且偏轻；
   • $B$堆当中有一个球为次品，且偏重；

   此时，我们进行第二次称重：

   • 左侧： { a 1 , a 2 , b 1 , b 2 } \{a_1, a_2, b_1, b_2\} {a1​,a2​,b1​,b2​}
   • 右侧： { a 3 , c 1 , c 2 , c 3 } \{a_3, c_1, c_2, c_3\} {a3​,c1​,c2​,c3​}

   此时有三种情况：

   1. 一样重：$a_1+a_2+b_1+b_2=a_3+c_1+c_2+c_3$

      此时有问题的一定在剩余的$a_4,b_3,b_4$当中，我们取如下小球进行第三次称重：

      • 左侧：$a_4,b_3$
      • 右侧：$c_1,c_2$

      此时，有三种情况：

      1. 左侧轻
         • $a_4$小球为次品，偏轻；
      2. 左侧重
         • $b_3$小球为次品，偏重；
      3. 两边一样重
         • $b_4$小球为次品，偏重；

   2. 左侧重：$a_1+a_2+b_1+b_2>a_3+c_1+c_2+c_3$

      此时要么次品在左侧的$b_1,b_2$当中，要么次品为$a_3$。

      我们同样取$a_3,b_1$与$c_1,c_2$进行第三次测量，有如下三种情况：

      1. $a_3+b_1>c_1+c_2$
         • $b_1$小球为次品，偏重
      2. $a_3+b_1<c_1+c_2$
         • $a_3$小球为次品，偏轻
      3. $a_3+b_1=c_1+c_2$
         • $b_2$小球为次品，偏轻

   3. 左侧轻：$a_1+a_2+b_1+b_2<a_3+c_1+c_2+c_3$

      此时次品必然在左侧的$a_1,a_2$小球当中，且次品必然偏轻，因此我们直接将他们放到天平两侧进行测量即可，两者当中较轻的小球即为次品。

综上，问题完成。

3. 问题拓展

事实上，上述问题可以进一步推广到更一般的情况：

推论1
已知$\frac{3^n-3}{2}$个小球当中有且仅有一个次品小球，但次品小球与良品小球的重量关系未知。
现给定一个无砝码天平，则我们可以通过$n$次称重来准确找到其中的次品小球，并判断其与良品小球的重量关系。

特别的，如果事先给出一个良品小球，那么上述推论可以进一步放宽到：

推论2
已知$\frac{3^n-1}{2}$个小球当中有且仅有一个次品小球，但次品小球与良品小球的重量关系未知。
现给定一个无砝码天平与一个确定的良品小球，则我们可以通过$n$次称重来准确找到其中的次品小球，并判断其与良品小球的重量关系。

要说明这两个问题，我们需要用到下面三个较弱的引理。

引理1
已知$3^n$个小球当中存在一个次品小球，且重量偏向已知，那么给定一个无砝码天平，我们必然可以在$n$次称重之后准确地找到这个次品小球。

引理2
给定两堆存在次品的小球$A,B$，他们各自均包含$\frac{3^n-1}{2}$个小球。
已知$A$堆小球重于$B$堆小球，且他们之中有且仅有一个次品小球，但不知道是偏轻还是偏重。
此外，我们还有若干个良品小球，且个数不少于$3^{n-1}$个。
现给出一个无砝码天平，则在$n$次称重后，必然可以从这两堆小球当中定位到唯一的一个次品小球，并判断其轻重关系。

引理3

给定两堆小球$A,B$，他们分别包含$\frac{3^n+1}{2}$个小球和$\frac{3^n-1}{2}$个小球。
且两堆小球当中有且仅有一个次品小球，次品小球的重量关系未知。
此外，我们还有若干个良品小球，且个数不少于$3^{n-1}+1$个。
已知$A$堆小球的重量和$B$堆小球加一个良品小球的重量不相同，但是重量关系已知（不妨设为$A$堆小球较重）。
现给出一个无砝码天平，则在$n$次称重后，必然可以从这两堆小球当中定位到唯一的一个次品小球，并判断其轻重关系。

下面，我们逐次来说明这三个引理和两个推论。

1. 引理1

首先，我们重新给出引理1的具体描述如下：

引理1
已知$3^n$个小球当中存在一个次品小球，且重量偏向已知，那么给定一个无砝码天平，我们必然可以在$n$次称重之后准确地找到这个次品小球。

这个结论其实是比较显然的，不过为求严谨，我们用数学归纳法进行一下证明：

首先，由于次品小球的重量偏向已知，我们不妨设次品小球比良品小球要重一些。

此时，我们考察当$n=1$的情况。

这个是比较显然的，我们任取两个小球放到天平两侧，此时：

• 如果天平不平衡，那么其中较重的一个小球就是次品；
• 如果天平平衡，那么剩下的第三个小球就是次品。

然后，我们假设$n\le k$的情况下都满足上述引理，我们考察$n=k+1$时的情况。

此时，我们将小球均分为3组，则每组都有$3^k$个小球，然后我们任取两堆放到天平两侧，则有如下两种情况：

• 如果天平不平衡，那么其中较重的一组小球当中包含次品；
• 如果天平平衡，那么剩下的第三组小球当中包含次品。

此时，我们就退回到了$n=k$时的情况，由此$n=k+1$的情况下同样可以满足。

综上，引理1证毕。

事实上，这个引理可以进一步推广到：

推论
那么给定一个无砝码天平，我们总可以在$n$次称重之后从不超过$3^n$个小球当中准确地找到其中唯一的一个轻重关系已知的次品小球。

这个引理的证明和上面没啥差别，这里就不展开赘述了，有兴趣的读者可以自行考虑一下。

2. 引理2

首先，我们重新给出引理2的具体描述如下：

引理2
给定两堆存在次品的小球$A,B$，他们各自均包含$\frac{3^n-1}{2}$个小球。
已知$A$堆小球重于$B$堆小球，且他们之中有且仅有一个次品小球，但不知道是偏轻还是偏重。
此外，我们还有若干个良品小球，且个数不少于$3^{n-1}$个。
现给出一个无砝码天平，则在$n$次称重后，必然可以从这两堆小球当中定位到唯一的一个次品小球，并判断其轻重关系。

我们使用归纳法对这个问题进行处理。

首先，考虑当$n=1$的情况，此时，$A,B$两堆小球均为1个，另有1个良品小球。

此时，我们令天平两侧分别为：

• 左侧：小球$A$
• 右侧：良品小球

此时有两种情况：

1. 左侧较重
   • 小球$A$为次品，且偏重
2. 两侧一样重
   • 小球$B$为次品，且偏轻

下面，我们假设$n\le k$时引理成立，考察$n=k+1$时的情形。

此时，$A,B,C$三堆小球各自含有$\frac{3^{k+1}-1}{2}$个小球，且有至少

我们令天平两侧分别为：

• 左侧：$3^k$个$A$组中的小球 + $\frac{3^k-1}{2}$个$B$组中的小球
• 右侧：$3^k$个良品小球 + $\frac{3^k-1}{2}$个$A$组中的小球

此时，我们剩余$3^k$个$B$组中的小球在天平之外。

我们可能有以下三种称重结果：

1. 左侧较轻
   • 此时，有问题的小球必然在左侧的$\frac{3^k-1}{2}$个$B$组中的小球或者右侧的$\frac{3^k-1}{2}$个$A$组中的小球当中。此时问题退回到了$n=k$时的情况，因此这种情况下问题得以解决。
2. 左侧较重
   • 此时，有问题的小球必然在左侧的$3^k$个$A$组中的小球当中，且次品小球较重。由上述引理1，问题得解。
3. 两侧一样重
   • 此时，有问题的小球必然在未称重的剩余$3^k$个$B$组中的小球当中，且次品小球较轻。同样由上述引理1，问题得解。

因此，$n=k+1$时，命题同样成立。

综上，引理2证毕。

3. 引理3

同样的，我们将引理3的具体内容重新记录在下面：

引理3

给定两堆小球$A,B$，他们分别包含$\frac{3^n+1}{2}$个小球和$\frac{3^n-1}{2}$个小球。
且两堆小球当中有且仅有一个次品小球，次品小球的重量关系未知。
此外，我们还有若干个良品小球，且个数不少于$3^{n-1}+1$个。
已知$A$堆小球的重量和$B$堆小球加一个良品小球的重量不相同，但是重量关系已知（不妨设为$A$堆小球较重）。
现给出一个无砝码天平，则在$n$次称重后，必然可以从这两堆小球当中定位到唯一的一个次品小球，并判断其轻重关系。

关于这个引理的证明方法和上述引理2的证明方法完全一致。

我们同样采用数学归纳法对这个问题进行处理。

首先，我们考虑$n=1$的情形，此时$A$堆小球有2个，$B$堆小球有1个，另有至少2个良品小球，且已知$A$堆小球的重量大于$B$堆小球加上1个良品小球的重量。

此时，我们进行如下称量：

• 天平左侧：1个$A$堆小球 + 1个$B$堆小球
• 天平右侧：2个良品小球

此时，有三种可能的结果：

1. 天平左侧重
   • 次品小球为天平左侧的$A$堆小球，且偏重
2. 天平左侧轻
   • 次品小球为天平左侧的$B$堆小球，且偏轻
3. 天平平衡
   • 次品小球为剩余的一个$A$堆小球，且偏重

下面，我们假设$n\le k$时上述命题都成立，考察$n=k+1$时的情形。

我们进行如下称量：

• 天平左侧：$\frac{3^k+1}{2}$个$A$堆中的小球 + $3^k$个$B$堆中的小球
• 天平右侧：$\frac{3^k-1}{2}$个$B$堆中的小球 + $3^k+1$个良品小球

此时，对于称量可能出现的三种情况，有：

1. 天平左侧重
   • 次品小球必然在天平左侧的$\frac{3^k+1}{2}$个$A$堆中的小球或者天平右侧的$\frac{3^k-1}{2}$个$B$堆中的小球当中。由之前的归纳总结，我们可以在剩余的$k$次称量之后找到其中的次品小球并判断其轻重情况；
2. 天平左侧轻
   • 次品小球必然在左侧的$3^k$个$B$堆中的小球当中，且次品小球偏轻。我们由前述引理1可知，能够在剩余的$k$次称量之后准确找到其中的次品小球。
3. 天平平衡
   • 次品小球必然在剩余的的$3^k$个$A$堆中的小球当中，且次品小球偏重。我们由前述引理1可知，能够在剩余的$k$次称量之后准确找到其中的次品小球。

因此，$n=k+1$的情况得证。

综上，引理3证毕。

4. 推论1

下面，我们来看一下推论一的证明。

同样的，我们首先回顾一下推论1的细节描述：

推论1
已知$\frac{3^n-3}{2}$个小球当中有且仅有一个次品小球，但次品小球与良品小球的重量关系未知。
现给定一个无砝码天平，则我们可以通过$n$次称重来准确找到其中的次品小球，并判断其与良品小球的重量关系。

此时，我们将小球均分为三堆，则每堆小球都有$\frac{3^{n-1}-1}{2}$个小球。

然后，我们任取两堆放到天平的两侧进行称重，能够有以下两种情况：

1. 天平不平衡
   • 此时，次品小球必然在这两堆小球当中，且两者重量关系已知。由上述引理2，我们能够从中找出次品小球，问题得解。
2. 天平平衡
   • 此时，次品小球必然在剩下的$\frac{3^{n-1}-1}{2}$，且天平上的所有小球都是已知的良品小球，因此，由前述提到的推论2中的结论，这个问题也同样是可解的。

综上，只要下面我们说明了推论2中的情况，那么推论1也就完整证毕了。

5. 推论2

最后，我们来看一下推论2的解法。

同样的，我们先重新给出一下推论2的具体描述：

推论2
已知$\frac{3^n-1}{2}$个小球当中有且仅有一个次品小球，但次品小球与良品小球的重量关系未知。
现给定一个无砝码天平与一个确定的良品小球，则我们可以通过$n$次称重来准确找到其中的次品小球，并判断其与良品小球的重量关系。

这里，我们同样使用归纳法对这个推论进行解答。

首先，对于$n=1$的情况，这个是显然的，因为我们有一个次品小球和一个良品小球，因此我们只需要一次测量就能够判断其与良品小球的重量关系。

下面，我们假设$n\le k$时命题都成立，考察$n=k+1$时的情况。

我们按照如下方式进行第一次天平测量：

• 天平左侧：取$\frac{3^k+1}{2}$个小球
• 天平右侧：取$\frac{3^k-1}{2}$个小球 + 一个良品小球

此时，我们有如下两种情况：

1. 天平不平衡
   • 此时，剩余的$\frac{3^k-1}{2}$个小球必均为良品，因此，由上述引理3，我们可以证明在$k$称重后我们一定可以找到其中的次品小球，并确定其与良品小球对应的重量关系。
2. 天平平衡
   • 此时，次品小球必然在剩余的$\frac{3^k-1}{2}$个小球当中，由之前的归纳结果，我们已知其可以在$k$次称重后找到其中的次品小球，并确定其与良品小球对应的重量关系。

因此，$n=k+1$时命题同样成立。

综上，推论2证毕。

这篇关于数学杂谈：残次品的无砝码天平定位问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---