数理論 へ戻る【 問 題 １ 】
-
３円玉と４円玉がそれぞれ無数にあれば、10円以上のすべての自然数の金額をおつりなしで支払うことができることを証明せよ。
-
10円 ＝ ３円×２ ＋ ４円×１
11円 ＝ ３円×１ ＋ ４円×２
12円 ＝ ３円×４ ＝ ４円×３
13円 ＝ ３円×３ ＋ ４円×１
14円 ＝ ３円×２ ＋ ４円×２
15円 ＝ ３円×５ ＝ ３円×１ ＋ ４円×３
16円 ＝ ４円×４ ＝ ３円×４ ＋ ４円×１
17円 ＝ ３円×３ ＋ ４円×２
18円 ＝ ３円×３ ＝ ３円×２ ＋ ４円×３
19円 ＝ ３円×５ ＋ ４円×１ ＝ ３円×１ ＋ ４円×４
20円 ＝ 10円×２ ＝→ ３円×４ ＋ ４円×２
20円 ＋ x 円 のとき、
AMARI ( x , 20 ) ＜ 10 のとき、
20円 ＋ x 円 ＝ 10円 ＋ 20円 × SYOU ( 10＋x , 20 ) ＋ AMARI ( 10＋x , 20 ) となり、
AMARI ( 10＋x , 20 ) は 11円 から 19円 のいずれかなので、おつりなしで支払うことができる。
AMARI ( x , 20 ) ≧ 10 のとき、
20円 ＋ x 円 ＝ 20円 ＋ 20円 × SYOU ( x , 20 ) ＋ AMARI ( x , 20 ) となり、
AMARI ( x , 20 ) は 11円 から 19円 のいずれかなので、おつりなしで支払うことができる。
※ SYOU ( m, n ) は m を n で割った商を出力する関数である。
AMARI ( m, n ) は m を n で割った余りを出力する関数である。
-
全体集合を 0 以上の整数とする。
８以上の数はすべて ３ x ＋ ４ y の式で表すことができることを証明せよ。
-
８ ＝ ３×０＋４×２ なので、題意を満たす。
n を ３以上の整数とする。
３ x ＋４ y ＝ ３ n で表される場合について考えると、
x ＝ n 、 y ＝ ０ のときであり、 条件を満たしていることは明白である。
３ x ＋４ y ＝ ３ n ＋１ で表される場合について考えると、
３ ( x − n ) ＋４ y ＝ １ だから、
x ＝ n 、 y ＝ １ のときであり、 それは、
x ＝３ 、 y ＝１、 n ＝３
x ＝４、 y ＝１、 n ＝４
x ＝５、 y ＝１、 n ＝５
・ ・ ・ ・ ・ ・ と無限に存在する。
３ x ＋４ y ＝ ３ n ＋２ で表される場合について考えると、
３（ x − n ）＋４ y ＝ ２ だから、
x ＝ n −２ 、 y ＝２ のときであり、 それは、
x ＝１、 y ＝２、 n ＝３
x ＝２、 y ＝２、 n ＝４
x ＝３、 y ＝２、 n ＝５
・ ・ ・ ・ ・ ・ と無限に存在する。
というわけで、 ８以上の整数はすべて ３ x ＋４ y の式で表されることが解った。