ベズー方程式の解の公式 その3（完全版）
過去ブログの転載です。
多元ベズー方程式とは、上の多元不定方程式のことを指します。一次ディオファントス方程式ともいいます。
既知で非0の整数a[i]と、未知の整数x[i]との積和が整数b[1]になるとき、未知の整数x[i]の組を列挙するのが、この方程式を解くことを意味します。右辺をb[1]にしているのは、計算の利便性のためです。ただの定数とお考えください。
前回まではa[i]は正の数に限定していたり、それぞれ互いに素であったり、x[i]が自然数のときしか対応していなかったりしたので、定義域、値域ともに拡張した解の公式を作りました。x[i]は自然数に限らず、任意の範囲を指定することが出来ます。
おそらくもうほぼ完璧です。とびとびの範囲には対応していないぐらいでしょう。
非常に長いので、もう証明はしません。ざっくりしたことしか説明しませんが、ご了承ください。手計算も非常にめんどくさいですから、解いてくれるプログラムを作成しました。そのため、解を求めるだけでしたら↓これを利用してください＾＾；
式の一覧
1. 剰余
割り算のあまりです。a, bともに任意の実数に拡張しています。負の数のあまりを求める場面があるので、そのために必要となります。
2. 最大公約数
任意の整数a, bの最大公約数を求める関数です。ユークリッドの互除法を用いて再帰的に求めます。
3. ax＋by＝1の特殊解
gcd(a, b)＝±1を満たす整数a, bに対する不定方程式ax＋by＝1の特殊解の一つを、拡張されたユークリッドの互除法を用いて再帰的に求める関数です。これが解の公式の肝となります。
4. ax＋by＝cの整数解
任意の非0の整数a, bに対するベズー方程式ax＋by＝cのすべての整数解x, yを求める関数です。整数nを用います。cがa, bの最大公約数で割り切れなければ解は存在しないので、∞を返します。そうでなければa, bが互いに素になるように両辺を割って、ax＋by＝1の形を作り、それを用いて右辺がcのときの整数解を求めます。
5. 個数関数で比較する下限値・上限値
ax＋by＝cの解の範囲がx^[-]≦x≦x^[+], y^[-]≦y≦y^[+]であったときの整数解x, yの範囲を求めるために使用される定数です。これらの定数は次に挙げる個数関数で用いられます。
6. 個数関数
解の下限値に対する範囲がNmin^[-], Nmax^[-]となり、解の上限値に対する範囲がNmin^[+], Nmax^[+]となります。二つの範囲が存在するので、解の範囲も二つとなりますが、次に挙げるようにして共通部分をとってやります。
7. 個数関数共通部分
gcd(a, b)や、c mod gcd(a, b)の条件については4番の式と同じです。解があれば、6番の個数関数の共通部分を上のような場合分けで取得します。共通部分を機械的にとるための手続きに過ぎないので、こんな大層なことしなくても、手計算する際にはてきとうに比較して共通部分をとるので構いません。
8. ベズー方程式の解
これらの準備によって、上の方程式を解くことができるようになります。パラメータはそれぞれ整数で、解x, yを求めます。複数の解が得られるため、整数nを用います。nの範囲は以下のとおりです。
この範囲の任意のnを用いて、解x, yは次式で表わされます。
これで2元の場合の解の公式ができました。
前回までと違って、ちゃんと負の係数にも対応させています。
9. 多元定数の範囲
記号が紛らわしいですが、｛ ｝の中身が条件で場合分けされて、前の数字と掛け算されます。単にax＋by＝cのx, yにあたる部分を下限値、上限値に置き換えただけです。
多元ベズーを解くためには例えば、a1x1＋a2x2＋a3x3＝b1となっている場合、後ろを
a2x2＋a3x3＝b2と新たに置くことによって、
① a1x1＋b2＝b1
② a2x2＋a3x3＝b2
という連立方程式にします。
①を解いてb2を求め、それを用いて②を解くことになります。4元以上も同様です。しかし、b2の範囲が分からないと有限解でも無限範囲が必要となりますから、上式によってb2の範囲を求めておきます。
10. 多元ベズー方程式の解
9番の式によって得られたb[i]の範囲を用いて、n[i]の範囲を出します。
この範囲の任意のn[i]を用いて、次式よりx[i]とb[i+1]を計算します。
b[i+1]を求めたら、次のn[i]の範囲を求めて、それにより次のx[i]とb[i+1]を求めて、……というのを続ければすべての解を求めることができます。
長い道のりでしたね。私は3元を手計算でやるのが限界でした。
例
再掲しますが、これが解くプログラムです。
これからはプログラムを用いて解きましょう。
2x＋3y＋5z＝20（x, y, zは0以上の整数）
これをプログラムに入力すると、解が11個でてきますね。0以上の整数の範囲にするには、下限に0を入力し、上限を空欄にします。
(x, y, z)＝(10, 0, 0), (7, 2, 0), (6, 1, 1), (5, 0, 2), (4, 4, 0),
(3, 3, 1), (2, 2, 2), (1, 6, 0), (1, 1, 3), (0, 5, 1), (0, 0, 4)
楽勝ですね＾＾！
桁をひっくり返す問題
ある5桁の数をひっくり返すとまた5桁になるのだが、そのひっくり返した値を2倍して12345足すともとの数に戻る。ある数は何だ？
手計算でこれを求めるのは、非常に難しそうです。ということで、プログラムにやってもらいましょう。
ある数を10000a＋1000b＋100c＋10d＋eとおくと、ひっくり返して2倍して12345足した数は20000e＋2000d＋200c＋20b＋2a＋12345と表されますから、
10000a＋1000b＋100c＋10d＋e＝20000e＋2000d＋200c＋20b＋2a＋12345
を解く問題になります。整理すると、
9998a＋980b－100c－1990d－19999e＝12345 となります。
a～eは各位の値ですが、aとeは端の数で、ひっくり返しても5桁になることから、aとeだけ1～9で、あとのb, c, dは0～9の範囲となりますね。これをプログラムに入力すると、なんと、1通りの解しか出てきません。
(a, b, c, d, e)＝(3, 9, 5, 3, 1)
ということは、答えは39531ということになりますね。ホントかな？？
ひっくり返すと13593で、2倍すると27186、これに12345を足すと39531になって戻りますね！
小銭何円入ってるかな問題
いまここに、貯金箱があります。何円か入れたのですが、いくら入れたか覚えていません。開けるには壊さなきゃいけませんが、まだほとんど入れてないので、壊すのはもったいないです。
壊さずに中の金額を知るにはどうすればいいでしょう……？
重さを量ってみるのがいいでしょうね。そこで実際に量ってみると、貯金箱そのものの重さは無視して、小銭全体が28.45gであったとします。
さあ、何円入っているでしょうか？？
実は、小銭はそれぞれ重さが決まっています。
1円: 1.0g
5円: 3.75g
10円: 4.5g
50円: 4.0g
100円: 4.8g
500円: 7.0g
ということは、重さを係数にして枚数を変数にして、こんな方程式を立ててやればいいですね。
1.0x1＋3.75x2＋4.5x3＋4.0x4＋4.8x5＋7.0x6＝28.45
この非0整数解x1～x6を求めれば、各小銭の枚数がわかります。プログラムに入力するには係数を整数にしなきゃいけないので、てきとうに両辺100倍して、100x1＋375x2＋450x3＋400x4＋480x5＋700x6＝2845としてやってみましょう。すると、なんとこれまた解が1通りだけ出てきます。
(x1, x2, x3, x4, x5, x6)＝(1, 1, 1, 0, 4, 0)
ということは、中に入っているのは1円玉1枚、5円玉1枚、10円玉1枚、100円玉4枚、ということで、416円となります。重さだけで金額を特定できてしまうのは、何だか面白いですね＾＾
しかし、これはさっぱり実用的ではありません。重さが大きくなると解の数が膨大に増えるので、特定できないのです。
その中でも比較的少なめな、36.45gの場合を見てみると、
(x1, x2, x3, x4, x5, x6)＝
(9, 1, 1, 0, 4, 0),
(6, 3, 0, 0, 4, 0),
(5, 1, 1, 1, 4, 0),
(2, 3, 0, 1, 4, 0),
(2, 1, 1, 0, 4, 1),
(1, 1, 1, 2, 4, 0),
(0, 1, 3, 0, 4, 0)
という7通りの解が出てきます。それぞれ枚数から金額を計算してみると、
424円,
421円,
470円,
467円,
917円,
516円,
435円
ということがわかります。421円～917円のどれかということですね。
500円玉が入ってるかどうかが大きいですが、ほとんど500円前後のようです。
このように解は多いけれど、金額をある程度絞り込めるのは多分いいことでしょう。
何かに使えるとうれしいね＾＾！
