ウソブックス:Aとbが互いに素で、あるときのaとbだけの和で表せない最大の整数がab-(a+b)であることの雑な説明

出典: 究極の八百科事典『ウソペディア』
ナビゲーションに移動 検索に移動
事実を書きすぎな記事
この記事は嘘やユーモアも含まれてはいますが、8割方は事実を書いています。
ユーモアを付け足してくれる方を募集しています。

Twitterのトレンドになっていたから、自分も参加、証明はウソペディアらしく雑(だって嘘でも良いんだし。)表を元にした説明でも別に良いかなーと。かるーい読み物に タイトルの問題は、フロベニウスの硬貨交換問題として有名である。

フロベニウスの硬貨交換問題[編集 | hide | hide all]

見栄の為出来るだけ高価な互いに素な数種類の硬貨で、釣は取っときなと言いながら、釣り銭が出ないように、少額決済を繰り返す、エクストリームスポーツである。硬貨が3種類以上の場合の公式は未だ見つかっておらず、硬貨の種類に対して多項式時間で解けるアルゴリズムも見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である。一方で、2種類である場合は、以下のようにして、比較的容易に釣銭が出ない条件を定式化することができる。

硬貨の切手バージョンの問題として、郵政公社により切手販売促進の為、シルベスターの切手問題なるキャンペーンが開始されたが、郵政民営化により廃止された。

Twitterのトレンドに乗っかる[編集 | hide]

aとbが互いに素で、あるときのaとbだけの和で表せない最大の整数がab-(a+b)であることの、屁理屈。

が、有限としても一般性は失われない。

まず、 として自然数を

という形の行列に分ける。

同列にある隣接行の成分の差は常にであるから、あるにおいて、、つまりの倍数になったとすると、任意のにおいて、の形で表すことができる。…(*)

ここで、が互いに素である時、

で割った余りは全て異なり、その集合は明らかに個の非負整数で構成されているから、全ての以外の列にの倍数が入るには、までを計算すれば十分[1]である。


ここで、までの自然数において、で表現されない数を考慮するにあたっては、の倍数の列は明らかに除外してよい。

の列と、の倍数列以外の列については、より各行にの倍数は高々1回しか出現しないことから、の存在する行よりも上の行、かつ、を満たすあるについて、の倍数となる。

このことと(*)より、の一つ上の行の時点で、の列以外の全ての列にの倍数が出現しており、かつの区間に存在するについては、各の一つ上以上のどこかの行に存在するの倍数と同列ということになるため、やはりの形で表現することができる。

故に、求める数は、と同列で一つ上の行に存在する数であり、この数には、からを引けば到達するので、

求める数はとなる。

イメージ図[編集 | hide]

の場合 1 2 3 4 5
=1 =2 =3 =4 5
=6 =7 =8 =9 10
=11 =12 =13 =14 15
=16 =17 =18 =19 20
=21 =22 =23= =24 25
=26 =27 =28= =29 30
=31 =32 =33 =34 35=

脚注[編集 | hide]

  1. は、明らかにの列に入るため。

この書籍「Aとbが互いに素で、あるときのaとbだけの和で表せない最大の整数がab-(a+b)であることの雑な説明」は、初版投稿者によって同一性保持権がガチでつよく主張されています。なので初版投稿者のお許しもなく「無許可でのリバートや内容の置き換え」等を行ったり、テンプレートを剥がした場合は荒らしとみなされ、著作権保護団体員達によって逮捕されるかもしれませんので、ご注意ください。どうしても自分勝手に本を書きたい場合はウソブックス:Aとbが互いに素で、あるときのaとbだけの和で表せない最大の整数がab-(a+b)であることの雑な説明 (2)のようにフォークを立てて、あとは独自論を勝手にお書き下さい。