黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【JMO(日本数学オリンピック)】「1以上2016以下の整数のうち、20で割った余りが16で割った余りよりも小さい物は幾つあるか?」を3通りのやり方で解いた

C 整数 整数論

近い将来JMO(日本数学オリンピック)の本選が行われるようだ。数学オリンピックは高校生までの参加者を対象にした数学のコンテスト。さて今日はJMOの問題のうち、自分程度でも手が出た問題と解法を紹介する。色々な方法でやってみたので、興味のある方は是非見て欲しい。

JMO2016年予選2 問題

1以上2016以下の整数のうち、20で割った余りが16で割った余りよりも小さい物は幾つあるか?

解法1:C言語(プログラム)を使って総当たり

最初の解法は1から2016までの整数に対し、20と16で割った余りを総当たりで調べる。後々の答えの検証のために、一旦確実な方法を取っておきたい。そんな時にC言語(プログラム)の出番と言う訳だ。

1から2016までの整数nに対し、「nを20で割った余り<nを16で割った余り」となるものの個数を考える。以下のソースコードを実行すると600(個)と言う結果が得られた。

解法2:一次不定方程式を活用

解法2は一次不定方程式を活用する方法だ。解法3作成後に作った解答で、16と20の最小公倍数は80である事を使った。整数問題おなじみの不等式や消去法を駆使し、まさかこの方法で解答まで話が進むとは思わなかった。

まず自然数nを16で割った商をq_{16}、余りをr_{16}自然数nを20で割った商をq_{20}、余りをr_{20}とする。このときnは以下の2通りに表すことができる。

n = 16q_{16} + r_{16} 但し( 0 \leq r_{16} < 16)
n = 20q_{20} + r_{20} 但し( 0 \leq r_{20} < 20)

式変形を行うと、

20q_{20} - 16q_{16} =  r_{16} - r_{20}
4(5q_{20} - 4q_{16}) =  r_{16} - r_{20}

ここで16と20の最小公倍数は80であることから、周期80毎にr_{16}-r_{20}の値は繰り返される。このことから( 0 \leq q_{16} \leq  5)( 0 \leq q_{20} \leq  4)の範囲で考える。

さらに題意よりr_{16} - r_{20} > 0である事が必要で、左辺の因数が4を含むことからr_{16} - r_{20}は4の倍数である事が必要である。この事からr_{16} - r_{20} = 4,8,12のいずれかの場合に限られる。

(i):r_{16} - r_{20} = 4のとき、(5q_{20}-4q_{16}) = 1より(q_{20},q_{16}) = (1,1)が見つかる。つまりこの範囲内にて、r_{16} - r_{20} = 4となる整数r_{16}-r_{20}の値が決まれば、(q_{20},q_{16})は唯一つに定まる。従ってr_{16} - r_{20} = 4を満たすものを数えれば良い。

r_{16} - r_{20} = 4となる整数の組は
(r_{16},r_{20})=(15,11),(14,10),(13,9),(12,8),(11,7),(10,6)
(r_{16},r_{20})=(9,5),(8,4),(7,3),(6,2),(5,1),(4,0)の12組。

(ii):r_{16} - r_{20} = 8のとき、(5q_{20}-4q_{16}) = 2より(q_{20},q_{16}) = (2,2)と唯一つに定まり、
(r_{16},r_{20})=(15,7),(14,6),(13,5),(12,4)
(r_{16},r_{20})=(11,3),(10,2),(9,1),(8,0)の8個

(iii):r_{16} - r_{20} = 12のとき、(5q_{20}-4q_{16}) = 3より(q_{20},q_{16}) = (3,3)と唯一つに定まり、
(r_{16},r_{20})=(15,3),(14,2),(13,1),(12,0)の4個

(i)(ii)(iii)より1 \leq n \leq 80の範囲でr_{16} - r_{20} = 4,8,12となるものは24個ある。一方で2000÷80 = 25より25回繰り返され、1 \leq n \leq 2000までで24*25=600(個)みつかる。尚2001から2016については、周期性より(r_{16},r_{20})=(1,1),(2,2)......,(16,16)となり上記の(i)(ii)(iii)を満たさない。以上より600(個)(答)

解法3:1〜80のときまでの余りを総当たりで調べる

最後に紹介する解法3は、1〜80のときまでの余りを総当たりで調べてみた方法。長くなるので最後に回す事にした。n=1,2,3....自然数を大きくして行って実験してみた所どうも、20と16の最小公倍数である80毎に同じ結果が得られる事が分かった。この事を活かし、総当たり回数を減らした解答を以下に書く。

解答

割る整数20と16の最小公倍数は80より、周期80で20で割った余りが16で割った余りは繰り返される。1以上2016以下の整数のうちこのような周期は2000÷80=25(回)繰り返される。以下自然数nにおいて、20で割った余りをf(n)、16で割った余りをg(n)f(n) < g(n)を満たす物の個数をr(n)とおく。

表よりr(80) = 24である事が分かる。25回繰り返されるため、r(2000) = 25 × r(80) = 600個見つかる。一方2001から2016については、1から16までの場合と結果は同じとなる。以上を考慮してr(2016)=600(個) (答)

n f(n) g(n) 結果
1 1 1 0
2 2 2 0
3 3 3 0
4 4 4 0
5 5 5 0
6 6 6 0
7 7 7 0
8 8 8 0
9 9 9 0
10 10 10 0
11 11 11 0
12 12 12 0
13 13 13 0
14 14 14 0
15 15 15 0
16 16 0 0
17 17 1 0
18 18 2 0
19 19 3 0
20 0 4 1
21 1 5 1
22 2 6 1
23 3 7 1
24 4 8 1
25 5 9 1
26 6 10 1
27 7 11 1
28 8 12 1
29 9 13 1
30 10 14 1
31 11 15 1
32 12 0 0
33 13 1 0
34 14 2 0
35 15 3 0
36 16 4 0
37 17 5 0
38 18 6 0
39 19 7 0
40 0 8 1
41 1 9 1
42 2 10 1
43 3 11 1
44 4 12 1
45 5 13 1
46 6 14 1
47 7 15 1
48 8 0 0
49 9 1 0
50 10 2 0
51 11 3 0
52 12 4 0
53 13 5 0
54 14 6 0
55 15 7 0
56 16 8 0
57 17 9 0
58 18 10 0
59 19 11 0
60 0 12 1
61 1 13 1
62 2 14 1
63 3 15 1
64 4 0 0
65 5 1 0
66 6 2 0
67 7 3 0
68 8 4 0
69 9 5 0
70 10 6 0
71 11 7 0
72 12 8 0
73 13 9 0
74 14 10 0
75 15 11 0
76 16 12 0
77 17 13 0
78 18 14 0
79 19 15 0
80 0 0 0
総合計個数 24