参考阅读: www.cut-the-knot.org/blue/weight3.shtml
问题：N 枚硬币，其中一枚为假币。假币与真币的唯一区别是重量不同，但是不知道假币更轻还是更重。用一个天平，最少称几次可以保证找出这枚假币，并确定它是更轻还是更重？设计一个通用的解法。
常见的例题包括：N = 3，N = 12，等等。
每次用天平比较时，相当于把硬币分为三份：天平两侧各一份，其余硬币为一份。如果天平是平衡的，则假币在其余硬币那一份中；如果不平衡，则假币在天平某一侧的一份中，若假币更轻，则假币在更轻的一份中，否则在更重的一份中。因此，容易想到基于三进制的编号来解决这道问题。
核心的想法是，设法用同一套编号，既表示硬币编号，也记录每次天平比较的结果。第二点非常容易做到，只需要每次天平称量时，记录天平左侧的结果：用 A 表示天平左侧较轻（above），B 表示天平左侧较重（below），C 表示天平两侧平衡。得到的字符串记为 result。
为了让每次称量都能获得尽可能多的信息，我们设法让每次称量都确定硬币的三进制编号中的一位。由此反推，每次称量时，硬币分组的依据就应该是它的三进制编号的某一位。即，该位为 A 的硬币都在天平左侧，该位为 B 的硬币都在天平右侧，该位为 C 的硬币不放在天平上。于是，每一位是 A 或 B 的硬币数应该相等。
只要我们知道假币是更轻还是更重，就可以由之前记录的称量结果字符串 result 确定假币的编号。如果第 k 位是 C，显然假币的第 k 位就是 C。如果是 A（或 B），则表明第 k 位为 A （或 B）的硬币整体更轻：如果假币更轻，这就是我们所需的编号；如果假币更重，则交换 A 和 B 才是我们想要的编号。
在 result 中，将所有 A 改成 B，所有 B 改成 A，得到的字符串记为 resultB。如果假币更轻，它的编号就是 result；否则，答案是 resultB。换句话说，如果知道了假币是轻是重，就可以唯一确定假币的三进制编号。
问题是，我们并不知道假币是更轻还是更重，因此只能将答案缩小到 result 和 resultB 这两个候选。如何确定是哪一个？很简单，我们只要保证硬币的编号只包括 result 和 resultB 两者之一，它们不会同时出现在编号中。换句话说，我们需要将所有可能的编号划分为两类，只使用其中的第一类作为硬币的编号，而第二类都可以由第一类对换 A 和 B 得到。这里我们采用的划分标准是：对三进制编号字符串，考虑第一处相邻两位不同的字符，如果是 AB, BC, CA 之一，则为第一类，如果是 BA, CB, AC 之一，则为第二类。显然两类字符串总数相等，且很容易相互转换。这里，我们不考虑全相同的字符串（每次天平称量时它都位于同一侧）。
易知，n 位的三进制串至多可以对 (3^n - 3) // 2 枚硬币编号。反过来，对 N 枚硬币，最少的称量次数等于最短的编号长度，为 n = ceil(log(2*N+3, base=3))。
到此为止，我们的解法就基本构造完成了。下面就用之前说的两个例子来演示一下。
例一： 3 枚硬币，需要的编号长度和称量次数都为 2。
- 首先，将硬币编号为 AB, BC, CA。
- 第一次称量：左AB，右BC，剩余CA。
- 第二次称量：左CA，右AB，剩余BC。
如果 result 字符串为 AB，即第一次左轻右重，第二次左重右轻，那么假币编号就是 AB（轻）或 BA（重）。AB 就在硬币编号中，因此假币正是 AB，它比真币更轻。
例二：12 枚硬币，需要的编号长度和称量次数都为 3。
- 首先，将硬币编号为 AAB，ABA，ABB，ABC，BBC，BCA，BCB，BCC，CAA，CAB，CAC，CCA。
- 第 k 次称量，第 k 位编号是 A 的硬币在天平左侧，是 B 的硬币在右侧，剩余是 C 的硬币。
如果 result 字符串为 ACB，那么假币编号就是 ACB（轻）或 BCA（重）。其中 BCA 在硬币编号中，因此假币是 BCA，它比真币更重。