皆さん50円切手と80円切手しかないとか570円とか微妙な値段上手いこと組み合わせあるんかって思ったことありましたよね
話をもっと簡単にすると5円玉と8円玉があるとして
5円玉と8円玉と組み合わせて57円が作れるかって話やな。
それは例えば
5円玉5枚と8円玉4枚で57円になるな。
そしたら56円は言われると
8円玉7枚でええやろ。
59円は5円玉7枚、8円玉3枚やな。
と言うよりだいたい全部いけるんちゃうかってわかってくるやろ。
それはどう考えたらいいかと言うと5で割った余りで分類するねん。
8円が0枚のときは5で割った余りが0
5円玉を1枚,2枚,3枚…って使っていけば
5,10,15,20,25,30,35,…
って5の倍数全部あらわせるやろ。
8円が1枚のときは8円で5で割った余りが3やろ
5円玉を1枚,2枚,3枚…って使っていけば
8,13,18,23,28,33,38,…
って8以上の5で割った余りが3の整数があらわせるやろ。
8円が2枚のときは16円で5で割った余りが1やろ
5円玉を1枚,2枚,3枚…って使っていけば
16,21,26,31,36,41…
って16以上の5で割った余りが1の整数があらわせるやろ。
8円が3枚のときは24円で5で割った余りが4やろ
5円玉を1枚,2枚,3枚…って使っていけば
24,29,34,39,44…
って24以上の5で割った余りが4の整数があらわせるやろ。
8円が4枚のときは32円で5で割った余りが2やろ
5円玉を1枚,2枚,3枚…って使っていけば
32,37,42,47…
って32以上の5で割った余りが2の整数があらわせるやろ。
8円玉が5枚のときは40円でこれは8円玉を0枚使うときにあらわせる数
5,10,15,20,25,30,35,40,…
に含まれますね。
まとめると
5,10,15,20,25,30,35,…
8,13,18,23,28,33,38,…
16,21,26,31,36,41…
24,29,34,39,44…
32,37,42,47…
これ27はないけど28以上の整数は全部入ってるから28円以上は全部払えるねん。
有名な算数の問題でもあるな。
でもこれは実は瞬殺で答えがだせて
(5－1)(8－1)=4×7=28以上
一般的に書くと
a,bを互いな素な自然数とすると,x,yに適当な0以上の整数を入れると
ax+by
は(a－1)(b－1)以上の整数があらせるやな。
更にもっと話を簡単にすると
ax+by=(a-1)(b-1)以上
の両辺をa+bをたして
a(x+1)+b(y+1)=ab+1
になってx+1≧1,y+1≧1より結局
ax+byはx,yに適当な1以上の整数を入れるとab+1以上の整数があらわせる
ということになりますね。
(ax+by=abとするとax=b(a-y)よりxはbの倍数やけどaxがabの倍数になってbyは0以下になるから矛盾
つまりab+1以上はあらわせるけど、abはあらわせない)
更にはab+1,ab+2,…,ab+(a-1),ab+aまであらわせたら、後はxを1増やせばa大きくなるから全部あらわせることになりますね。
ただab+aはx=1,y=aで簡単にあらわせるから問題は
ab+1,ab+2,…,ab+(a-1)
をあらわせるかやな。
これを直感的に理解したいな思っていてん。
そこでa,bは互いに素な整数としてb＞aとしよか
すると
b,2b,3b,4b,…,(a-1)bをaで割った余りは1,2,3,4,…,a-1が1つずつあらわれるという定理あるやん。
これを割り算の式でかけば
nb=aq+r
n=1,2,…,a-1
r=1,2,…,a-1
nb＜abやからabをaで割ると商はbよりnbをaで割ると商qはbより小さいねん。
このとことから
a(-q)+bn=r
となりますね。
これはxとyにx=-q,y=nと代入すれば1,2,3,…,a-1まで全てあらわせるということになるけど
-qが負やねん。
xとyは正の整数にしたいわけやん。
だから正になるように-qに正の整数を足してあげるねん
q＜bやから-qにbをたしてあげたいとこやな。
a(-q)+b(n)=r
a(b)+b(0)=ab
両辺たして
a(b-q)+b(n)=ab+r
これでab+1,ab+2,…,ab+(a-1)
まであらわせましたね。
要するにnbをaで割った式
a(-q)+bn=r
でn=1,2,3,…,a-1と入れていくとr=1,2,3,…,a-1が全部あらわれるけど
xのところを正にしないといけないか-qにbを足しただけやったわけやな。
まあこれは集合
{ax+by|x,y∈Ｚ}
の元同士を足しても整数倍してもこの集合に属するベクトル空間になっているということから元を適当に足して
{ax+by|x,y∈Ｎ}
の元にすることが出来るというわけやな。
これで安心して切手を貼ることができますね。
何も恐くありません。
数学、物理
テーマ:日記 - ジャンル:日記
|
