第一次1234vs5678
第二次19ABvs2345
第三次269Cvs137A
(十二个球记作123456789ABC,解法不唯一)
大家可以验证一下每个球异常对应的结果都不同,这就意味着这样称可以辨别出来。那么这种称法是怎么得到的呢?
注意总共有24种情况,称三次每次三种结果共27种(以0代表左边重,1代表右边重,2代表平,那么结果就是一个三进制三位数),我们只要让每种情况都对应上不同的结果就能从结果辨别出到底是哪一种情况。我们把x号球偏重的情况记作「x重」,偏轻类似。
显然,假如情况「1重」对应结果001,那么「1轻」就会对应110。类似地,我们只需要把重的情况对应的结果设置一下就行了,这样轻的情况对应的结果自然也就确定了(只要把01反过来2不变即可)。这样我们就只用设置12种情况对应的结果了。
另外,假如「x重」对应结果012,那x号球肯定第一次上左边盘,第二次上右边盘,第三次不上天平。所以我们不能随便设置对应,必须保持每次天平左右盘球数相等,也就是0在任一位出现次数与1在那一位出现次数相等。
为达到此目标,我们可以考虑设置这12种情况对应的结果使得每一位恰出现四个0四个1四个2。那么到底怎么设置呢?
可以用如下方法。比如我想让「1重」对应001,那么我也要让「x重」对应112,「y重」对应220,对某个x,y。(在我的答案中「5重」对应112,「C重」对应220)现在已经有三个了。还要九个。比如我想让「2重」对应010(为什么不能对应002?因为它已经被「5轻」对应了,要避开),那么我也让「7重」对应121,「B重」对应202。(知道我的办法了吗?)这样,只要一设置一个情况对应的结果,就把那个结果加上111不进位后得到的结果也让某个情况对应,这样就能保证每一位012各有4个啦(要注意避开已经被那些「x轻」对应了的情况喔)。接下来的过程我不再赘述,最后得到的对应是:
1—001
2—010
3—011
4—012
5—112
6—120
7—121
8—122
9—200
A—201
B—202
C—220
再把每一位的0放到左盘1放到右盘就得到一开始那个答案啦!
这种方法看上去比较麻烦,但是它可以推广到任何(3^n-3)/2称n次得出答案,而且还可以O(n3^n)实现哟(不能更少,因为你总共就要输出O(n3^n)个数)。
-----------------------------------------
我也能用严格的数学语言写 = = 然而这样子应该更不容易看懂 = =