「5と8を使った和で表すことができない最大の整数を求めよ」を解いてみる

小2が「5と8を使った和で表すことができない最大の整数を求めよ」という大学入試レベルの算数を教えてと聞いてきた

この問題が面白いなと思って自分なりに解いて見たので書いてみます。数学は専門ではないので厳密さに欠けることは先に記しておきます。

問題を書き直すと、

8x + 5y (xとyは0以上の整数) で表される数で、表現できない最大の数はいくつか

になります。

問題文から、ある程度大きい数字であれば5と8の和で表すことができるので、適当な数で確かめます。 49にでもしましょうか。

49から8を順に引いていきます。

さらに5で割った余りを下に書いていきます。

25が5で割り切れますね。25までは49から3回8を引いていますので、

49 = 8 × 3 + 5 × 5

で表すことができます。別の数でもやってみましょう。8を引いていった数字と、それぞれ5で割った数字を書きます。

40が5で割り切れます。40まで1回8を引いているので、

48 = 8 × 1 + 5 × 8
(もちろん、48 = 8 × 6 でもよいです)

15が5で割り切れます。15まで4回8を引いているので、

47 = 8 × 4 + 5 × 3

長くなるので、たくさんのパターンは書けませんが、ある数から8を引いて、それを5で割った余りは、

この順番で現れることがわかります。もう少し大きい数でも確かめてみましょう。97でやってみます。

f:id:yucatio:20190209152509p:plain

なりますね。実際に定理になってると思うのですが、何の定理か忘れました。

ある数から8ずつ引いていくと、5回に1回は、5で割った余りが0になる(=5で割り切れる=5の倍数である)ということがわかりました。

ということは、ある数から4回以上8が引ければ、元の数と合わせて5個の数字が並び、その中の1つは5で割り切れます。4回以上8が引ける数の最小は33 (= 8 * 4 + 1 ) です。確かめてみると、

33 = 8 × 1 + 5 × 5

で表すことができます。

32のときは

5で割り切れる数は出てきませんが、8で割り切れるので、

32 = 8 × 4

です。1つずつみていきましょう。

31のときは、

31 = 8 × 2 + 5 × 3

30のときは、

30 = 5 × 6

29のときは、

29 = 8 × 3 + 5 × 1

28のときは、

28 = 8 × 1 + 5 × 4

27のときは、

27から8を引いていっても5の倍数にならないので、27が 8x + 5y で表すことのできない最大の数ということがわかります。

実は、32から1つずつみていかなくても、規則性を見ていけば計算で答えを求められます。

f:id:yucatio:20190209151022p:plain

32から25までは8が3回引けるので、元の数と合わせて4つの数が並びます。4つの場合、上の図で、2から始まると 2 → 4 → 1 → 3になり、0が出てこない(=5で割り切れない)ことが分かります。

5で割った余りが2になる33より小さい数は、32ですが、これは8の倍数(32 = 8*4)なので、次に大きい27(=32-5)が答えになります。

小学校2年生まで習う知識ではとても解けなさそうでした。

ネット上に同じ解法が載っているかもしれませんが、見つけられませんでした。

この問題自体はフロベニウスの硬貨交換問題として知られているそうです。

yucatio@システムエンジニア