青州网站制作哪家好,安卓开发基础教程,临沂网,php网站制作软件数学杂谈#xff1a;残次品的无砝码天平定位问题 1. 问题描述2. 问题解答3. 问题拓展 1. 引理12. 引理23. 引理34. 推论15. 推论2 1. 问题描述
给出问题如下#xff1a; 12个乒乓球#xff0c;有一个次品#xff0c;不知轻重#xff0c;用一台无砝码天平称三次#xf…数学杂谈残次品的无砝码天平定位问题 1. 问题描述2. 问题解答3. 问题拓展 1. 引理12. 引理23. 引理34. 推论15. 推论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}
然后任取两组进行第一次天平测量。
下面我们进行分类讨论 两堆小球重量一样 此时有问题的小球必然在第三堆当中记 { c 1 ⋯ c 4 } \{c_1 \cdots c_4\} {c1⋯c4}而 A , B A,B A,B两堆小球必然均为好球。 然后我们进行第二次测量 左侧 c 1 , c 2 c_1, c_2 c1,c2右侧 c 3 , a 1 c_3, a_1 c3,a1 此时有三种情况 左侧重 此时只有两种可能性 c 1 , c 2 c_1, c_2 c1,c2当中有一个次品且偏重 c 3 c_3 c3为次品且偏轻 因此我们进行第三次测量 左侧 c 1 c 3 c_1 c_3 c1c3右侧 a 1 a 2 a_1 a_2 a1a2 此时有三种情况 左侧轻 c 3 c_3 c3为次品且偏轻 左侧重 c 1 c_1 c1为次品且偏重 一样重 c 2 c_2 c2为次品且偏重 左侧轻 左侧轻与左侧重的情况完全一样只是结论相反即 c 1 , c 2 c_1, c_2 c1,c2当中有一个次品且偏轻 c 3 c_3 c3为次品且偏重 同样我们进行第三次测量 左侧 c 1 c 3 c_1 c_3 c1c3右侧 a 1 a 2 a_1 a_2 a1a2 此时有三种情况 左侧轻 c 1 c_1 c1为次品且偏轻 左侧重 c 3 c_3 c3为次品且偏重 一样重 c 2 c_2 c2为次品且偏轻 一样重 此时次品一定是 c 4 c_4 c4,我们只需要对其确定轻重即可因此我们只需要将其与任意一个好球比如说 a 1 a_1 a1进行比较即可 若 c 4 a 1 c_4 a_1 c4a1则偏重若 c 4 a 1 c_4 a_1 c4a1则偏轻 两堆小球重量不一样 此时显然 C C C堆一定都是好的而由于我们不确定次品是偏重还是偏轻因此我们不确定 A A A堆和 B B B堆哪一堆有问题。不妨设 A A A堆为较轻的一堆而 B B B堆为较重的一堆那么只可能有以下两种情况 A A A堆当中有一个球为次品且偏轻 B B 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} 此时有三种情况 一样重 a 1 a 2 b 1 b 2 a 3 c 1 c 2 c 3 a_1 a_2 b_1 b_2 a_3 c_1 c_2 c_3 a1a2b1b2a3c1c2c3 此时有问题的一定在剩余的 a 4 , b 3 , b 4 {a_4, b_3, b_4} a4,b3,b4当中我们取如下小球进行第三次称重 左侧 a 4 , b 3 a_4, b_3 a4,b3右侧 c 1 , c 2 c_1, c_2 c1,c2 此时有三种情况 左侧轻 a 4 a_4 a4小球为次品偏轻 左侧重 b 3 b_3 b3小球为次品偏重 两边一样重 b 4 b_4 b4小球为次品偏重 左侧重 a 1 a 2 b 1 b 2 a 3 c 1 c 2 c 3 a_1 a_2 b_1 b_2 a_3 c_1 c_2 c_3 a1a2b1b2a3c1c2c3 此时要么次品在左侧的 b 1 , b 2 b_1, b_2 b1,b2当中要么次品为 a 3 a_3 a3。 我们同样取 a 3 , b 1 a_3, b_1 a3,b1与 c 1 , c 2 c_1, c_2 c1,c2进行第三次测量有如下三种情况 a 3 b 1 c 1 c 2 a_3 b_1 c_1 c_2 a3b1c1c2 b 1 b_1 b1小球为次品偏重 a 3 b 1 c 1 c 2 a_3 b_1 c_1 c_2 a3b1c1c2 a 3 a_3 a3小球为次品偏轻 a 3 b 1 c 1 c 2 a_3 b_1 c_1 c_2 a3b1c1c2 b 2 b_2 b2小球为次品偏轻 左侧轻 a 1 a 2 b 1 b 2 a 3 c 1 c 2 c 3 a_1 a_2 b_1 b_2 a_3 c_1 c_2 c_3 a1a2b1b2a3c1c2c3 此时次品必然在左侧的 a 1 , a 2 a_1, a_2 a1,a2小球当中且次品必然偏轻因此我们直接将他们放到天平两侧进行测量即可两者当中较轻的小球即为次品。
综上问题完成。
3. 问题拓展
事实上上述问题可以进一步推广到更一般的情况 推论1 已知 3 n − 3 2 \frac{3^n-3}{2} 23n−3个小球当中有且仅有一个次品小球但次品小球与良品小球的重量关系未知。 现给定一个无砝码天平则我们可以通过 n n n次称重来准确找到其中的次品小球并判断其与良品小球的重量关系。 特别的如果事先给出一个良品小球那么上述推论可以进一步放宽到 推论2 已知 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球当中有且仅有一个次品小球但次品小球与良品小球的重量关系未知。 现给定一个无砝码天平与一个确定的良品小球则我们可以通过 n n n次称重来准确找到其中的次品小球并判断其与良品小球的重量关系。 要说明这两个问题我们需要用到下面三个较弱的引理。 引理1 已知 3 n 3^n 3n个小球当中存在一个次品小球且重量偏向已知那么给定一个无砝码天平我们必然可以在 n n n次称重之后准确地找到这个次品小球。 引理2 给定两堆存在次品的小球 A , B A,B A,B他们各自均包含 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球。 已知 A A A堆小球重于 B B B堆小球且他们之中有且仅有一个次品小球但不知道是偏轻还是偏重。 此外我们还有若干个良品小球且个数不少于 3 n − 1 3^{n-1} 3n−1个。 现给出一个无砝码天平则在 n n n次称重后必然可以从这两堆小球当中定位到唯一的一个次品小球并判断其轻重关系。 引理3 给定两堆小球 A , B A,B A,B他们分别包含 3 n 1 2 \frac{3^n1}{2} 23n1个小球和 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球。 且两堆小球当中有且仅有一个次品小球次品小球的重量关系未知。 此外我们还有若干个良品小球且个数不少于 3 n − 1 1 3^{n-1}1 3n−11个。 已知 A A A堆小球的重量和 B B B堆小球加一个良品小球的重量不相同但是重量关系已知不妨设为 A A A堆小球较重。 现给出一个无砝码天平则在 n n n次称重后必然可以从这两堆小球当中定位到唯一的一个次品小球并判断其轻重关系。 下面我们逐次来说明这三个引理和两个推论。
1. 引理1
首先我们重新给出引理1的具体描述如下 引理1 已知 3 n 3^n 3n个小球当中存在一个次品小球且重量偏向已知那么给定一个无砝码天平我们必然可以在 n n n次称重之后准确地找到这个次品小球。 这个结论其实是比较显然的不过为求严谨我们用数学归纳法进行一下证明
首先由于次品小球的重量偏向已知我们不妨设次品小球比良品小球要重一些。
此时我们考察当 n 1 n1 n1的情况。
这个是比较显然的我们任取两个小球放到天平两侧此时
如果天平不平衡那么其中较重的一个小球就是次品如果天平平衡那么剩下的第三个小球就是次品。
然后我们假设 n ≤ k n \leq k n≤k的情况下都满足上述引理我们考察 n k 1 n k1 nk1时的情况。
此时我们将小球均分为3组则每组都有 3 k 3^k 3k个小球然后我们任取两堆放到天平两侧则有如下两种情况
如果天平不平衡那么其中较重的一组小球当中包含次品如果天平平衡那么剩下的第三组小球当中包含次品。
此时我们就退回到了 n k nk nk时的情况由此 n k 1 nk1 nk1的情况下同样可以满足。
综上引理1证毕。
事实上这个引理可以进一步推广到 推论 那么给定一个无砝码天平我们总可以在 n n n次称重之后从不超过 3 n 3^n 3n个小球当中准确地找到其中唯一的一个轻重关系已知的次品小球。 这个引理的证明和上面没啥差别这里就不展开赘述了有兴趣的读者可以自行考虑一下。
2. 引理2
首先我们重新给出引理2的具体描述如下 引理2 给定两堆存在次品的小球 A , B A,B A,B他们各自均包含 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球。 已知 A A A堆小球重于 B B B堆小球且他们之中有且仅有一个次品小球但不知道是偏轻还是偏重。 此外我们还有若干个良品小球且个数不少于 3 n − 1 3^{n-1} 3n−1个。 现给出一个无砝码天平则在 n n n次称重后必然可以从这两堆小球当中定位到唯一的一个次品小球并判断其轻重关系。 我们使用归纳法对这个问题进行处理。
首先考虑当 n 1 n1 n1的情况此时 A , B A,B A,B两堆小球均为1个另有1个良品小球。
此时我们令天平两侧分别为
左侧小球 A A A右侧良品小球
此时有两种情况
左侧较重 小球 A A A为次品且偏重 两侧一样重 小球 B B B为次品且偏轻
下面我们假设 n ≤ k n \leq k n≤k时引理成立考察 n k 1 nk1 nk1时的情形。
此时 A , B , C A,B,C A,B,C三堆小球各自含有 3 k 1 − 1 2 \frac{3^{k1}-1}{2} 23k1−1个小球且有至少
我们令天平两侧分别为
左侧 3 k 3^{k} 3k个 A A A组中的小球 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 B B B组中的小球右侧 3 k 3^{k} 3k个良品小球 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 A A A组中的小球
此时我们剩余 3 k 3^{k} 3k个 B B B组中的小球在天平之外。
我们可能有以下三种称重结果
左侧较轻 此时有问题的小球必然在左侧的 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 B B B组中的小球或者右侧的 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 A A A组中的小球当中。此时问题退回到了 n k nk nk时的情况因此这种情况下问题得以解决。 左侧较重 此时有问题的小球必然在左侧的 3 k 3^{k} 3k个 A A A组中的小球当中且次品小球较重。由上述引理1问题得解。 两侧一样重 此时有问题的小球必然在未称重的剩余 3 k 3^{k} 3k个 B B B组中的小球当中且次品小球较轻。同样由上述引理1问题得解。
因此 n k 1 nk1 nk1时命题同样成立。
综上引理2证毕。
3. 引理3
同样的我们将引理3的具体内容重新记录在下面
引理3 给定两堆小球 A , B A,B A,B他们分别包含 3 n 1 2 \frac{3^n1}{2} 23n1个小球和 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球。 且两堆小球当中有且仅有一个次品小球次品小球的重量关系未知。 此外我们还有若干个良品小球且个数不少于 3 n − 1 1 3^{n-1}1 3n−11个。 已知 A A A堆小球的重量和 B B B堆小球加一个良品小球的重量不相同但是重量关系已知不妨设为 A A A堆小球较重。 现给出一个无砝码天平则在 n n n次称重后必然可以从这两堆小球当中定位到唯一的一个次品小球并判断其轻重关系。 关于这个引理的证明方法和上述引理2的证明方法完全一致。
我们同样采用数学归纳法对这个问题进行处理。
首先我们考虑 n 1 n1 n1的情形此时 A A A堆小球有2个 B B B堆小球有1个另有至少2个良品小球且已知 A A A堆小球的重量大于 B B B堆小球加上1个良品小球的重量。
此时我们进行如下称量
天平左侧1个 A A A堆小球 1个 B B B堆小球天平右侧2个良品小球
此时有三种可能的结果
天平左侧重 次品小球为天平左侧的 A A A堆小球且偏重 天平左侧轻 次品小球为天平左侧的 B B B堆小球且偏轻 天平平衡 次品小球为剩余的一个 A A A堆小球且偏重
下面我们假设 n ≤ k n \leq k n≤k时上述命题都成立考察 n k 1 nk1 nk1时的情形。
我们进行如下称量
天平左侧 3 k 1 2 \frac{3^k1}{2} 23k1个 A A A堆中的小球 3 k 3^k 3k个 B B B堆中的小球天平右侧 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 B B B堆中的小球 3 k 1 3^k1 3k1个良品小球
此时对于称量可能出现的三种情况有
天平左侧重 次品小球必然在天平左侧的 3 k 1 2 \frac{3^k1}{2} 23k1个 A A A堆中的小球或者天平右侧的 3 k − 1 2 \frac{3^k-1}{2} 23k−1个 B B B堆中的小球当中。由之前的归纳总结我们可以在剩余的 k k k次称量之后找到其中的次品小球并判断其轻重情况 天平左侧轻 次品小球必然在左侧的 3 k 3^k 3k个 B B B堆中的小球当中且次品小球偏轻。我们由前述引理1可知能够在剩余的 k k k次称量之后准确找到其中的次品小球。 天平平衡 次品小球必然在剩余的的 3 k 3^k 3k个 A A A堆中的小球当中且次品小球偏重。我们由前述引理1可知能够在剩余的 k k k次称量之后准确找到其中的次品小球。
因此 n k 1 nk1 nk1的情况得证。
综上引理3证毕。
4. 推论1
下面我们来看一下推论一的证明。
同样的我们首先回顾一下推论1的细节描述 推论1 已知 3 n − 3 2 \frac{3^n-3}{2} 23n−3个小球当中有且仅有一个次品小球但次品小球与良品小球的重量关系未知。 现给定一个无砝码天平则我们可以通过 n n n次称重来准确找到其中的次品小球并判断其与良品小球的重量关系。 此时我们将小球均分为三堆则每堆小球都有 3 n − 1 − 1 2 \frac{3^{n-1}-1}{2} 23n−1−1个小球。
然后我们任取两堆放到天平的两侧进行称重能够有以下两种情况
天平不平衡 此时次品小球必然在这两堆小球当中且两者重量关系已知。由上述引理2我们能够从中找出次品小球问题得解。 天平平衡 此时次品小球必然在剩下的 3 n − 1 − 1 2 \frac{3^{n-1}-1}{2} 23n−1−1且天平上的所有小球都是已知的良品小球因此由前述提到的推论2中的结论这个问题也同样是可解的。
综上只要下面我们说明了推论2中的情况那么推论1也就完整证毕了。
5. 推论2
最后我们来看一下推论2的解法。
同样的我们先重新给出一下推论2的具体描述 推论2 已知 3 n − 1 2 \frac{3^n-1}{2} 23n−1个小球当中有且仅有一个次品小球但次品小球与良品小球的重量关系未知。 现给定一个无砝码天平与一个确定的良品小球则我们可以通过 n n n次称重来准确找到其中的次品小球并判断其与良品小球的重量关系。 这里我们同样使用归纳法对这个推论进行解答。
首先对于 n 1 n1 n1的情况这个是显然的因为我们有一个次品小球和一个良品小球因此我们只需要一次测量就能够判断其与良品小球的重量关系。
下面我们假设 n ≤ k n \leq k n≤k时命题都成立考察 n k 1 n k1 nk1时的情况。
我们按照如下方式进行第一次天平测量
天平左侧取 3 k 1 2 \frac{3^k1}{2} 23k1个小球天平右侧取 3 k − 1 2 \frac{3^k-1}{2} 23k−1个小球 一个良品小球
此时我们有如下两种情况
天平不平衡 此时剩余的 3 k − 1 2 \frac{3^k-1}{2} 23k−1个小球必均为良品因此由上述引理3我们可以证明在 k k k称重后我们一定可以找到其中的次品小球并确定其与良品小球对应的重量关系。 天平平衡 此时次品小球必然在剩余的 3 k − 1 2 \frac{3^k-1}{2} 23k−1个小球当中由之前的归纳结果我们已知其可以在 k k k次称重后找到其中的次品小球并确定其与良品小球对应的重量关系。
因此 n k 1 nk1 nk1时命题同样成立。
综上推论2证毕。
