第２７問の解答

１．問題

セブンイレブン国では、７円玉と１１円玉の硬貨のみ発行していて、紙幣は全く発行していません。

（問１）１００００円以内の買い物で、お釣りのないように支払うことの出来る金額は何通りでしょうか。

（問２）１００００円以内の買い物で、お釣りをもらうことも可能な場合に支払うことの出来る金額は何通りでしょうか。

２．解答例1（Taroさん、清川育男さん、吉田和義さん、カミナリ親父さん、N.Nishi さん、ありっちさん、他）

（問１）

１円から７円まで、８円から１４円まで、・・・、を表１のように並べます。

表１
参考図1		 表２
参考図2

７の倍数、および１１の倍数となる金額は、それぞれ１種類の硬貨だけで支払うことが出来ます。

次に、ある金額が７円玉、１１円玉で支払うことが出来ると、その金額に７の倍数を加えた金額（すなわち表２の同じ列で下にあるもの）は全て支払うことが出来ます。

残った金額は、７円玉、１１円玉だけでは支払うことができないので、これらの個数を数えると３０通りになります。

よって、１円から１００００円までで支払い可能な金額は１００００−３０＝９９７０通りとなります。

（問２）

１１×２−７×３＝１なので、１円を支払うのには、１１円玉を２枚だして７円玉を３枚をお釣りとして貰えばいいことになります。

よって、ｎ円（ｎ＞１）のときも同様にして、１１円玉をｎ枚だして７円玉をｎ枚をお釣りとして貰うといいことになります。

従って、１円以上の任意の金額を支払うことができるので、１万円までだと１００００通りとなります。

　

答：（問１）９９７０通り　（問２）１００００通り

以上　　

３．解答例２（tomhさん、他）


まず、ｐ円を７円玉ｍ枚、１１円玉ｎ枚で払った（負のときはお釣りとして貰う）とすると、
　　 7ｍ +11ｎ＝ｐ 　・・・　(1)
となります。

（１）の整数解のうち、ｍ、ｎともに正の解の個数が問１、負の解もあって良いときが問２の個数となります。

ｐ＝１のとき、(1) を解いてみましょう。
　　7×（−３） +11×２＝１　・・・　（２）
より、ｍ＝−３、ｎ＝２が一つの解になります。
よって、ｍ＝−３ｐ、ｎ＝２ｐは、（１）の一つの解になります。

従って、お釣りが可能なら、全ての金額を支払うことが出来ますので、問２の答は１００００通りになります。

更に（１）の一般解を求めましょう。
（１）−（２）×ｐより、
　　７（ｍ＋３ｐ）＋１１（ｎ−２ｐ）＝０
　　７（ｍ＋３ｐ）＝−１１（ｎ−２ｐ）　　・・・　（３）
７と１１は互いに素なので、（３）より、（ｍ＋３ｐ）は１１の倍数、（ｎ−２ｐ）は７の倍数となります。

よって、ｋを任意の整数としてｍ＋３ｐ＝１１ｋ、ｎ−２ｐ＝７ｋ、
すなわち、ｍ＝１１ｋ−３ｐ、ｎ＝−７ｋ＋２ｐ　・・・　（４）　と表せます。　

問１の答を得るため、（１）が正の整数解を持つ条件を求めます。
（４）から、
　　ｍ＝１１ｋ−３ｐ≧ 0,
　　ｎ＝−７ｋ＋２ｐ ≧ 0
となり、
　２/７×ｐ ≧ ｋ ≧ ３/１１×ｐ　　・・・　 （５）
を得ます。

（５）より、もし　２/７×ｐ−３/１１×ｐ＝１/７７×ｐ ≧ 1
すなわち、ｐ ≧ ７７ならば、必ず（５）は正の整数解を持ちますので、ｐ＜７７を調
べれば十分なことがわかります。

参考図3
参考図4
参考図5
参考図6


以上、４６通りです。これに７７円〜１００００円の９９２４通りを合わせる
と、計９９７０通りとなります。

(参考)

一般に、ｐ、ｑが互いに素である正整数のとき、次が成り立つ。
　（１）ｐｘ＋ｑｙ＝１は、必ず整数解ｘ、ｙを持つ。
　（２）ｄ≧ｐｑのとき、ｐｘ＋ｑｙ＝ｄは必ず正または０の整数解ｘ、ｙを持つ。

（証明）ｐ＞ｑとして一般性を失わない。

（１）
ｐ、ｐ×２、ｐ×３、・・・、ｐ×（ｑ−１）、ｐ×ｑについて、それぞれｑで割った余りをｒ１、ｒ２、ｒ３、・・・、ｒq-1、ｒq・・・（Ａ）とする。

もし、（Ａ）の中に等しいもの（ｒm＝ｒn、１≦ｍ＜ｎ≦ｑ）があったと仮定する。
　ｐｍ＝ｑｓ＋ｒm、ｐｎ＝ｑｔ＋ｒnと表せるので、
　ｐｍ−ｐｎ＝ｒm−ｒn＝０、よってｐ（ｍ−ｎ）＝０。
これは、ｍ＜ｎに反するので矛盾。
よって、（Ａ）の中に等しいものはない。

ｑで割った余りは、０、１、２、・・・、ｑ−１のｑ個しかなく、（Ａ）の個数は、ｑ個なので、この中に１に等しいものが必ず存在する。これをｒnとする。
　ｐｎ＝ｑｔ＋ｒn＝ｑｔ＋１
　ｐｎ＋ｑ（−ｔ）＝１　・・・（Ｂ）
よって、ｐｘ＋ｑｙ＝１は、整数解ｘ＝ｎ、ｙ＝−ｔを持つ。

（２）
ｄをｑで割った余りをｒとすると、ｄ＝ｑｕ＋ｒと表される。
ｄ≧ｐｑより、ｕ≧ｐでなければならない。

（１）と同様にして、（Ａ）の中にｒと等しいものが必ず存在するので、これをｒnとする。
　ｐｎ＝ｑｔ＋ｒn＝ｑｔ＋ｒ
　ｐｎ−ｄ＝（ｑｔ＋ｒ）−（ｑｕ＋ｒ）＝ｑ（ｔ−ｕ）
よって、ｐｎ＋ｑ（ｕ−ｔ）＝ｄ。
　ｐｎ＝ｑｔ＋ｒ≦ｐｑ≦ｄ＝ｑｕ＋ｒ
従って、ｕ−ｔ≧０。
よって、ｐｘ＋ｑｙ＝ｄは正または０の整数解ｘ＝ｎ、ｙ＝ｕ−ｔを持つ。

（２）の別証明
　（Ｂ）より、ｐｎ＋ｑ（−ｔ）＝１。
　ｐｘ＋ｑｙ＝ｄ、ｐｎｄ＋ｑ（−ｔｄ）＝ｄ
　（ｐｘ＋ｑｙ）−｛ｐｎｄ＋ｑ（−ｔｄ）｝＝０
　ｐ（ｘ−ｎｄ）＝−ｑ（ｙ＋ｔｄ）
ところが、ｐ、ｑが互いに素であるから、ｘ−ｎｄはｑの倍数でなければならない。ｘ−ｎｄ＝ｑｋと表される。
このとき、ｙ＋ｔｄ＝ｐ（ｘ−ｎｄ）／ｑ＝ｐｑｋ／ｑ＝ｐｋ。

よって、ｘ＝ｎｄ＋ｑｋ、ｙ＝−ｐｋ−ｔｄ。
これが、ｘ、ｙともに正または０となるには、
　ｎｄ＋ｑｋ≧０、−ｐｋ−ｔｄ≧０
すなわち、−ｎｄ／ｑ≦ｋ≦−ｔｄ／ｐ　・・・（Ｃ）を同時に満たす整数ｋが存在することが必要かつ十分。

（−ｔｄ／ｐ）−（−ｎｄ／ｑ）＝（ｐｎ−ｑｔ）ｄ／（ｐｑ）＝ｄ／ｐｑ≧１
より、（Ｃ）を満たす整数ｋが必ず存在する。

よって、ｐｘ＋ｑｙ＝ｄはｘ、ｙともに正または０の整数解を持つ。