書記が数学やるだけ#907 バシェの分銅問題，無限の猿定理

記数法にまつわる問題を2つ扱う。

問題

無限の猿定理（infinite monkey theorem）とは、十分長い時間をかけてランダムに文字列を作り続ければ、どんな文字列もほとんど確実にできあがるという定理である。これに関連した話題として，「桁数が増加するにつれ、任意の数字列 w がどこかに出現する確率が 1 に近づく」ことを示す。

説明

バシェの分銅問題は、17世紀フランスの数学者クロード・バシェ・ド・メジリアックが提起した、天秤を用いて任意の重さを測るために必要な分銅の最小セットを問うパズルである。バシェの問題が扱うのは天秤であり，分銅の重さ w は測定される重さに対して「足す」だけでなく「引く」ことも可能である。

無限の猿定理に関連する事項として，数学における正規数（normal number）とは、実数のうち、その小数部の数字が一様に分布し、数字の列が現れる頻度に偏りがないものをいう。

解答

セットA：1,2,4,… (2 の冪) の分銅の場合，1を乗せるor乗せない，2を乗せるor乗せない，…とおくことで全ての整数を表せる。一方でセットB：1,3,9,… (3 の冪) の分銅の場合，1を左に乗せる（+）or右に乗せる（-）or乗せない，3を左に乗せる（+）or右に乗せる（-）or乗せない，…とおくことで全ての整数を表せる。ここで10までを表すのに必要な分銅の数について，セットAでは4つ必要なところ，セットBでは3つに減らすことができる。

任意の重さ N は、まず通常の三進法で表現した後に、繰り上げと負の桁（−1）を導入する操作を行うことで、係数が {−1,0,1} となる平衡三進法の形に必ず変換できる（存在証明）。

さらに、その表現がただ一つであることを示すために、背理法を用いる。すなわち、もし異なる 2 つの表現が存在すると仮定し、その差を計算してゼロに等しいと置くと、最上位の非ゼロの桁の重みが下位の桁の重みの総和を上回るため、整数性の矛盾が生じる。これにより、任意の整数 N の平衡三進法表現は一意に定まることが示される。

d個の分銅は左・右・乗せないの3通り乗せ方があり，正整数のみ数えることでM(d)が求められる。これが最大であることは，繰り上がりと負の係数の操作が整合的に機能するのは基数3の場合のみであることなどから示せる。

9が出てこない整数の数は，一見すると約10分の1の整数を取り除くだけに見えるが、実際には桁数が増えるにつれてその割合は急速に減少し，最終的に k→∞ では 0 に収束する。

さらに強い主張として，9を含まない整数の逆数和は収束することが言える。

より一般に，「桁数が増加するにつれ、任意の数字列 w がどこかに出現する確率が 1 に近づく」ことを示すことができる。

本記事のもくじはこちら：