問題
\(n\)を正の整数とする。JMO王国には\(2^{n}\)人の国民と1人の王がいる。また、JMO王国では貨幣として\(2^{n}\)円の紙幣と\(2^{a}\ (a=0, 1, 2, … , n-1)\)円硬貨を取り扱っている。全ての国民は紙幣をいくらでもたくさん持っており、また、国民が持っている硬貨の枚数の挿話は\(S\)枚であった。さて、ある日からJMO王国では次の徴税と呼ばれる操作を毎日行うようになった。
- すべての国民は毎朝自分の持っている貨幣のうち、有限枚を選び、その日の夜にそれぞれの貨幣を他の国民または王に渡す。
- この際、すべての国民について渡した金額が渡された金額よりちょうど1円多くなるようにする。
JMO王国では以後、永遠に徴税を行い続けることができるという。このとき、Sとしてありうる最小の値を求めよ。
回答
問題の取っ掛かりとしては、「永遠に徴税を行い続けることができる」という点にあります。すなわち、「同じ形の繰り返し」が行われる必要があるわけです。硬貨の枚数に限りがあることから、硬貨を王に渡すような徴税はありえないはずです。また、国民の中だけでこの徴税が完結することもありえません。はじめにこれら二つのことを証明します。
硬貨を王に渡す徴税はSを最小にしないことの証明
もし、ある徴税システムがあって、それを満たす最小のSが発見されたとします。このとき、そのシステムのうちのどこかで、国民が王に硬貨をN枚(\(N\geq1\))渡すと国民の合計の硬貨の枚数は\(S-N\)枚となり、徴税システムを続けることができなくなります。よって、国民が王に硬貨を渡すことはありません。
国民の中だけで徴税が完結することはないことの証明
この証明に入る前に、国民が税を与える相手と徴税を受け取る相手は異なることを示します。もし、A国民とB国民がいて、AとBが互いに税のやり取りをすると、徴税システムのうち、「渡した金額が渡された金額よりちょうど1円多くなる」というルールが満たされません。ゆえに、国民が税を与える相手と徴税を受け取る相手は異なることがわかります。
さて、国民の中だけで徴税が完結するします。このとき、最初に税を与えた国民を\(A_{1}\)でその金額を\(a_{1}\)円とします。 \(A_{1}\)国民が税を与える国民を\(A_{2}\)、\(A_{2}\)国民が税を与える国民を\(A_{3}\)、… 、のようにし、最終的に\(A_{1}\)国民に税を与える国民を\(A_{n}\)とします。このとき、\(A_{n}\)が支払う税金は\(a_{1}+n-1\ (n-1\geq1)\)であり、やはり徴税システムのルールを満たすことができません。ゆえに国民の中だけで徴税が完結することはありえません。
以上の事実から、少なくとも一人の国民は王に対して「紙幣」によって税を支払う必要がある、ということがわかります。この国民を\(N_{0}\)とします。Sを最小にするためには、この金額は最小でなければならないので、税は\(2^{n}\)円1枚を選ぶことになります。また、\(N_{0}\)は\(N_{1}\)から\(2^{n}-1\)円をもらいます。同様に、\(N_{1}\)は\(N_{2}\)から\(2^{n}-2\)円をもらいます。このように\(N_{k}\ (k\geq1)\)国民は\(N_{k-1}\ (k\geq1)\)国民に\(2^{n}-k\)円を渡し、\(N_{k+1}\ (k\geq1)\)国民から\(2^{n}-k-1\)円を受け取るというシステムができます。
次に、具体的にどのような硬貨でこの税を支払うかを考えます。Sを最大にする場合は\(N_{0}\)国民が硬貨を持たず、\(N_{k}\ (k\geq1)\)国民がそれぞれ1円硬貨を\(7-k\)枚持っていれば良いです。このとき、全ての税を1円硬貨で支払えば、各国民がもつ硬貨の枚数は循環し、\(N_{k}\)のナンバリングを再定義することで再び徴税を行うことが可能です。
次にSを最小にする場合を考えます。Sを最小にするには、1円硬貨をできる限りそれ以上の硬貨に両替すれば良いです。この「両替」は10進数を2進数に置き換えることに対応し、最終的な硬貨の枚数は2進数で表した時の1の数の総和で表せます。すなわち、今の場合、\(1\to2^{n}-1\)までの10進数を全て2進数に置き換え、置き換えた2進数に現れる全ての1の数を足し上げれば、最小のSを求めることができます。
一般にnけた以下の全ての2進数に現れる1の数の総和は\(n\times2^{n-1}\)です。これを示します。
nけた以下の全ての2進数に現れる1の数の総和は\(n\times2^{n-1}\)である証明
nけたの2進数において、1をa個用いたものは\(_{n}C^{a}\)だけ存在するのでaについての和をとれば
$$\sum_{a=0}^{n}a\times_{n}C_{a} = \sum_{a=1}^{n}a\times_{n}C_{a}$$
$$\sum_{a=1}^{n}n\times\frac{(n-1)!}{((n-1)-(a-1))!(a-1)!}$$
$$\sum_{a^{\prime}=0}^{n-1}n\times\frac{(n-1)!}{((n-1)-a^{\prime})!a^{\prime}!} = n\times2^{n-1}$$
ゆえに、求める最小のSは\(n\times2^{n-1}\)です。
追記
先ほどの議論で登場した「循環」と「両替」のところを具体例を使ってみてみます。わかりやすく\(n=2\)で考えましょう。このとき国民はA, B, C, Dの4人います。最初の硬貨の枚数は、次のようにします。
- Aが0枚
- Bが1円硬貨1枚
- Cが1円硬貨2枚
- Dが1円硬貨3枚
このときAが王に4円紙幣を渡すとします。すると、DがAに1円硬貨を3枚渡し、CがDに1円硬貨を2枚渡し、BがCに1円硬貨を1枚渡します。結果次のように硬貨の枚数が変化します。
- Aが1円硬貨3枚
- Bが1円硬貨0枚
- Cが1円硬貨1枚
- Dが2枚
このように循環するので、次はB→王, A→B, D→A, C→Dのように税を支払えば良いことがわかります。これは永遠に繰り返されます。
次に、Sを最小にする「両替」です。Sを最小にする場合は、今の例の場合ですと、1円硬貨2枚を2円硬貨1枚に変え、1円硬貨3枚を2円硬貨1枚と1円硬貨1枚に変えれば良いです。すると次のように硬貨の枚数がわかります。
- Aが0枚
- Bが1円硬貨1枚
- Cが2円硬貨1枚
- Dが1円硬貨1枚と2円硬貨1枚
この状態でも先ほどの循環は成立し、かつこれ以上硬貨の枚数の合計を小さくすることができないので、これが\(n=2\)の場合の解となります。それでは\(n=3\)の場合はどうでしょうか。
- Aが0枚
- Bが1円硬貨1枚
- Cが1円硬貨2枚
- Dが1円硬貨3枚
- Eが1円硬貨4枚
- Fが1円硬貨5枚
- Gが1円硬貨6枚
- Hが1円硬貨7枚
ですので、Sを最小にするには次のように「両替」すれば良いでしょう。
- Aが0枚
- Bが1円硬貨1枚
- Cが2円硬貨1枚
- Dが1円硬貨1枚、2円硬貨1枚
- Eが4円硬貨1枚
- Fが1円硬貨1枚、4円硬貨1枚
- Gが2円硬貨1枚、4円硬貨1枚
- Hが1円硬貨1枚、2円硬貨1枚、4円硬貨1枚
これを計算していていると、2進法の計算とリンクさせることに気づくのではないでしょうか。
- Aが0枚 (\(0_{2}\))
- Bが1円硬貨1枚 (\(1_{2}\))
- Cが2円硬貨1枚 (\(10_{2}\))
- Dが1円硬貨1枚、2円硬貨1枚 (\(11_{2}\))
- Eが4円硬貨1枚 (\(100_{2}\))
- Fが1円硬貨1枚、4円硬貨1枚 (\(101_{2}\))
- Gが2円硬貨1枚、4円硬貨1枚 (\(110_{2}\))
- Hが1円硬貨1枚、2円硬貨1枚、4円硬貨1枚 (\(111_{2}\))
そして、2進法で表した時の1の数の合計がそれぞれの国民が持っている硬貨の枚数です。ゆえに全国民が所持する硬貨の枚数は、1の数の合計を数えれば良いです。\(n=3\)の時、一人の国民が所持する硬貨の合計金額は2進法で3けたであり、2進法で3けた以下の数の1の総和は\(3\times4 = 12\)です。
コメント