第４４問の解答

問題　［ 整数の性質］

算チャレ共和国は変な国で、流通している貨幣は１７円玉と１８円玉だけであるそうです。

このとき、ぴったりで払うことのできない金額のうち、最大の金額を求めてください。

解答例１

１７円玉をn枚と１８円玉をm枚で払える額を、0≦n、m≦17の範囲で計算してみます。

参考図１

２７２円以上なら、ぴったり払うようなｎ、ｍの組み合わせがありそうですが、２７１円ではなさそうです。
従って、２７１円 が最大金額のようです。

 式で確かめてましょう。
Ｎ円を１７円玉をn枚と１８円玉をm枚で払えるとき、
　Ｎ＝１７n＋１８m　
が成り立ちます。

Nを１７で割ったときの商をp、余りをrとすると、
　Ｎ＝１７p＋r＝１７（n＋m）＋m

よって、
　１７（n＋m−p）＝r−m　・・・　（１）

従って、
　n＋m−p＝０、r−m＝０　・・・　（２）　　
なら（１）が成り立ちます。

（２）をn、mについて解くと、
　n＝p−ｒ、m＝r　・・・　（３）
を得ます。

もし、N≧２７２＝１７×１６のとき、p≧１６。
ｒはＮを１７で割った余りなので、r≦１６。

よって、（３）を満たすn、mは０≦n、mを満たします。
従って、２７２円以上なら必ずぴったり支払うことができることが分かります。　・・・　（４）

さて、Ｎ＝２７１円がぴったり支払うことができたとします。
２７１＝１７×１５＋１６だから、（１）より、
１７（n＋m−１５）＝１６−m　・・・　（１）’

２７１＝１７n＋１８m≧１８m、
よって、m≦２８８/１８≒１５．０５・・
従って、m<１６となり、0<１６−m≦１６。

これは、（１）’と矛盾します。

よって、２７１円をぴったり支払うことはできません。
（４）と合わせて考えれば、２７１円がぴったり支払えない最大金額と分かります。

答：　２７１円

以上