問題は下の方に
<問題>
41円切手と9円切手のみがあるとする。
この２種類の切手だけではできない料金で最大のを答えよ。
(ただし、料金は整数とする。)
-----------------------
解答は下にスクロールしたら出てきます。
スポンサードリンク
-----------------------
<解答>
41x+9yが41円切手と9円切手の２種類で出てくる料金である。
(x,yはそれぞれ0以上の整数)
x=0のとき、41x=0である。
さらに、yが整数なら、41x+9yは、9で割ると余りは０となる。
つまり、0以上で9で割ると余りは０となる整数は、
x=0を代入すれば、41x+9yですべて表せる。
x=1のとき、41x=41である。そして41÷9=4余り5
さらに、yが整数なら、41x+9yは、9で割ると余りは5となる。
つまり、41以上で9で割ると余りは5となる整数は、
x=1を代入すれば、41x+9yですべて表せる。
(しかし、41円未満の9で割ると余りは5となる整数は、41x+9yで表せない)
x=2のとき、41x=82である。そして82÷9=9余り1
つまり、82以上で9で割ると余りは1となる整数は、
41x+9yですべて表せる。
x=3のとき、41x=123である。そして123÷9=13余り6
つまり、123以上で9で割ると余りは6となる整数は、
41x+9yですべて表せる。
x=4のとき、41x=164である。そして164÷9=?余り2
つまり、164以上で9で割ると余りは2となる整数は、
41x+9yですべて表せる。
x=5のとき、41x=205である。そして205÷9=?余り7
つまり、205以上で9で割ると余りは7となる整数は、
41x+9yですべて表せる。
x=6のとき、41x=246である。そして246÷9=?余り3
つまり、246以上で9で割ると余りは3となる整数は、
41x+9yですべて表せる。
x=7のとき、41x=287である。そして287÷9=?余り8
つまり、287以上で9で割ると余りは8となる整数は、
41x+9yですべて表せる。
x=8のとき、41x=328である。そして328÷9=?余り4
つまり、328以上で9で割ると余りは4となる整数は、
41x+9yですべて表せる。
(しかし、328円未満の9で割ると余りは4となる整数は、41x+9yで表せない)
328以上で9で割ると、余りが0,1,2,3,4,5,6,7,8となる整数は、
41x+9yですべて表せる。
(用は、328以上の整数がすべて41x+9yで表せる)
9で割ると余りは4となる整数である319は、41x+9yで
は表せない。また、41x+9yで表せない整数の中で、一番最大となる。
答え：319円
<解答終わり>
次の問題
<問題>
互いにaとbが素であるとき、a円の切手とb円の切手のみで
a×b円以上が表せることができることを証明せよ。
(ただし、a>bとする。)
<解答>
(x,yは0以上の整数とする。)
a円の切手とb円の切手のみで表せる料金は、
ax+byである。
先ほどの問題だと、a=41,b=9として、
a×0,a×1,・・・・a×(b-1)をbで割った時の余りが、
ちゃんと0からb-1となったので、a×b以上のすべての整数はax+byで
表せることがわかった。
ならば、
a×0,a×1,・・・・a×(b-1)をbで割った時の余りが、
ちゃんと0からb-1のどれかになることを証明すればいい。
a×m=b×n+zm とする。
mは0以上b-1以下の整数、nはa×mをbで割ったときの商、
zmは、a×mをbで割ったときの余りとする。
m1とm2は0以上b-1以下の整数であり、m1>m2としたとき、
zm1とzm2が等しくなったとする。
a×m1=b×n1+zm1 -①
a×m2=b×n2+zm2 -②
①から②を引くと、
a×(m1-m2)=b×(n1-n2)となる。
しかし、右辺はbの倍数であるが、
m1-m2がb未満の自然数で、aがbと同じ約数を持たないので、
左辺はbの倍数にはならない。
矛盾が生じるため、a×0,a×1,・・・・a×(b-1)をbで割った時の余りは、
すべて違う数字となる。
余りは0~b-1 のb通りだけであり、a×0,a×1,・・・・a×(b-1)をbで割った時の余りが
すべて違う数字となるのであれば、
a×0,a×1,・・・・a×(b-1)をbで割った時の余りが、0からb-1のどれかになる。
(めんどくさいから省略。先ほどの問題の解答と一緒)
これより、
互いにaとbが素であるとき、a円の切手とb円の切手のみで
a×b円以上が表せることができる
<解答終わり>
目次に戻る
0 件のコメント:
コメントを投稿