|
※クリックで全体表示。 
|
3月13日の19時9分頃、国際宇宙ステーション（ISS）が ［※追記］翌日に再度観察したところ、木星とシリウスを取り違えていたことが分かりました。訂正させていただきます。 |
|
Copyright(C)長谷川芳典 |
03月のインデックスへ戻る
最新版へ戻る
|
※クリックで全体表示。
|
3月13日の19時9分頃、国際宇宙ステーション（ISS）が ［※追記］翌日に再度観察したところ、木星とシリウスを取り違えていたことが分かりました。訂正させていただきます。 |
【小さな話題】フロベニウスの硬貨問題と「加法素数」 3月12日に公開されたYouTubeの解説動画で、 ●【フロベニウスの硬貨問題】小学生でも理解できるのに誰も解けない数学の超難問【ゆっくり解説】 という興味深い話題を取り上げていた。この話題は2022年7月20日に考察した内容に関連しておりなかなか奧が深い。 もともとの問題は ●7円玉と9円玉だけで48円以上の全ての金額の支払いができるか？ であり、より一般化すると、 ●a、bは互いに素、ｘ、yを整数とすると、Nより大きいすべての整数は、ax+byで表わすことができる。 ということになる。ちなみに、上記で「Nより大きい数」というのは、7円玉と9円玉の支払いに関して言えば「47円」がNに相当している。このことについては別に定理があり、 ●a、bを互いに素な自然数、x、yは0以上の整数とするとき、ax+byで表せない最大の整数は ab-a-b である。 ということが証明されている。じっさい7円玉と9円玉について言えば、a＝7、b＝9とすると、ab-a-b＝7×9−7−9＝47 となり、47円の支払いはできないことが分かる【証明はこちら参照】。 さて、2022年7月に考察した時は、私自身の興味は「すべての整数は、ax+byで表わすことができる」ということにあったのだが、今回の動画は「ax+byで表わすことができない最大数Nは？」というように視点が異なっていた。 このことでふと思ったが、そもそも素数というのは、1より大きい自然数a、bの積a×bで表すことができない数のことであるが、上記のNは、これに似ており「1より大きい自然数aとbの足し合わせで作れない数」となっており、いわば「加法素数」となっている。但し、
今回視聴した動画によれば、「加法素数」の最大値Nは「フロベニウス数（Frobenius number）」と呼ばれており、ウィキペディアによれば、フェルディナント・ゲオルク・フロベニウス（1849-1917）に因んで名づけられた。 上にも述べたように、aとbという2種類の硬貨の問題はすでに解決済であるが、 硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、（硬貨の種類の数の「対数」に対して）多項式時間でフロベニウス数を計算するアルゴリズムが存在する。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である。という点が興味深い。ウィキペディアのリンク先ではさらに、
余談だが、日本の現行硬貨は1、5、10、50、100、500円というようにかなり冗長になっている。あらゆる金額の支払いができるのは1円玉があるからで、通常1円〜4円の金額部分はその枚数の1円玉を支払うか、もしくはお釣りとして受け取ることで処理されている（5円玉を含む6円から9円も同様）。日本ではこのやりとりは普通に行われているが、外国で買い物をする時にはしばしばお釣りが無いと言われ、本来受け取れるはずのお釣り分を巻き上げられてしまうことがしばしばある。店の人もそれが当然であるというような顔をしている。ま、そういう点では、日本での釣り銭不足はそれほど顕著ではないように見える。むしろ釣り銭ばかり受け取っていると財布が膨れて入りきらなくなったりする。 |