二進法が隠された奇妙な整数問題(数学オリンピック日本本戦2016年第3問)を解いてみた。物理・数学の問題に少しでも近寄れるようになるために。【質問・悩みに回答します】ブログの趣旨ホームサイトマップお問い合わせ二進法が隠された奇妙な整数問題(数学オリンピック日本本戦2016年第3問)を解いてみた。2019.08.10問題\(n\)を正の整数とする。JMO王国には\(2^{n}\)人の国民と1人の王がいる。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_{n}\)とします。(n-1\geq1)\)であり、やはり徴税システムのルールを満たすことができません。ゆえに国民の中だけで徴税が完結することはありえません。以上の事実から、少なくとも一人の国民は王に対して「紙幣」によって税を支払う必要がある、ということがわかります。この国民を\(N_{0}\)とします。Sを最小にするためには、この金額は最小でなければならないので、税は\(2^{n}\)円1枚を選ぶことになります。\(N_{0}\)は\(N_{1}\)から\(2^{n}-1\)円をもらいます。同様に、\(N_{1}\)は\(N_{2}\)から\(2^{n}-2\)円をもらいます。(k\geq1)\)国民から\(2^{n}-k-1\)円を受け取るというシステムができます。次に、具体的にどのような硬貨でこの税を支払うかを考えます。(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\times2^{n-1}$$ゆえに、求める最小のSは\(n\times2^{n-1}\)です。先ほどの議論で登場した「循環」と「両替」のところを具体例を使ってみてみます。わかりやすく\(n=2\)で考えましょう。最初の硬貨の枚数は、次のようにします。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枚渡します。結果次のように硬貨の枚数が変化します。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進法の計算とリンクさせることに気づくのではないでしょうか。(\(111_{2}\))そして、2進法で表した時の1の数の合計がそれぞれの国民が持っている硬貨の枚数です。ゆえに全国民が所持する硬貨の枚数は、1の数の合計を数えれば良いです。数学オリンピックメネラウスの定理と補助線でオリンピック難角問題を解く。2003年数学オリンピック日本本戦第1問を解いてみました。メネラウスの定理・補助線をうまく使うと綺麗に解くことができます。整数問題を解く2009年の日本数学オリンピック本戦問題の第1問を解きます。整数問題で、旧帝大の大学入試問題の練習としても効果的だと思います。よろしければ、トライしてみてください。整数問題を解く第3回近畿大学数学コンテストの整数問題を解きます。数学コンテストのA問題は高校数学の知識で十分解くことができるように作られています。チャレンジしてみてください。スポンサーリンク空間図形の問題に対して、ベクトルで攻めるか初等幾何で攻めるか、を2001年の東京大学の問題を使って考えてみる。コメントをキャンセルメールアドレスが公開されることはありません。コメント名前メールアドレスサイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。最近のコメントカーティスの定理を高校数学の範疇で証明する。指導経験:塾講師として4年間。中学1年生から高校3年生まで経歴:文系の私立大学を卒業後、1年間予備校で勉強して、理系の国公立大学に進学。そのまま学部・修士を卒業、博士に進学。死ぬ前に食べたいもの:日○屋の担々麺コメント:眠らないウサギになれたらなぁ。質問・悩みお待ちしています。