すのものの「ニセ金貨とてんびんのパズル」

問題. k を 3 以上の整数とする。k 枚の金貨があり、 そのうち k-1 枚は同じ重さであるが残りの 1 枚は（ごくわずかだけ）重さが違う。 ほかに、 左右どちらの皿に乗せたものが重いかだけを知ることのできるてんびんがある。 このてんびんを使って重さの違う金貨を見つけ出すには、 何回てんびんを使う必要があるか？

答え. 正の整数 n が n-1 < log₃(2k + 1) <= n を満たすとき n 回である。 この式を書きかえれば (3^n-1 - 1) / 2 < k <= (3ⁿ - 1) / 2 となる。

重さの違う金貨を「求める金貨」、 てんびんの左右の皿に金貨を乗せてどちらが重いかを知ることを 「比較」と呼ぼう。

何回かの比較のあとでは、 「もしもこれが重さの違う金貨であるなら『より重い』」 「もしもこれが重さの違う金貨であるなら『より軽い』」 とわかることがある。 それらの金貨にはそれぞれ「重いかも」「軽いかも」の「目印」をつける。 ここで「目印」と言ったらこの意味に限る。 求める金貨でないことが判明した金貨を「普通の金貨」と呼ぶ。

補題 X. 0 以上の整数 n と正の整数 k が 3^n-1 < k <= 3ⁿ を満たしている。 k 枚の金貨があり、 それらの中には一枚だけ重さが（ごくわずかだけ）違う金貨が含まれている。 それ以外の金貨は同じ重さである。 さらに、全ての金貨に 「重いかも」「軽いかも」のどちらかの目印がついている。 このとき、てんびんを n 回だけ使って重さの違う金貨を見つけ出せる。 ただし、k = 2 で「重いかも」「軽いかも」が 1 枚ずつの場合は除く。

証明： n = 0 のとき k = 1 である。このときは正しい。 n = 1 のとき k = 2, 3 である。 k = 3 のときは同じ目印のついた金貨を天秤の左右の皿に乗せて比較すればよい。

n >= 2 のときを考える。k > 3 である。 これらの金貨を“ほぼ三等分”する。すなわち、 k = 3j, 3j+1, 3j+2 （j は正の整数）のどれが成り立つかに従って

• k = 3j のとき
  • 第一群 j 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 1 のとき
  • 第一群 j+1 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 2 のとき
  • 第一群 j 個、
  • 第二群 j+1 個、
  • 第三群 j+1 個

• 上で指定した各群の枚数は正であることに注意する。 まず、第一群を選ぶが、 その際、指定された枚数より一つ少ない枚数までは、適当に選ぶ。 最後の一枚を選ぶ際には、残りのうちで 「重いかも」「軽いかも」のどちらか一方のみが奇数枚であるから、 奇数のほうから選ぶ。 そして、残りのうちの 「重いかも」から半分を選び出したものと 「軽いかも」から半分を選び出したものとを合わせて第二群とし、 残りを第三群とする。

• つりあった場合、求める金貨は第一群に含まれる。
• つりあわなかった場合、 求める金貨は重かったほうの「重いかも」と軽かったほうの 「軽いかも」を合わせたもの --- それらの枚数は第二群・第三群の枚数と同じ --- に含まれる。

• k = 3j のとき 3j <= 3ⁿ より j <= 3^n-1.
• k = 3j+1 のとき 3j+1 <= 3ⁿ の右辺は 3 の倍数なので左辺も 3 の倍数に切り上げて 3j+3 <= 3ⁿ, ゆえに j+1 <= 3^n-1.
• k = 3j+2 のとき 3j+2 <= 3ⁿ の右辺は 3 の倍数なので左辺も 3 の倍数に切り上げて 3j+3 <= 3ⁿ, ゆえに j+1 <= 3^n-1.

いずれにせよ、n がより小さい場合に帰着する。 ただし、 「重いかも」「軽いかも」が 1 枚ずつの場合に帰着してしまったら、 いま求める金貨でないと判明した金貨を「重いかも」と比較する。

［証明了］

注：「重いかも」3 枚と「軽いかも」2 枚の計 5 枚の場合は、 上のやり方では「重いかも」「軽いかも」 が 1 枚ずつの場合に帰着する可能性がある。

補題 Y. 0 以上の整数 n と自然数 k が (3^n-1 + 1) / 2 < k <= (3ⁿ + 1) / 2 を満たしている。 k 枚の金貨があり、 それらの中には一枚だけ重さが（ごくわずかだけ）違う金貨が含まれている。 それ以外の金貨は同じ重さである。このとき、 これとは別に普通の金貨が一枚あれば、 天秤を n 回だけ使って重さの違う金貨を見つけ出せる。

証明： n = 0 のときは k = 1 である。この場合には正しい。 n = 1 のときは k = 2 である。 この場合はどちらかを普通の金貨と比較すればよい。

n >= 2 とする。k >= 3 である。 これらの金貨を“ほぼ三等分”する。すなわち、 k = 3j, 3j+1, 3j+2 （j は正の整数）のどれが成り立つかに従って

• k = 3j のとき
  • 第一群 j 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 1 のとき
  • 第一群 j+1 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 2 のとき
  • 第一群 j+1 個、
  • 第二群 j+1 個、
  • 第三群 j 個

• k = 3j のとき 6j <= 3ⁿ + 1, よって 6j <= 3ⁿ + 3 より j <= (3^n-1 + 1) / 2.
• k = 3j + 1 のとき 6j + 2 <= 3ⁿ + 1 より 6j + 6 <= 3ⁿ + 5, 左辺は 6 の倍数であり右辺は 6 で割ると 2 余ることから 6j + 6 <= 3ⁿ + 3, j+1 <= (3^n-1 + 1) / 2.
• k = 3j + 2 のとき 6j + 4 <= 3ⁿ + 1, 6j + 6 <= 3ⁿ + 3, よって j+1 <= (3^n-1 + 1) / 2.

• k = 3j のとき 6j <= 3ⁿ + 1, 左辺は 6 の倍数であり右辺は 6 で割ると 4 余るので 6j <= 3ⁿ - 3, よって 2j <= 3^n-1 - 1 <= 3^n-1.
• k = 3j + 1 のとき第一群に関する計算結果から。
• k = 3j + 2 のとき第一群に関する計算結果から。

k = 3j のときおよび k = 3j + 1 のときは第二群と第三群をてんびんで比較する。 k = 3j + 2 のときは、 第二群と、第三群に普通の金貨を加えたものとをてんびんで比較する。

• つりあった場合、求める金貨は第一群に含まれている。 n がより小さい場合に帰着した。
• つりあわなかった場合、 重かったほうの皿に乗せた金貨のうち普通の金貨以外のものに「重いかも」、 軽かったほうの皿に乗せた金貨のうち普通の金貨以外のものに「軽いかも」 の目印をつけ、これらの金貨に補題 X を適用する。 ただし、 「重いかも」「軽いかも」が 1 枚ずつの場合は、 そのどちらかと普通の金貨とを比較する。

［証明了］

定理 Z. 2 以上の整数 n と 3 以上の整数 k が (3^n-1 - 1) / 2 < k <= (3ⁿ - 1) / 2 を満たしている。 k 枚の金貨があったとし、 それらの中には一枚だけ重さが（ごくわずかだけ）違う金貨が含まれているとする。 それ以外の金貨は同じ重さである。このとき、 天秤を n 回だけ使って重さの違う金貨を見つけ出せる。

証明： 金貨を“ほぼ三等分”する。すなわち、 k = 3j, 3j+1, 3j+2 （j は正の整数）のどれが成り立つかに従って

• k = 3j のとき
  • 第一群 j 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 1 のとき
  • 第一群 j+1 個、
  • 第二群 j 個、
  • 第三群 j 個
• k = 3j + 2 のとき
  • 第一群 j 個、
  • 第二群 j+1 個、
  • 第三群 j+1 個

• k = 3j のとき 3j <= (3ⁿ - 1) / 2 より j <= (3^n-1 - 1/3) / 2 だから。
• k = 3j + 1 のとき 3j + 1 <= (3ⁿ - 1) / 2 より 3j + 3 <= (3ⁿ + 3) / 2, j + 1 <= (3^n-1 + 1) / 2.
• k = 3j + 2 のとき 3j + 2 <= (3ⁿ - 1) / 2 より 3j <= (3ⁿ - 5) / 2, j <= (3^n-1 - 5/3) / 2 だから。

• k = 3j のとき 3j <= (3ⁿ - 1) / 2 より 6j <= 3ⁿ - 1, 左辺は 6 の倍数であり右辺は 6 で割ると 2 余るので 6j <= 3ⁿ - 3, よって 2j + 1<= 3^n-1.
• k = 3j + 1 のとき 3j + 1 <= (3ⁿ - 1) / 2 より 6j + 2 <= 3ⁿ - 1, 2j + 1 <= 3^n-1.
• k = 3j + 2 のとき 3j + 2 <= (3ⁿ - 1) / 2 より 6j + 4 <= 3ⁿ - 1, 左辺は 6 で割ると 4 余り、右辺は 6 で割ると 2 余るので 6j + 4 <= 3ⁿ - 5, これから 6j + 9 <= 3ⁿ, 2j + 3 <= 3^n-1.

• つりあった場合、第一群に補題 Y を使えばあと n-1 回で判明する。
• つりあわなかった場合、 第二群と第三群を合わせたものに第一群の金貨 --- 普通の金貨と判明した --- を一枚加えたものに補題 X を使えばあと n-1 回で判明する。

［証明了］