晚上好！2024年的第40周！
本周的啊哈数是：𝟏𝟐。
有12个小球，重量互不相同，但是从外观上看不出区别。现在你手头的工具只有一个天平，它没办法像秤一样显示重量，只能通过天平的倾斜分析出两侧放置的物品谁重谁轻。如果每次只能把其中两个小球放到天平两侧看看哪个更轻哪个更重，最少用几次天平才保证可以给这12个小球从轻到重排序呢？
4小球排序问题
咱们先用个更简单的情况来分析一下问题。12个小球太多，就拿4个小球来说吧！不妨把它们记作A、B、C、D。前面说了，它们的重量各不相同。那这时候，为了保证可以完成按照重量的排序，至少需要使用几次天平呢？
当然，在运气最好的情况下，3次就够了。比如，第一次比较A、B，得到A比B轻；接下来比较B、C，正好得到B比C轻；最后比较C、D，正好得到C比D轻。这样的话，只用了3次天平就可以排出顺序：A<B<C<D。
所以3次就是答案咯？当然不是。谁能保证自己运气一定这么好呢！很有可能用了3次天平，我们只是缩小了范围，但根本无法完成排序。我们需要寻找保证可以完成排序的次数，那就不能用最好情况来算，而是要考虑最坏情况下最少使用几次天平。
为了保证能把4个小球按重量排序，最容易想到的办法当然就是每两个小球之间都比一下重量。如果每次选两个小球，那一共有6种组合：AB、AC、AD、BC、BD、CD。所以，我们至少可以得出，用6次天平肯定是足够了。可如果只用5次天平呢？能办到吗？
还真可以。其中一种方案如下：
第一次：把小球分成A、B和C、D两组。将A、B放在天平两端，得出谁轻谁重。
第二次：将C、D放在天平两端，得出谁轻谁重。
第三次：将两组中各自的较轻者放在天平两端，比出总的最轻者。
第四次：将两组中各自的较重者放在天平两端，比出总的最重者。
第五次：剩下的两个小球的重量一定夹在总的最轻者和总的最重者之间。把它们俩放在天平上称一下，就知道它们的轻重顺序。总的轻重顺序就确定了。
所以用5次天平是可以的咯！那4次呢？这回是真不能了，上面所说的已经是最佳方案了。我们可以利用信息论的方法从理论上证明，使用4次天平无法保证成功给4个小球的轻重排好顺序。
任何一种给小球排序的策略，本质上就是上图那样的树状图。4个小球的顺序一共有4×3×2×1=24种不同的可能，但每用一次天平只能产生两条分支，因而使用4次天平最多只能得到2⁴=16种可能的结局，这不足以区分24种情况。所以，只用4次天平是不够的。
综合上面的推理，我们就知道了，为了保证给4个小球的重量排好顺序，5次排序是必须的，也是足够的。
难倒众人的12小球排序问题
现在我们已经知道4个小球的排序问题如何解决了，5个小球也可以用类似的方法分析。5个小球的轻重一共有5×4×3×2×1 = 120种顺序，而2⁶ = 64，2⁷ = 128。这意味着，为了保证给5个小球的轻重排好顺序，使用6次天平肯定不够，理论上至少也得用7次天平。人们也确实找到了一种用7次天平保证排好顺序的方案。（你可以试着设计出符合要求的方案。有点难度哦！）对于6, 7, 8, 9, 10, 11个小球，也是类似的情况。
可就在大家信心满满地准备解决12小球排序问题的时候，事情变得棘手起来。12个小球的轻重一共有479001600种顺序，而2²⁸ = 268435456，2²⁹ = 536870912。这意味着，为了保证给12个小球的轻重排好顺序，使用28次天平肯定不够。但是，人们一直没找到使用29次天平保证完成任务的方案。
1965年，在计算机穷举的辅助下，我们才知道用29次天平也是不够的。为了保证完成任务，至少需要使用30次天平。
今天，我们利用天平的“倾斜”来给小球按重量排序。本周，小数点同学会的主题就是“倾斜”，看看数学中都有哪些和倾斜有关的内容吧！
这里是小数点同学会，小伙伴的数学据点。关注我们，每天五分钟，聊点儿小孩也能看懂的趣味数学。
