小球称重问题

近期，syd 在准备面试的过程中，问了我一道小球称重问题。

我在上网学习之后，简单记录一下我的学习过程。

问题

给出 个小球，其中有一个球不正常，不过并不知道那个不正常的球是偏重的还是偏轻的。

现在有一个天平，要求通过至多三次称重，找出那个不正常的小球。

解法

首先随意拿出 个，然后分成两堆，每堆 个，放到天平上称。

如果天平上的两堆是相等的，那么说明不正常的球在剩下的 个中，这个时候问题变成了 个小球，两次称重，找出不正常小球的子问题，较为简单，留给读者思考。

那么下面我们考虑不正常的球在天平上的 个球中。

我们假定天平左边的 个球为 ，右边的 个球为 。

我们假定

与此同时，我们知道我们有已知的 个正常的球，标记为 。

那么在第二次称重当中，我们交换 和 的位置，并且用三个正常的球，替换 ，即天平上的排列变为：

下面分三种情况考虑。

第一种，我们假定；

说明有问题的球在 中，并且不正常的球偏轻。

第二种，我们假定：

说明有问题的球在 中，并且不正常的球偏重。

第三种，我们假定：

说明有问题的球是 。

那么对于给出 个球，并且知道不正常的球是偏轻还是偏重的情况下，给出一次称重机会，是较为容易去解的，此处留给读者思考。

---

Last update: May 3, 2022
Created: May 3, 2022