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

小2長男「算数の問題教えて。」
俺「いいよー。どんな問題？」
長男「5と8の和で表すことができない最大の整数を求めよ。」
俺「！？」

小4向けの問題集だけど大学入試で出てもおかしくないレベル。なかなか良問だった。

— 吉田匠 (@takuYSD) 2019年1月27日

バイト中暇なので解いてみた。

問題

0以上の整数 を用いて

とするとき、 の取り得ない最大値を求めよ

解法1

一般に、整数をもちいて作れる整数は

である。ベズーの等式
今 で より であるため に正負の制限をかけなければすべての整数が作れることがわかる。
これを利用するのが普通の解法だ。

解法2

では、ベズーの公式を知らない場合はどうするのか。解き方を考えてみた。
そもそも、がある値以上ならすべての値をとり得るのか？
もしそうなら(問題としてそうなるはずだが)ある値が求まれば未満の数について考えれば良いので問題は簡単になるはずだ。

考察

十分に大きな を考える。このときとすると、 を作ることができれば帰納的に以降のすべての値はとり得る。
しかしこれは嘘である。 なぜなら+1を作るには のどちらかは負でなければならない。
が負の場合、となるで一番大きなは なので、とすればになる。これを再帰的に続けて行くとが負になってしまうからだ。

少し発想を変えてみる。
に0以上の整数を加えてできるのうち最小のものはでだ。
ということはあるが与えられたときに が実際に作れるなら帰納的に以上の値はすべてとり得ると言える。

K	n	m
+1	-3	2
+2	-6	4
+3	-1	1
+4	-4	3

上の表から、ならそれ以上のは作成可能である。 最小値はのときとなり未満の数について考察していけばいい。 を考えるとで、上の表から+1,+3,+4は作成可能。よって27が解の候補となる。実際にと代入していくと27は作りえないので答えは27である。