编码巧解称环游戏

╰+攻爆jí腚メ 2022-08-14 02:49 82阅读 0赞

张路

摘　要　针对一个“用天平称最少的次数来从所给环中找出特殊环，并判明轻重”的游戏，巧妙地采用编码方法予以解决。此方法对所给环和称量的结果分别进行编码，然后利用特殊环的编码与称量结果的编码之间的关系，找出特殊环并判明轻重。同时给出了该方法在具体实现时的选码、称量规则及其证明。  
关键词　三进制编码　对称码　称环游戏

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

2　利用三进制编码解决称环问题  
　　称环游戏可具体推广为：“有m个金色小环，其中一个与其它不同，请用天平称最少的次数n次，将特殊环选出，并判明轻重”。其等价命题是：“用天平称量n次，最多可从多少个环中选出其中的一个特殊环，并判明轻重”。  
　　我们可对小环用下列方法编码：在第i次称量时，若某小环在天平左边，令Ai＝1；若某小环在天平右边，令Ai＝2；若某小环不在天平上，令Ai＝0。于是，经n次称量后，每个小环上都有编码A＝(A1，A2，…，An)，即每个小环都被赋以一个n位三进制编码。  
　　显然，为了找出特殊环，在每次称量时，天平两边所放环的数目应该相等。下面我们定义一些符号：称量结果为“＜”，表示天平左边轻于右边；称量结果为“＞”，表示天平左边重于右边；称量结果为“＝”，表示天平左边等于右边。  
　　设在n次称量结束后，特殊环的编码为A＝(A1，A2，…，An)，则有如下事实：  
　　(1) 若特殊环较轻，当Ai＝1，2，3时，第i次的称量结果分别是＜，＞，＝；  
　　(2) 若特殊环较重，当Ai＝1，2，3时，第i次的称量结果分别是＞，＜，＝。  
　　对称量结果也可用三进制编码表示。当第i次称量结果为＜，＞，＝时，分别令Bi＝1，2，0。同时在给定B＝(B1，B2，…，Bn)时，定义其对称码为B’＝(B’1，B’2，…，B’n)，其中当Bi＝1时，B’i＝2；当Bi＝2时，B’i＝1；当Bi＝0时，B’i＝0。  
　　这时可以发现，在特殊环较轻时，其编码A＝B；在特殊较重时，其编码A＝B′。当A＝(0，0…，0)时，却无法判明轻重。  
　　下面进一步分析如何称量才能唯一地将特殊环找出并判明轻重。当n次称量结束后，B有两种可能：若B＝(0，0，…，0)，则可以唯一地判定编码为A(0，0，…，0)的环是特殊环；若B不为(0，0，…，0)，则当特殊环较轻时，编码为A＝B的环是特殊环；当特殊环较重时，编码为A＝B’的环是特殊环。因为事先并不知道特殊环的轻重，故A＝B与A＝B’，若同时用来编码就不能唯一判别出特殊环。换句话说，互为对称码的2个三进制码至多只能取其中一个用来作为环的编码。  
　　那么，倒底具有什么性质的n位三进制码可以用来作为编码唯一判断出特殊环呢?n位三进制码共有3n个，其中共有(3n－1)/2对对称码和1个自对称码(0，0，…，0)。若只从每对对称码中取一个用来作为小环的编码，于是可以作为小环编码的三进制共有(3n－1)/2+1＝(3n+1)/2个。  
　　因为每次称量时天平两边所放环的数目应相等，所以在编码中，A1＝1与A1＝2的码的个数应相等。另一方面，n位三进制码中，A1＝1与A1＝2的码共有2×3n－1个，它们可构成3n－1对对称码，于是从中只能取3n－1个来作小环的编码。但3n－1是奇数，而我们又要求A1＝1的编码数与A1＝2的编码数相同，即其和是偶数。所以A1＝1与A1＝2的编码数的总和应小于等于3n－1－1且为偶数。而A1＝0的三进制码共有1个自对称码(0，0，…，0)和(3n－1－1)/2对对称码，所以其中可作小环编码的有1+(3n－1－1)/2个。所以总的来说，要从n次称量中唯一判别出特殊环(不一定能判明轻重)，则可用作小环编码的n位三进制码至多可取(3n－1－1)+1+(3n－1－1)/2＝(3n－1)/2个。这也就说明用天平称量n次，最多可从(3n－1)/2环中选出一个特殊环，但由于自对称码(0，0，…，0)的存在，却不一定能判明轻重。  
　　具体针对此题，本来称量3次，n＝3，(3n－1)/2＝13，最多可从13个环中找出特环殊却不一定能能判明轻重。但为了保证一定能判明轻重，才将总环数从13个去掉1个变成12个，因为要保证一定能判明轻重，就不允许有自对称码(0，0，…，0)出现。所以，要从n次称量中唯一判别出特殊环并一定能判明轻重，则可用作小环编码的n位三进制码至多只能有［(3n－1)/2］－1个。也就是说，用天平称n次，最多可从［(3n－1)/2］－1个环中找出特殊环并判明轻重。至此，我们已从理论上论证了用三进制编码解决该问题的可行性。

3　利用编码找出特殊环的具体实现步骤  
　　通过以上分析可以看出，按照上述规则选码时，要做到Ai＝1与Ai＝2(i＝2，3，…，n)的码数目相同是完全可能的。不过随着n的增大，选码的难度将越来越大。当n大到一定程度时，要在短时间内选出这样的码根本不可能。那么这个问题应该如何解决呢?  
　　实际上，由于每次称量后均有一个判别过程，所以具体实现并不需要把每个环都严格按照最初的编码来进行称量，完全可以利用每次称量的判别结果将下一次的搜索范围缩小，就可进一步缩小称量范围。因此，我们要保证每次称量时天平两边小环数目相同，不必使最初的编码中Ai＝1与Ai＝2(i＝2，3，…，n)的码数目相同。因为从第2次称量开始，就可以利用前面称量判别出的普通环，来弥补最初的编码在这个要求上的漏洞。当然，这样就有一部分普通环节并不按照预先的编码来进行称量。不过这并没有关系，因为我们的目的仅仅是找出特殊环并判明轻重。  
　　下面先给出具体的选码和称量步骤，然后再对其进行一些必要的数学证明。  
　　选码步骤如下：  
　　(1) 令Pn为所有n位三进制码的集合，根据A＝(A1，A2，…，An)的第1位A1＝0，A1＝1，A1＝2来将其分成3组Pn0、Pn1、Pn2，再从Pn0中删去A＝(0，0，…，0)，则Pn0中有3n－1－1个码，Pn1、Pn2中各有3n－1个码。  
　　(2) 从Pn1中取出(3n－1－1)/2个码。然后在Pn2中将已取出的Pn1中码的对称码删去，其余码取出，还应再删去1个，以保证A1＝1与A1＝2的码数目相同。同时，这些从Pn1和Pn2中选出的码还必须满足如下规则：  
　　a.在从Pn1和Pn2中选出的全部码中，若A2＝1与A2＝2的码都存在，则从Pn1和Pn2中选出的全部码中，A2＝1的最少数目与A2＝2的的最少数目均应为不小于(1+3n－2)/4的最小整数；  
　　b.在从Pn1和Pn2中选出的全部码中，若A2＝1(或A2＝2)的码不存在，则从Pn1和Pn2中选出的全部码中，A2＝2(或A2＝1)的码最多只能取(3n－1－1)/2个。  
　　(3)从 Pn0中任取(3n－1－1)/2个码，且其中无相互对称的码。  
　　经过选码，编码为A1＝0、A1＝1、A1＝2的环的数目均为(3n－1－1)/2个，各占环总数［(3n－1)/2］－1＝3×(3n－1－1)/2的1/3。  
　　称量步骤如下：  
　　(1)第1次将编码为A1＝1的环全部放在天平左边，将编码为A1＝2的环全部放在天平右边，编码为A1＝0的环全部不上天平。  
　　(2)根据第1次称量后的结果，我们可以判别出一部分环(至少是总数的1/3)是普遍环。于是第2次就可将搜索范围缩小到可能包含特殊环的那部分环中，在这些属于搜索范围的环中，将编码为A2＝1的环全放在天平的左边，编码为A2＝2的环全放在天平右边，编码为A2＝0的环全部不上天平。按此要求摆放后，若天平两边环数不等，就可在某边补放上已判别出的普通环以使其相等。  
　　说明1：选码步骤中的规则a和规则b已能保证，在第2次称量时，普通环的数目一定能够补足天平两边环数相等。后面将对其给予证明。  
　　(3)根据第2次称量后的结果，又可以判别一部分环是普通环。于是第3次就可将搜索范围进一步缩小。在这些可疑的环中，将编码为A3＝1的环全放在天平左边，编码为A3＝2的环全放在天平右边，编码为A3＝0的环全部不上天平。按此要求摆放后，若天平两边环数不等，就可在某边补放上已判别出的普通环以使其相等。  
　　说明2：若称量次数n≥3，则在按前述步骤进行的前提下，从第3次称量开始，每次称量时，由前面的称量判别出的普通环的数目已必定能够补足步骤中所述天平两边环数不等的情况。后面将其给予证明。  
　　其余步骤类同。  
　　结论如下：最后一次称量结束后，得到称量结果的编码B，则在处于最后一次搜索的那些环中，必有一个小环的编码为A＝B或A＝B′，这个环就是特殊环。若其编码是A＝B，则特殊环较轻；若其编码是A＝B′，则特殊环较重。当然有时在称量过程中即可预先判出其轻重。在称量过程中，对于那些曾属于搜索范围的小环，在它们因被判别出是普通环，而从搜索范围中被剔除以前，都是严格按最初的编码进行称量的。所以，只有那些属于最后一次搜索范围的小环才是完全按最初的编码进行n次称量。因此，对于这些小环的编码而言，每个码仍满足唯一且无对称码的规定。所以根据前面已论证的理论，在这些环中，那个编码为A＝B或A＝B’的小环是特殊环。

4　具体步骤中相关的证明  
4.1　说明1的证明  
　　规则a和规则b选码后，就能保证在第2次称量时有足够的普通环来弥补因按编码规则摆放而造成的天平两边小环数的不等。  
　　证明：首先进行一些基本分析。Pn1中共有3n－1个编码，其中A2＝0、A2＝1与A2＝2的码各有3n－1/3＝3n－2个；Pn2中情况相同。设n次称量的总环数为N＝［(3n－1］/2］－1＝3×3(n－1－1)/2，按我们的选码规则，应从Pn0、Pn1、Pn2中各选出N/3＝(3n－1－1)/2个编码。则第1次称量后至少能判别出(3n－1－1)/2个环是普通环。  
　　对此，分别就其在称量中可能出现的最坏情况，即已判出的普通环的数目最少而所有需用往天平上补放的普通环的数目最多的情况进行讨论。若最坏情况都能解决，则其余情况自然能解决。  
　　证规则a。其最坏情况是第1次称量的结果为不等，则由此只能判别出Pn0中选出的(3n－1－1)2个码所对应的环是普通环，是能差别出的最少数目；并且选码时从Pn1、Pn2中总共选出最少数目(设为X)的A2＝1(A2＝2)的码和此时能选的所有A2＝2(A2＝1)的码，则在第2次的搜索范围中，A2＝1的码数与A2＝2的码数差别最大，使得需要用于补放上天平的普通环数目最多。  
　　那么这个X为多大才能使最坏情况得以成功解决呢?分析后列出方程如下：  
　　2×3n－2－X＝(3n－1－1)/2+X　　(n≥2)  
解得：X＝(1+3n－2)/4，因为(1+3n－2)/4不一定是整数，所以这个最少数目X应为不小于(1+3n－2)/4的最小整数。  
　　证规则b。其最坏的情况是：第1 次称量的结果为不等，则由此只能判别出Pn0中选出的(3n－1－1)/2个码所对应的环是普通环，是能判别出的最少数目；并且从Pn1、Pn2中选码时，若不选A2＝1(A2＝2)的码，就从Pn1、Pn2中将A2＝2(A2＝1)的码按最多数目(设为Y)选出，则在第2次的搜索范围中，A2＝1的码数与A2＝2的码数差别最大，使需要用于补放上天平的普通环数目最多。  
　　那么，这个Y应为多大才能使最坏情况得以成功解决呢?经分析，对这种情况，在第2次称量时，天平的一边将全部都是由第1次称量判别的普通环共(3n－1－1)/2个，所以另一边能放的环数Y也最多只能是(3n－1－1)/2个。因此这个最多数目Y应为(3n－1－1)/2个。  
4.2　说明2的证明  
　　称量次数n≥3时，在按步骤进行的前提下，从第3次称量开始，每次称量时，由前面的称量判别出的普通环的数目已必定能够补足步骤中所述天平两边环数不等的情况。  
　　证明：首行进行一些基本分析。Pn1、Pn2中Ai＝1与Ai＝2(i＝3，4，…，n)的码均各有3n－2个。  
　　对此就其在称量中可能出现的最坏情况，即已判出的普通环的数目最少而所需用于往天平上补放的普通环的数目最多的情况进行讨论。若最坏情况都能解决，则其余情况自然能解决。  
　　其最坏情况的首要前提是：第1次称量的结果为不等，即由此只能判别出Pn0中选出的(3n－1－1)/2个码所对应的环是普通坏，是能判别出的最少数目。下面分2种情况进行证明。  
　　(1) 若第2次称量的结果为相等，则最坏情况即第2次称量判别出的普通环最少的情况应为：从Pn1、Pn2中选出的全部码中包含尽可能多的A2＝0的码的情况。因为第2次称量结果相等，则编码为A2＝1与A2＝2的小环就是普通环，而此时Pn1、Pn2中选出的全部码中即第2次搜索范围中，A2＝1与A2＝2的码的总数是最少的情况，所以是最坏的情况。  
　　考虑到选码时无对称码的要求，从Pn1、Pn2中总共能选出的最多的A2＝0的码为3n－2个；而相应地，此时从Pn1、Pn2中选出的A2＝1与A2＝2的码的总数，亦即通过第2次称量能判别出的普通环数为2×(3n－1－1)/2－3n－2＝2×3n－2－1个。因为第1次称量判别普通环数为(3n－1)－1/2个，所以第2次称量后，2次称量总共判别出的普通环数目为(3n－1)－1/2+2×3n－1－1＝(7×3n－1－3)/2个。由分析可知，从第3次称量开始，每次称量时，随着搜索范围缩小，所需往天平上补放的普通环数目的最大值应小于2×3n－2个。  
　　因为(7×3n－2－3)/2＞2×3n－2　　(n≥3)，所以得证。  
　　(2) 若第2次称量的结果为不等，则最坏情况即第2次称量判别出的普通环最少的情况应为：从Pn1、Pn2中选出的全部码中包含尽可能少的A2＝0的码的情况。因为第2次称量结果不等，则编码为A2＝0的小环就是普通环，而此时Pn1、Pn2中选出的全部码中即第2次搜索范围中，A2＝0的码的总数是最少的情况，所以是最坏的情况。  
　　考虑到选码时无对称码的要求，从Pn1、Pn2中总共能选出的最少的A2＝0的码为2×(3n－1－1)/2－2×3n－1＝3n－2－1个。这个数目也就是通过第2次称量能判别出的普通环数目。因为第1次称量判别出的普通环数目为(3n－1－1)/2个，所以第2次称量后，2次称量总共判别出的普通环数为(3n－2－1)/2+3n－2－1＝(5×3n－1－3)/2个。由分析可知，从第3次称量开始，每次称量时，随着搜索范围缩小，所需往天平上补放的普通环数目的最大值应小于2×3n－2个。  
　　因为(5×3n－2－3)/2≥2×3n－2　　(n≥3)，所以得证。  
　　上面对具体操作中的整体选码和称量过程进行了严格证明。这样，按照上述步骤，就能方便快捷地找出特殊环，并判明其较普通环是轻还是重。

5　启示  
　　如果把称环游戏中所有的小环作为整体看成一个系统，把混在众多普通环中的那个特殊环看成是系统中的的故障，那么，从小环中找出那个特殊环并判明轻重就可以看成从系统中找出故障并查明其性质。我们已经成功地运用编码解决了这个问题，由此得到启示，今后在遇到从系统尤其是数字系统中寻找故障的问题时，就可以考虑运用编码来解决。