今回はこんな整数問題。2種類の金額の切手を使って支払うことのできない金額を考える有名な類題もある問題ですが。。


問題

どのような0以上の2つの整数mとnを用いても

3m+5nの形では表すことのできない正の整数をすべて求めよ。     (大阪大)


この手の問題は、整数問題の鉄則「余りで分類」です。
合同式の考え方になりますが、すべての整数は△で割った余りで△通りにグループ分けできます。

今回は、3で割った余りで分類してみます。

n=0のとき、3m+5n=3m≧0(m=0、1、2、・・・) → 3の倍数はすべて表せる。

n=1のとき、3m+5n=3m+5=3(m+1)+2≧5(m=0、1、2、・・・) → を除く、3で割って2余る整数はすべて表せる。

n=2のとき、3m+5n=3m+10=3(m+3)+1≧10(m=0、1、2、・・・) → 1、4、7を除く、3で割って1余る整数はすべて表せる。

以上より、3m+5nの形では表すことのできない正の整数は、1、2、4、7




あるいは、もっとシンプルに考えると、小学生にも理解できます。

次のように表を書いて、、

まず、3の倍数は全部OKだから3列目にを付ける。

つぎに、5の倍数は全部OKだから5と10にを付けて、その下は3ずつ増えていくからOKでを付ける。



このとき、残った数が答えで、1、2、4、7

だから、こんなものは紙に書くまでもなく秒殺で答えわかりますと( ・3・)〜♪



≪発展≫

AとBが互いに素な整数で、mとnを0以上の整数とするとき、

(A−1)×(B−1)以上の整数は、Am+Bnの形で表せる。


→ 今回だと(3−1)×(5−1)=2×4=8以上の整数はすべて表せる。だから、7以下の整数を吟味してもOK!


[←戻る]