用三进制解决小球称量问题

1. 引言

有一道有趣的智力游戏题:“有 12 个金色小环,其中一个与其它环不同,请用天平称 3 次将特殊环选出,并说明该环比其它环是轻还是重。”初看起来,此题可以凭借称量中的技巧来解决,并发现 3 次是可能的最少次数。但是,如果将环的总数推广至 m 次,最少称量次数推广至 n 次时,就不再是能用称量技巧轻易解决的问题了。我们发现可以利用数制与编码来解决这个问题。

2. 利用三进制编码解决称环问题

称环游戏可具体推广为:“有 m 个金色小环,其中一个与其它不同,请用天平称最少的次数 n 次,将特殊环选出,并判明轻重”。其等价命题是:“用天平称量 n 次,最多可从多少个环中选出其中的一个特殊环,并判明轻重”。

我们可对小环用下列方法编码:在第i次称量时,若某小环在天平左边,令 ;若某小环在天平右边,令 ;若某小环不在天平上,令 。于是,经 n 次称量后,每个小环上都有编码 ,即每个小环都被赋以一个 n 位三进制编码。

显然,为了找出特殊环,在每次称量时,天平两边所放环的数目应该相等。下面我们定义一些符号:称量结果为“<”,表示天平左边轻于右边;称量结果为“>”,表示天平左边重于右边;称量结果为“=”,表示天平左边等于右边。

设在 n 次称量结束后,特殊环的编码为 ,则有如下事实:

  1. 若特殊环较轻,当 时,第 i 次的称量结果分别是<,>,=;
  2. 若特殊环较重,当 时,第 i 次的称量结果分别是>,<,=。

对称量结果也可用三进制编码表示。当第 i 次称量结果为<,>,=时,分别令 。同时在给定 时,定义其对称码为 ,其中当 时,;当 时,;当 时,

这时可以发现,在特殊环较轻时,其编码 ;在特殊较重时,其编码 。当 时,却无法判明轻重。

下面进一步分析如何称量才能唯一地将特殊环找出并判明轻重。当 n 次称量结束后, 有两种可能:若 ,则可以唯一地判定编码为 的环是特殊环;若 不为 ,则当特殊环较轻时,编码为 的环是特殊环;当特殊环较重时,编码为 的环是特殊环。因为事先并不知道特殊环的轻重,故 ,若同时用来编码就不能唯一判别出特殊环。换句话说,互为对称码的 2 个三进制码至多只能取其中一个用来作为环的编码。

那么,到底具有什么性质的 n 位三进制码可以用来作为编码唯一判断出特殊环呢? n 位三进制码共有 个,其中共有 对对称码和 1 个自对称码 。若只从每对对称码中取一个用来作为小环的编码,于是可以作为小环编码的三进制共有 个。

因为每次称量时天平两边所放环的数目应相等,所以在编码中, 的码的个数应相等。另一方面,n 位三进制码中, 的码共有 个,它们可构成 对对称码,于是从中只能取 个来作小环的编码。但 是奇数,而我们又要求 的编码数与 的编码数相同,即其和是偶数。所以 的编码数的总和应小于等于 且为偶数。而 的三进制码共有 1 个自对称码 对对称码,所以其中可作小环编码的有 个。所以总的来说,要从 n 次称量中唯一判别出特殊环(不一定能判明轻重),则可用作小环编码的 n 位三进制码至多可取 个。这也就说明用天平称量 n 次,最多可从 个环中选出一个特殊环,但由于自对称码 的存在,却不一定能判明轻重。

具体针对此题,本来称量 3 次,,最多可从 13 个环中找出特环殊却不一定能能判明轻重。但为了保证一定能判明轻重,才将总环数从 13 个去掉 1 个变成 12 个,因为要保证一定能判明轻重,就不允许有自对称码  出现。所以,要从 n 次称量中唯一判别出特殊环并一定能判明轻重,则可用作小环编码的 n 位三进制码至多只能有 个。也就是说,用天平称 n 次,最多可从 个环中找出特殊环并判明轻重。至此,我们已从理论上论证了用三进制编码解决该问题的可行性。

3. 利用编码找出特殊环的具体实现步骤

通过以上分析可以看出,按照上述规则选码时,要做到 , 的码数目相同是完全可能的。不过随着 n 的增大,选码的难度将越来越大。当 n 大到一定程度时,要在短时间内选出这样的码根本不可能。那么这个问题应该如何解决呢?

实际上,由于每次称量后均有一个判别过程,所以具体实现并不需要把每个环都严格按照最初的编码来进行称量,完全可以利用每次称量的判别结果将下一次的搜索范围缩小,就可进一步缩小称量范围。因此,我们要保证每次称量时天平两边小环数目相同,不必使最初的编码中 的码数目相同。因为从第 2 次称量开始,就可以利用前面称量判别出的普通环,来弥补最初的编码在这个要求上的漏洞。当然,这样就有一部分普通环节并不按照预先的编码来进行称量。不过这并没有关系,因为我们的目的仅仅是找出特殊环并判明轻重。

下面先给出具体的选码和称量步骤,然后再对其进行一些必要的数学证明。

选码步骤如下:

  1. 为所有 n 位三进制码的集合,根据 的第 1 位 来将其分成 3 组 ,再从 中删去 ,则 中有 个码, 中各有 个码。
  2. 中取出 个码。然后在 中将已取出的  中码的对称码删去,其余码取出,还应再删去 1 个,以保证 的码数目相同。同时,这些从   中选出的码还必须满足如下规则:
    1. 在从 和  中选出的全部码中,若 的码都存在,则从 中选出的全部码中, 的最少数目与 的最少数目均应为不小于 的最小整数;
    2. 在从 中选出的全部码中,若 (或 ) 的码不存在,则从  中选出的全部码中, (或 ) 的码最多只能取 个。
  3. 中任取 个码,且其中无相互对称的码。

经过选码,编码为 的环的数目均为 个,各占环总数 的 1/3。

称量步骤如下:

  1. 第 1 次将编码为 的环全部放在天平左边,将编码为 的环全部放在天平右边,编码为 的环全部不上天平。
  2. 根据第 1 次称量后的结果,我们可以判别出一部分环(至少是总数的 1/3)是普遍环。于是第 2 次就可将搜索范围缩小到可能包含特殊环的那部分环中,在这些属于搜索范围的环中,将编码为 的环全放在天平的左边,编码为 的环全放在天平右边,编码为 的环全部不上天平。按此要求摆放后,若天平两边环数不等,就可在某边补放上已判别出的普通环以使其相等。
    • 说明1:选码步骤中的规则 a 和规则 b 已能保证,在第 2 次称量时,普通环的数目一定能够补足天平两边环数相等。后面将对其给予证明。
  3. 根据第 2 次称量后的结果,又可以判别一部分环是普通环。于是第 3 次就可将搜索范围进一步缩小。在这些可疑的环中,将编码为 的环全放在天平左边,编码为 的环全放在天平右边,编码为 的环全部不上天平。按此要求摆放后,若天平两边环数不等,就可在某边补放上已判别出的普通环以使其相等。
    • 说明2:若称量次数 n≥3,则在按前述步骤进行的前提下,从第 3 次称量开始,每次称量时,由前面的称量判别出的普通环的数目已必定能够补足步骤中所述天平两边环数不等的情况。后面将其给予证明。
  4. 其余步骤类同。

结论如下:最后一次称量结束后,得到称量结果的编码 ,则在处于最后一次搜索的那些环中,必有一个小环的编码为 ,这个环就是特殊环。若其编码是 ,则特殊环较轻;若其编码是 ,则特殊环较重。当然有时在称量过程中即可预先判出其轻重。在称量过程中,对于那些曾属于搜索范围的小环,在它们因被判别出是普通环,而从搜索范围中被剔除以前,都是严格按最初的编码进行称量的。所以,只有那些属于最后一次搜索范围的小环才是完全按最初的编码进行 n 次称量。因此,对于这些小环的编码而言,每个码仍满足唯一且无对称码的规定。所以根据前面已论证的理论,在这些环中,那个编码为 的小环是特殊环。

4. 具体步骤中相关的证明

4.1 说明 1 的证明

规则 a 和规则 b 选码后,就能保证在第 2 次称量时有足够的普通环来弥补因按编码规则摆放而造成的天平两边小环数的不等。

证明:首先进行一些基本分析。 中共有 个编码,其中  的码各有 个; 中情况相同。设 n 次称量的总环数为 ,按我们的选码规则,应从  中各选出 个编码。则第 1 次称量后至少能判别出 个环是普通环。

对此,分别就其在称量中可能出现的最坏情况,即已判出的普通环的数目最少而所有需用往天平上补放的普通环的数目最多的情况进行讨论。若最坏情况都能解决,则其余情况自然能解决。

证规则 a。其最坏情况是第 1 次称量的结果为不等,则由此只能判别出  中选出的 个码所对应的环是普通环,是能差别出的最少数目;并且选码时从  中总共选出最少数目(设为 X)的  () 的码和此时能选的所有 () 的码,则在第2次的搜索范围中, 的码数与 的码数差别最大,使得需要用于补放上天平的普通环数目最多。

那么这个 X 为多大才能使最坏情况得以成功解决呢?分析后列出方程如下:

解得:,因为  不一定是整数,所以这个最少数目 X 应为不小于  的最小整数。

证规则 b。其最坏的情况是:第 1 次称量的结果为不等,则由此只能判别出 中选出的 个码所对应的环是普通环,是能判别出的最少数目;并且从  中选码时,若不选 () 的码,就从 中将 () 的码按最多数目(设为 Y)选出,则在第 2 次的搜索范围中, 的码数与 的码数差别最大,使需要用于补放上天平的普通环数目最多。

那么,这个 Y 应为多大才能使最坏情况得以成功解决呢?经分析,对这种情况,在第 2 次称量时,天平的一边将全部都是由第 1 次称量判别的普通环共 个,所以另一边能放的环数 Y 也最多只能是 个。因此这个最多数目 Y 应为 个。

4.2 说明 2 的证明

称量次数 n≥3 时,在按步骤进行的前提下,从第 3 次称量开始,每次称量时,由前面的称量判别出的普通环的数目已必定能够补足步骤中所述天平两边环数不等的情况。

证明:首行进行一些基本分析。 中  与  的码均各有 个。

对此就其在称量中可能出现的最坏情况,即已判出的普通环的数目最少而所需用于往天平上补放的普通环的数目最多的情况进行讨论。若最坏情况都能解决,则其余情况自然能解决。

其最坏情况的首要前提是:第 1 次称量的结果为不等,即由此只能判别出 中选出的 个码所对应的环是普通坏,是能判别出的最少数目。下面分 2 种情况进行证明。

1. 若第 2 次称量的结果为相等,则最坏情况即第 2 次称量判别出的普通环最少的情况应为:从 中选出的全部码中包含尽可能多的  的码的情况。因为第 2 次称量结果相等,则编码为  的小环就是普通环,而此时 中选出的全部码中即第 2 次搜索范围中, 的码的总数是最少的情况,所以是最坏的情况。

考虑到选码时无对称码的要求,从 中总共能选出的最多的 的码为 个;而相应地,此时从 中选出的  的码的总数,亦即通过第 2 次称量能判别出的普通环数为 个。因为第 1 次称量判别普通环数为  个,所以第 2 次称量后,2 次称量总共判别出的普通环数目为 个。由分析可知,从第 3 次称量开始,每次称量时,随着搜索范围缩小,所需往天平上补放的普通环数目的最大值应小于 个。

因为 ,所以得证。

2. 若第 2 次称量的结果为不等,则最坏情况即第 2 次称量判别出的普通环最少的情况应为:从 中选出的全部码中包含尽可能少的 的码的情况。因为第 2 次称量结果不等,则编码为 的小环就是普通环,而此时 中选出的全部码中即第 2 次搜索范围中, 的码的总数是最少的情况,所以是最坏的情况。

考虑到选码时无对称码的要求,从 中总共能选出的最少的 的码为 个。这个数目也就是通过第 2 次称量能判别出的普通环数目。因为第 1 次称量判别出的普通环数目为 个,所以第 2 次称量后,2 次称量总共判别出的普通环数为 个。由分析可知,从第 3 次称量开始,每次称量时,随着搜索范围缩小,所需往天平上补放的普通环数目的最大值应小于 个。

因为 ,所以得证。

上面对具体操作中的整体选码和称量过程进行了严格证明。这样,按照上述步骤,就能方便快捷地找出特殊环,并判明其较普通环是轻还是重。

IT IS OVER !


再次感谢原作者!

文章归档

阅读更多

Be First to Comment

发表评论

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