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

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

togetter.com

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

問題を書き直すと、

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

になります。

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

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

f:id:yucatio:20190209142054p:plain
49から8を引いていく

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

f:id:yucatio:20190209142142p:plain
5で割った余りを書く

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

49 = 8 × 3 + 5 × 5

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

f:id:yucatio:20190209142813p:plain
48から8を引いていく

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

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

f:id:yucatio:20190209143221p:plain
47から8を引いていく

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

47 = 8 × 4 + 5 × 3

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

f:id:yucatio:20190209151022p:plain
0 -> 2 -> 4 -> 1 -> 3 の繰り返し

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

f:id:yucatio:20190209152509p:plain

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

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

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

f:id:yucatio:20190209152956p:plain
33から8を引いていく

33 = 8 × 1 + 5 × 5

で表すことができます。

32のときは

f:id:yucatio:20190209154140p:plain
32から8を引いていく

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

32 = 8 × 4

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

31のときは、

f:id:yucatio:20190209154204p:plain
31から8を引いていく

31 = 8 × 2 + 5 × 3

30のときは、

f:id:yucatio:20190209154224p:plain
30から8を引いていく

30 = 5 × 6

29のときは、

f:id:yucatio:20190209154252p:plain
29から8を引いていく

29 = 8 × 3 + 5 × 1

28のときは、

f:id:yucatio:20190209154400p:plain
28から8を引いていく

28 = 8 × 1 + 5 × 4

27のときは、

f:id:yucatio:20190209154420p:plain
27から8を引いていく

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年生まで習う知識ではとても解けなさそうでした。

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

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

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

面白くて眠れなくなる数学 (PHP文庫) [ 桜井進 ]
価格:691円(税込、送料無料) (2019/2/8時点)