パズルの国のアリス

くじ引きによる景品分配(解答)

 グリフォン案の当たり条件は奇妙で,ちょっと聞いただけではわかりにくい。しかし,1番のボールを1個とすると,どの番号のボールも正の整数個を入れることで目的が達成できるのだ。そのことを納得するには,順次考えていくのがわかりやすいだろう。

 n番のボールの個数をBn)としよう。B(1)=1のときB(2)はいくつだろうか。2番の人が当たる条件は1番か2番のボールが取り出されることだから,B(1)+B(2)がB(1)の2倍であればよい。つまり,B(1)+B(2) =2B(1)だからB(2)=1となる。B(3)も同様に考えると,B(1)+B(3)=3B(1)よりB(3)=2だとわかる。さらにB(1)+B(2)+B(4)=4B(1)よりB(4)=2だ。

 一般には

が成り立つ。ここでknknを割り切ることを表す記号である。つまり,左辺は,nを割り切るすべての正整数k(つまりnの約数k)にわたってBk)の総和を取ることを意味する。この式より,Bn)は帰納的に

と計算でき,先述のように次々と値が求められる。読者には

B(5)=4,B(6)=2,B(7)=6,B(8)=4,B(9)=6,B(10)=4

を確かめたうえで,さらに先,例えばB(20)くらいまで求めていただきたい。だが,これらの値から一般のnについてBn)がどう表されるかを予測するのは簡単ではあるまい。nとの関係式からBn)が整数になることは自明だろうが,n以下の正の数になるということすらそれほど明らかではない。

 まず,nが素数pのべき,すなわち正の整数eによってnpeと書ける場合に

となることを指数eに関する数学的帰納法で示そう。pは素数だから,e=1のとき,p1pの約数は1とpだけである。したがって,Bn)の計算式より,確かにBp1)=p1−1=p1p0となる。e>1のときは,peの約数はp0p1p2,…,pe−1peがそのすべてだが,帰納法の仮定とBn)の計算式より

Bpe)=pe−(Bp0)+Bp1)+Bp2)+…+Bpe−1))=pe−{1+(p−1)+(p2p)+…+(pe−1pe−2)}=pepe−1

である。

 さて,一般の自然数nについてBn)はどう書けるだろうか? そのためにはBの乗法性に気がつくことがポイントだ。自然数を定義域とする関数は「数論的関数」と呼ばれるが,そのような関数fが乗法性を持つとは,互いに素な任意のmnについてfmn)=fmfn)が成り立つこととして定義される。各素数のべきは明らかに互いに素であるから,Bが乗法性を持つならば,nの素因数分解をnp1e1p2e2prerとして,Bn)は

と書けることがわかる。

 そこでBの乗法性を示そう。すなわちmnが互いに素なときBmn)=BmBn)であることだ。証明は帰納法による。mn=1,すなわちmn=1のときは,定義よりB(1)=1=B(1)B(1)だから成り立つ。一般のmnの場合,nBn)の関係より

である。一方,

でもある。mnが互いに素であることから,mnの約数dは常にmの約数bnの約数cに一意に分解されてdbcと書け,このときbcは互いに素である。したがって帰納法の仮定より

となり,BmBn)=Bmn)が導かれる。

 実は,関数Bは,数論に詳しい人には馴染みのものだ。数列B(1),B(2),B(3),…やBn)の一般的表記を見て,そのことにお気づきになった読者もおられるだろう。オイラー(Leonhard Euler)が1761年に発見した「φ関数」とか「トーシェント関数」とか呼ばれるものである。nと互いに素なn未満の自然数の個数をφn) という記号で表記したのがその最初とされているが,ウィキペディアによれば江戸時代の将棋指しで和算家の久留島義太(くるしま・よしひろ)がその数年前に言及しているらしい。定義だけからは,Bn)がφn)に等しいことはそれほど明らかではないが,しかるべき数論の教科書を参照すれば,φn)が上述のBn)と同じ形の表記を持つことがわかるだろう。

問題はこちらです