日比谷生からの挑戦②解答

問題はこちら

 今回は非常に長い記事となっています。日比谷生からの挑戦①も合わせてご一読ください。

nを2018以下の自然数とする。以下の操作について考える。

 (操作)　2018をnで割った余りを新たにnとする。

(操作)をして求めたnが0でないならば、(操作)を実行することをを繰り返す。

n=0となったとき、それまでに実行した(操作)の回数をf(n)とする。

例えば、n=5のとき

2018÷5=403…3，2018÷3=672…2，2018÷2=1009

このように計算するので、f(5)=3である。

以下の問いに答えよ。

(1) f(n)=2を満たすnの個数を求めよ。

(2) f(n)=4を満たす最小のnを求めよ。

(3) (研究) f(n)の最大値と、そのときのnを求めよ。

 (1) この問題は、割り算をして余りを繰り返し求めます。この問題に限らず、整数の問題は、いきなり問題を解こうとせずに、まずは具体的な数字で実験をして、ある程度問題の流れや法則を探ってみるのがよいでしょう。

(ⅰ) n=1のとき 2018÷1=2018 よりf(1)=1

(ⅱ) n=2のとき 2018÷2=1009 よりf(2)=1

(ⅲ) n=3のとき 2018÷3=672...2，2018÷2=1009 よりf(3)=2

(ⅳ) n=4のとき 2018÷4=504...2，2018÷2=1009 よりf(4)=2

まず、f(n)=1となるnは、2018を1発で割り切ることができるものであるから、n=1,2,1009,2018です。

さて、f(n)=2となるnにどのような共通点があるかというと、

「2018÷nの余りが1,2,1009,2018のいずれか」となります。

(ⅲ)(ⅳ)を見ると、2回目の割り算が2で割っていることからも、「1回目の計算の余りが2であればよい」と気づく人がいるでしょう。そこから考えを発展させればよいのです。

①「2018を割ると1余るもの」=「2018-1=2017を割り切れるもの」=「2017の約数」で、1より大きいのものです。

2017は素数なので、ここでは2017の1個のみが当てはまります。

②「2018を割ると2余るもの」=「2018-2=2016の約数」で、2より大きいものです。

2016=2⁵×3²×7なので、2016の約数の個数は(5+1)(2+1)(1+1)=36個

このなかで2より大きいだけを残すので、1,2を除いて34個

③「2018を割ると1009余るもの」=「2018-1009=1009の約数」で、1009より大きいものです。  が、そのような数はありません。

④2018を割ると2018余るものもありません。

以上より、1+34=35個

(2) 答えはn=11です。n=1から順番に計算すればいずれ見つかりますが、それでは面白くありません。ここでは、「とりあえずf(n)=4となるnでおそらく最小であろうものを1つみつけて、それが確かに条件を満たす最小のnであることを確かめる」という方針でやってみましょう。つまり、とりあえずf(11)=4であることを見つけてから、f(1)からf(10)までが4にならないことを確認するということです。

 さて、f(n)=2となるnは、1回目の計算による余りが1,2,1009,2018(f(n)=1となるn)のいずれかであるような数でした。そしてそれは、f(n)=2となるnは、2016の約数のうち2より大きい34個と2017の計35個でした。

では、f(n)=3となるnは、1回目の計算による余りがあの35個(f(n)=2となるn)のいずれかであるような数であればよいのです。

同様にf(n)=4となるnは、1回目の計算による余りがf(n)=3となるnのいずれかであるような数であればよいのです。

では実際に求めてみましょう。

4回目の計算が2018÷2となるnについて考えてみます。つまり、以下の式に当てはまるa,b,cを探し、aがf(n)=4をみたすnの値です。

1回目の計算　2018÷a=〇...b

2回目の計算　2018÷b=〇...c

3回目の計算　2018÷c=〇...2

4回目の計算　2018÷2=1009

3回目の計算からcを求めます。それは(1)で述べた通り、2016の約数のうち2より大きいものなので、3,4,6,...と、34個の候補がありますが、ここでは最小の値をとって、c=3としましょう。

1回目の計算　2018÷a=〇...b

2回目の計算　2018÷b=〇...3

3回目の計算　2018÷3=672...2

4回目の計算　2018÷2=1009

次に、 2回目の計算からbを求めます。2018を割ると3余る数ですから、2015の約数のうち3より大きいものです。そのうち、最小ものをとって、b=5としましょう。

1回目の計算　2018÷a=〇...5

2回目の計算　2018÷5=403...3

3回目の計算　2018÷3=672...2

4回目の計算　2018÷2=1009

 最後に、aを求めます。2018を割ると5余る数なら、2013の約数のうち5より大きいものです。2013=3×11×61と因数分解でき、2013の約数は小さい順に1,3,11,33,61,183,671,2013であり、5より大きいものの中で最小のものをとって、a=11となります。これでf(n)=4となるnのうち、最小の可能性が高いものが11だと分かりました。

1回目の計算　2018÷11=183...5

2回目の計算　2018÷5=403...3

3回目の計算　2018÷3=672...2

4回目の計算　2018÷2=1009

 さて、あとは、本当に11がf(n)=4となる最小のnかどうかを確かめましょう。それはf(1)からf(10)を実際に計算するだけです。

実際にf(1)からf(10)はすべて4より小さいので、f(n)=4となる最小のnはn=11となります。

(3)これはなかなか大変そうです。(2)のやり方を応用して、2018を割ると11余るものから求めていく方法が思いつきますが、それで本当に一番計算回数が多いものにたどり着けるかはわかりません。

筆者もいろいろ考えましたが、どうにもよい解き方が思いつかなかったので、コンピューターに解いてもらいました。具体的には、1から2018までのすべてのnに対し、f(n)を求めるプログラムを書いて実行させました。そうすると、

f(n)の最大値は13でそのときのnは1155,1216,1228,1271,1285,1301の6つ

となりました。

(この問題の研究)

さて、参考程度に、30までのnに対するf(n)を表でまとめてみると、以下のようになります。

nが30までであれば、nが小さい分、f(n)も小さいものばかりとなりますが、nの値が大きくなるとそうとは限りません。f(n)が1,2,...となるnのそれぞれの個数はこのようになりました。計算回数は5回から6回が最も多いと分かりました。

平均計算回数は6.13回となりました。すべてのf(n)のグラフは以下の通りとなっています。(横軸が細かすぎて全体的につぶれていて見づらく、あまり参考になりませんが。)

さて、問題文に登場する数字が2018でなく他の整数なら平均計算回数はどうなるか？などなど、調べてみると面白い、研究の余地がまだまだありそうです。もしなにか面白いことが分かったら、また記事で紹介します。

今回は、非常に長い記事となってしまいました。最後まで読んでくださり、ありがとうございます。

記事の誤字脱字や内容に誤りがあった場合は、コメントやメールにて教えてください。

これからも応援よろしくお願いします。

written by k