問題概略
4 桁の整数 の各位の数の和は 17 の倍数です。また, の各位の数の和も 17 の倍数です。
このような のうち,最も大きいものを求めてください。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
n の 1 の位は 9
と の桁数字の和が両方とも 17 の倍数なので, の 1 の位で繰り上がりがおきるはずです。
の 1 の位は 9 です。 の形の数に絞って調べました。
In[]:= AbsoluteTiming[ f[n_] := AllTrue[{n, n + 1}, Divisible[Total@IntegerDigits@#, 17] &]; ans = SelectFirst[Reverse@Range[1009, 9999, 10], f]] Out[]= {0.000115, 9799}
条件をみたす数は 8899, 9799 の 2 つで,この問題の答えは です。
n の下 2 桁は 99
繰り上がりによる桁数字の変化をもう少しくわしく見てみましょう。繰り上がりの回数で場合分けします。
4 桁の数の桁数字の和は最大で なので,問題文中の「17 の倍数」は 17 か 34 です。
3. と 4. の は明らかに不適ですね。
1. の の桁数字の和は 以下なので 17 です。
このとき の桁数字の和は となって 1. は不適です。
2. も同様に考えると , から がわかります。
も考えると となって です。
これなら手計算で解けますね。
9 で割った余りに注目
桁数字の和ということで で考えます。上で見たように問題文中の「17 の倍数」は 17 か 34 しかなくて,9 で割ったときの余りは 8 か 7 です。
のとき 9 で割った余りは「1 増える」か「8 が 0 になる」のどちらかなので
つまり のはずで, の桁数字の和は 34 です。
4 桁の数の桁数字の和は最大で なので,これはかなり強い制約です。使える数字は次の 2 組しかありません。
1 の位が 9 であることも考えると, の候補は 6 個です。
これらに対して の桁数字を調べると,条件をみたすのは だけだとわかります。