Challenge!

問題194　２種類の硬貨
Weekend Mathematics／問題／問題194　２種類の硬貨

問題194　２種類の硬貨

ある国には、６円玉と７円玉の２種類しかお金がありません。

問１
この国では、おつりをもらわなければ絶対に支払うことができない値段が、全部で何種類ありますか。

問２
そのうちで、もっとも高い値段はいくらですか。

問題の出典

第２回算数オリンピック　予選
パズル気分で算数オリンピック
東大算数研究会・編集
講談社

解答

〜到着順にご紹介します〜

解答・その1

（ペンネ−ム：浜田　明巳）

エクセルのマクロで解いた．
１，２，３，４，５，８，９，１０，１１，１５，１６，１７，２２，２３，２９の１５種類で，
最も高い値段は２９円である．


Option Explicit
Const max As Long = 100000
Sub Macro1()
    Sheets("Sheet1").Select
    Dim a(max) As Integer
    Dim b As Long
    Dim j As Long
    Dim jj As Long
    For j = 1 To max
      a(j) = 0
    Next j
    For j = 0 To Int(max / 10)
      For jj = 0 To Int(max / 10)
        b = 6 * j + 7 * jj
        If 0 < b And b <= max Then
          a(b) = 1
        End If
      Next jj
    Next j
    Cells(1, 1).Value = 0
    Range("A1").Select
    For j = 1 To max
      If a(j) = 0 Then
        Cells(1, 1).Value = Cells(1, 1).Value + 1
        Cells(Cells(1, 1).Value, 2).Value = j
      End If
    Next j
End Sub

（別解）
６ｘ＋７ｙ（ｘ，ｙは非負整数）で表すことのできる，またはできない数を考える．

　　　６＝６・１＋７・０
　　　７＝６・０＋７・１
　　１２＝６・２＋７・０
　　１３＝６・１＋７・１
　　１４＝６・０＋７・２
　　１８＝６・３＋７・０
　　１９＝６・２＋７・１
　　２０＝６・１＋７・２
　　２１＝６・０＋７・３
　　２４＝６・４＋７・０
　　２５＝６・３＋７・１
　　２６＝６・２＋７・２
　　２７＝６・１＋７・３
　　２８＝６・０＋７・４

であり，１，２，３，４，５，８，９，１０，１１，１５，１６，１７，２２，２３，２９の １５個の数は表し得ない．
次に３０以上の数はすべて表すことができることを示す．
ｎを５以上の整数とし，６ｘ＋７ｙを６で割った余りで分類する．
i).６ｘ＋７ｙ＝６ｎのとき，(ｘ，ｙ)＝(ｎ，０)とすればよい．
ii).６ｘ＋７ｙ＝６ｎ＋１のとき，
　　６(ｘ−ｎ)＋７ｙ＝１
　上記のことから，ｘ−ｎ＜０となる．
　ｘ−ｎ＝−１とすると，
　　７ｙ＝１＋６　　　∴ｙ＝１
　故に(ｘ，ｎ)＝(４，５)，(５，６)，(６，７)，・・・とすればよい．
　故に５以上のすべてのｎについて，ｘ，ｙが存在する．
iii).６ｘ＋７ｙ＝６ｎ＋２のとき，
　　６(ｘ−ｎ)＋７ｙ＝２
　ｘ−ｎ＝−２とすると，
　　７ｙ＝２＋１２　　　∴ｙ＝２
　故に(ｘ，ｎ)＝(３，５)，(４，６)，(５，７)，・・・とすればよい．
iv).６ｘ＋７ｙ＝６ｎ＋３のとき，
　　６(ｘ−ｎ)＋７ｙ＝３< BR>　ｘ−ｎ＝−３とすると，
　　７ｙ＝３＋１８　　　∴ｙ＝３
　故に(ｘ，ｎ)＝(２，５)，(３，６)，(４，７)，・・・とすればよい．
v).６ｘ＋７ｙ＝６ｎ＋４のとき，
　　６(ｘ−ｎ)＋７ｙ＝４
　ｘ−ｎ＝−４とすると，
　　７ｙ＝４＋２４　　　∴ｙ＝４
　故に(ｘ，ｎ)＝(１，５)，(２，６)，(３，７)，・・・とすればよい．
vi).６ｘ＋７ｙ＝６ｎ＋５のとき，
　　６(ｘ−ｎ)＋７ｙ＝５
　ｘ−ｎ＝−５とすると，
　　７ｙ＝５＋３０　　　∴ｙ＝５
　故に(ｘ，ｎ)＝(０，５)，(１，６)，(２，７)，・・・とすればよい．
　以上より，６ｘ＋７ｙは３０以上のすべての整数を表し得る．
　（１）の答は，１５種類
　（２）の答は，２９円　　である．

解答・その2

（ペンネ−ム：haya）

答え：
(1) 15種類 (2) 29
【解き方】
6より小さい数は表せないから、1, 2, 3, 4, 5 は当然。
その上を探ると、8, 9, 10, 11, 15, 16, 17, 22, 23, 29 で、それ以上はない。

解答・その3

（ペンネ−ム：T_Tatekawa）

まず 6 円玉を何枚か持っていて，7 円玉に置き換えていく事を考えます．
支払いたい金額を 6 で割って余りが 1 の場合は，6円玉 を 7円玉に
1枚入れ替えられればピッタリ支払う事が出来ます．
同様に，余りがある数の場合，その枚数だけ6円玉 を 7円玉に
入れ替えられればピッタリ支払う事が出来ます．
この考え方によって種類を数え上げると，
6円玉を1枚も持っていない場合は 5 種類はおつりが出ます．
1枚だけの場合は 4 種類．
同様に考えて
　　5+4+3+2+1 = 15 種類

2) 6で割った余りの最大は 5 なので，
　　6 x 4 + 5 = 29円

解答・その4

（ペンネ−ム：紀伊龍洸）

問1が、5+4+3+2+1=15で15種類、
問2が、15+2+3+4+5=29で29円ですか。

解答・その5

（ペンネ−ム：スモークマン）

6a+7b
=6a+(6+1)b
=6(a+b)+b…a≧1

払える額…
b=0…6a…6以上の6n
b=1…6(a+1)+1…7以上の6n+1
b=2…6(a+2)+2…14以上の6n+2
b=3…6(a+3)+3…21以上の6n+3
b=4…6(a+4)+4...28以上の6n+4
b=5…6(a+5)+5…35以上の6n+5
つまり… (1) 払えない額は…
35未満の6n+5…5,11,17,23,29
28未満の6n+4…4,10,16,22
21未満の6n+3…3,9,15
14未満の6n+2…2,8
7未満の6n+1…1
の15種類

(２)?そのうちで、もっとも高い値段は29円

解答・その6

（ペンネ−ム：まーりんａｎｄさとりん）

問１
　　５＋４＋３＋２＋１＝１５　１５通り

問２
　　２９円

（理由）
支払額は、６ｎ＋ｋ　（ｋは０，１，２，３，４，５のいずれか）と表せる。
　　　６ｎ＋ｋ＝６（ｎ-ｋ）＋７ｋ
　 なので、　ｎが５以上ならば、必ず０以上の整数（ｎ−ｋ）が存在する。
よって６×５＝３０以上の整数はすべて６と７の和で表すことができる。


解答・その7

（ペンネ−ム：夜ふかしのつらいおじさん）

●おつりがなくても支払うことのできる値段を調べます。
○ｋ円が支払可能ならば、ｋ＋６ｎ円やｋ＋７ｎ円も支払が可能です。
　６と７の最小公倍数４２までを調べれば十分です。
　値段をカレンダーのように表に整理すると考えやすくなります。

　　　


　表１のように、６の倍数は斜めに、７の倍数は縦に現れます。
　この値段はおつりなしで支払が可能です。

○次に、表１の６と７の倍数に囲まれた数｛１３，１９，２０，２５，・・・｝について考えます。
　これらの数は、黄色の数の下、または緑の数の斜めにあります。
　これらの数は、上にある黄色の数と７ｎの和、または斜めにある緑の数と６ｎの和になります。
　つまりこれらの値段はおつりなしで支払が可能です。

●残った表２の値段は、おつりなしでは支払うことができません。
問１　おつりをもらわなければ絶対に支払うことができない値段は全部で１５種類です。
問２　もっとも高い値段は２９円です。

解答・その8

（ペンネ−ム：のっこん）

[1]１から４３までをカレンダーに似せて次のように書く

　　　　
１２３４５６７
８９１０１１１２１３１４
１５１６１７１８１９２０２１
２２２３２４２５２６２７２８　　
２９３０３１３２３３３４３５　　
３６３７３８３９４０４１４２　　
４３　　　

[2]６の倍数・７の倍数に○をつける
　　６、１２、１８、・・・、７、１４、２１、・・・に○がつく

[3]nを１以上の整数として（以下同じ）、（６＋７n）の数に○をつける
　　１３、２０、２７、・・・に○がつく

[4]（１２＋７n）、（１８＋７n）、（２４＋７n）、（３０＋７n）、（３６＋７n）の数に○をつける
　　１９、２６、・・・、２５、３２、・・・、３１、３８、・・・、３７、・・・、４３、・・・に○がつく

[5]（７＋６n）の数に○をつける
　　１３、１９、２５、・・・と斜めに○がついていくが、それらにはもう○がついている

[6]（１４＋６n）、（２１＋６n）、（２８＋６n）、（３５＋６n）の数に○をつける
　　斜めに○がついていくが、それらにはもう○がついている

○がついていないのは　５＋４＋３＋２＋１＝１５（個）
最大は２９

解答・その9

（ペンネ−ム：転位反応）

Ｎ円の商品を６円硬貨ｎ枚、及び７円硬貨ｍ枚でお釣りを貰うことなく支払ったとすると、
　　Ｎ＝６ｎ＋７ｍ　（ｎ，ｍ≧０、整数）
そこで、ｎ，ｍに具体的に数値を入れてＮの値を書き出してみると下表の通りになる。
なお、ｍ＝６の場合、６円硬貨の枚数として数えるので、ｍ≦５　の範囲で良い。

さて、例えば、ｎ＝３０〜３５に注目してＮの並び方をみると、
Ｎ⇒Ｎ＋１では、ｎ⇒ｎ−１、ｍ⇒ｍ＋１の規則性があることが解る。
そして、この関係は、Ｎ＝６ｎ＋７ｍを変形して導くことができる。
　　Ｎ＝６ｎ＋７ｍ
　　　＝６（ｎ−１）＋６＋７（ｍ＋１）−７
　　　＝６（ｎ−１）＋７（ｍ＋１）−１
∴Ｎ＋１＝６（ｎ−１）＋７（ｍ＋１）
∴Ｎ≧３０の商品はすべて、６円と７円の硬貨でお釣りを必要とすることなく支払いできる。
∴求めるＮは、上記の表に出てこない数値である。
列記すると、１，２，３，４，５，８，９，１０，１１，１５，１６，１７，２２，２３，２９の１５種類
最も高い値段は２９

解答・その10

（ペンネ−ム：次郎長）

答え
問１）　15種類
問２）　29円

１．6円と7円は、どちらかの硬貨1枚で支払える
　１Ａ）6円未満の1-5円の　【5種類】　はおつりが必要なことは自明です

２．硬貨2枚ずつの12-14円は、6円2枚、6円7円各1枚、7円2枚で支払える
　２Ａ)　その間の、8,9,10,11円の　【4種類】　はおつりが必要ですね。

３．硬貨3枚ずつの18-21円は、6円3枚、6円2枚7円1枚、6円1枚7円2枚、7円3枚で支払える
　３Ａ）　その間の、15,16,17円の　【3種類】　はおつりが必要

４）同様に、硬貨4枚ずつの24-28円は、6円4枚、6円3枚7円1枚、6円2枚7円2枚、6円1枚7円3枚、7円4枚で支払える
　３Ａ）　同様にその間の、22,23円の　【2種類】　はおつりが必要

４）同様に、硬貨5枚ずつの30-35円は、6円5枚、6円4枚7円1枚、6円3枚7円2枚、6円2枚7円3枚、6円1枚7円4枚、7円5枚で支払える
　３Ａ）　つまり、29円の【1種類】はどうしてもおつりが必要

以上から、おつりが必要なのは、1,2,3,4,5円と8,9,10,11円と15,16,17円と22,23円と29円の　【15種類】 もっとも高い値段は29円となります。
36円より高い値段は30円から35円までの連続した6つの値段が支払えることが分かったので、 6円ずつ足していけばずっとOKですね。

解答・その11

（ペンネ−ム：ちょろんは太太）

６円玉 m個、７円玉n個で支払うとする。ただし、m≧0 n≧0
支払える金額は、6m + 7n = 6(m + n) + n 　
６で割った余りを n とすると、その商が、ｎ より少ない場合はその金額にすることはできない。
　余り　１　で、商 0 の場合
　余り　2　で、商 0、1 の場合
　余り　3　で、商 0 、1、2 の場合
　余り　4　で、商 0 、1、2、3 の場合
　余り　5　で、商 0 、1、2、3、4 の場合
従って、15通りは、その金額にすることはできない。
また、最も大きな金額は、商が4で余りが5の場合、即ち、29

問１の答え　　　15種類　　
問２の答え　 　29　　


解答・その12

（ペンネ−ム：浦岡）


解答・その13

（ペンネ−ム：オヤジ）


従って　赤い色の数が、おつりをもらわなければ支払うことが困難な金額
　　Ｑ１　∴　１５種類
　　Ｑ２　∴　２９円　（上記表より）


解答・その14

（ペンネ−ム：迷子の雄猫）

6円5枚で30円を支払うことができる。
6円を7円に変えると1円増えるので、30円から35円までは支払うことができる。
30円から35円までにそれぞれ6円を加えると36円から42円までは支払うことができる。
以下同様に考えて43円以上なら支払うことができる。

よって30円未満がおつりなしで払えるか考える。
6円何枚かに、30円以上になるまで7円を加えていくことにする。
　0,7,14,21,28,35
　6,13,20,27,34
　12,19,26,33
　18,25,32
　24,31
　30,

よっておつりなしに支払えないのは
1,2,3,4,5,8,9,10,11,15,16,17,22,23,29の15通り

さて、こういう問題を出されると一般化する人が必ずいるはず。
ということで調べてみると、こんな記述がありました。
「互いに素な自然数m円,n円の硬貨があれば、
(m-1) (n-1) 円以上なら支払う方法があることは簡単に証明できる。」

証明が書いてなかった(汗)ということでチャレンジしてみることに。
m＜nとする。m,nは互いに素とする。
0,n,2n,3n, ... , (m-1)n　をそれぞれmで割った余りを考える。
数がm個あるので、余りも0から(m-1)まで重複無く出てくるはずである。
もし0,n,2n,3n, ... , (m-2)n, (m-1)n　をそれぞれmで割った余りが重複したとする。
重複した2数をpn,qn(ただしp＜q＜m)とする。そうすると(q-p)nはmで割り切れるので、
(q-p)=jとおいてjn=kmと書ける。
n,mは共通の素因数を持たないので、j=rm かつ　k=rn　(rは自然数)でないとこの式が成立しない。
j=(q-p)＜mであるのにj≧mであるのは矛盾する。
よって余りも0から(m-1)まで重複無く出てくる。

さて、(m-1)n-(m-1),(m-1)n-(m-2), ... ,(m-1)n-1, (m-1)n-0　をそれぞれmで割った余りを考える。
(m-1)n-(m-1)つまり(m-1)(n-1)から(m-1)nまでの連続するm個の自然数であるので、
余りも0から(m-1)まで重複無く出てくるはずである。
よって集合A{0,n,2n,3n, ... , (m-2)n }と集合B{(m-1)n-(m-1),(m-1)n-(m-2),... ,(m-1)n-1}を考えると、 集合Aの要素と集合Bの要素を、mで割った余りが同じ数同士で1対1に組みあわせることができ、 かつ集合Bの最 小の要素(m-1)n-(m-1)は集合Aの最大の要素(m-2)n=(m-1)n-nよりも大きいので、 集合Aの要素にmの整数倍を適宜加えた 集合A'{0+a1m,n+a2m,2n+a3m,3n+a4m, ... }が 集合Bと同じになるように出来る。

よって、(m-1) (n-1)から(m-1)nまでの連続するm個の自然数を
　　　am+bn ( a≧0,b≧0 )
という形式で表すこと ができるので、(m-1) (n-1)以上の自然数を
　　　am+bn ( a≧0,b≧0 )
という形式で表すことができる。
m=3,n=4のとき(m-1) (n-1)-1は5になるが、5は3a+4b ( a≧0,b≧0 )という形式で表 すことができない ので、(m-1)(n-1)-1以下の数はam+bn ( a≧0,b≧0 )という形式 で表すことができるとは限らない。
証明終わり


解答・その15

（ペンネ−ム：杖のおじさん）

答え
[1]１５種類です。　[2]２９です。

次のように表１又は表２を作って考えました。
表を作るに当っては各段の数列の項差が６円＋７円＝１３円等でも良いと思います。

表１　　　　７円の項差の表

表２　　　　６円の項差の表

表１は１から７までの数字に７を加算した数字が並んでいます。
表２は１から６までの数字に６を加算した数字が並んでいます。
ピンクの部分以外の場所にある数字は全部６円玉と７円玉で支払えます。
例えば、４０円は６円玉２枚と７円玉４枚となります。
１５０円はどのようになるか計算してみます。
７円玉で支払う方法は７で割って残りが６の倍数になるまで検算します。
１５０÷７＝２１枚残り３円
２０枚だと残り１０円
１９枚だと残り１７円
１８枚だと残り２４円、ここで６円の倍数になります。
従って、１５０円の支払いは７円玉１８枚、６円玉４枚で支払います。
６円玉で支払う方法は６で割って残りが７の倍数になるまで検算します。
１５０÷６＝１５枚　
ピンクの部分は６円又は７円で割った残りが６円、７円玉で支払えませんので

答えは
[1] １円、２円　３円、４円、５円、８円、９円、１０円、１１円、 １５円、１６円、１７円、２２円、２３円、２９円、の１５種類です。
[2] ２９円です。

解答・その16

（ペンネ−ム：Asterisk*）

問１
おつりをもらわなければ支払えない値段は、全部で15種類あります。
1,2,3,4,5,8,9,10,11,15,16,17,22,23,29円

問２
そのうちで、もっとも高い値段は29円です。

まず、6円と7円で支払うことの出来る金額を計算します・・
しかし、6+6, 6+7, 7+7...と計算するのは難しいので
6と7から始まる足し算の表を作りました。

解答・その17

（ペンネ−ム：SOU）

☆前置き
値段,6円玉の枚数,7円玉の枚数を各々z,x,y とすると、
　　z = 6x + 7y ( x,y ∈ Ｚ , z ∈ Ｎ)
のように表すことができる。

☆この式からわかること
　[1]x を1つ減らし、y を1つ増やすとz は1増える。逆なら1減る。
　[2]x,y のどちらかが負になるということは、お釣りが発生するということ。

☆問2を考える
6の倍数を、6による商をp として
　　z = 6p と表す。(z が正ならp も正) この数から1づつ増やした5つの値 z+1 , z+2 , ・・・ , z+5 を作ることを考える。 [1]を利用すると、
　　z+1 = 6*(p-1) + 7*1
　　z+2 = 6*(p-2) + 7*2
　　　・・・
　　z+5 = 6*(p-5) + 7*5
のように表現できる。
ここで[2]から、() 内は負にしてはならない。
即ち、p≧5 でなければ安全と言えない。
(逆に p=5 即ち z=30 以上の全ての値段に対しては、正の2数 x,y の組みが存在することがわかった。)
さしあたってp=4 の時を考えると、連続した5数は
　　24,25,26,27,28,29
であるが、題意から大きい方を先に調べる。
29 について考えると、その値を満たす正の2数 x,y の組みは存在しないのでこれが答え。

☆問1を考える
以上のことから29以下の値に対してお釣りなしで支払えるものを調べると
　　6,7,12,13,14,18,19,20,21,24,25,26,27,28
の14個なので、お釣りなしで支払えないのは15個となる。


解答・その18

（ペンネ−ム：K高校のT・I）

賢いやり方が思い浮かばなかったので「６」と「７」を組み合わせた数を作り、 倍数を書き出してにらめっこ

6，7，13，19，20，25，27，32，33，39，45，46の倍数
６，１２，１８，２４，３０，３６，４２
７，１４，２１，２８，３５，４２，４９
１３，２６，３９，５２，６５，７８
１９，３８，５７，７６，９５，１１４
・・・
と並べて抜けている数を小さい方から書き出していくと
1,2,3,4,5,8,9,10,11,15,16,17,22,23,29,31,34,37・・・となりました

途中までは「1,2,3,4,5」「8,9,10,11」「15,16,17」「22,23」「29」というように 連続する数がだんだん少なくなっていく規則性なのではないかと予想したのですが 31,34,37と数字が出てきた結果一時混乱。 その後「29」以降の数はすべて「6」と「7」で表すことができることに気づき解決

答えは
問1　15種類
問2　29円
となりました


解答・その19

（ペンネ−ム：三角定規）

6円x枚と7円y枚で支払える金額 N 円は，
　　6x＋7y＝N　・・・[1]
[1] の整数解 x，yは，mを整数として
　　x＝7m−N，y＝−6m＋N
　　x≧0，y≧0より，6m≦N≦7m　・・・[2]
[1] は，
　　m＝1 のとき，N＝6，7
　　m＝2 のとき，N＝12，13，14
　　m＝3 のとき，N＝18，19，20，21
　　m＝4 のとき，N＝24，25，26，27，28
　　m≧5 のとき，N≧30 のすべての自然数
を表すから，[1]が表すことができないNは，
　　N＝1，2，3，4，5，8，9，10，11，15，16，17，22，23，29
の15種類で，最大の金額は29円。

解答・その20

（ペンネ−ム：Tiki）

（１） １５種類
（２） ２９円

おつりをもらわないと払えない金額には、規則性がありますね。
７種類を周期として考えれば、最初は、１〜５円の５種類、次が８〜１１円の４種類、 その次が１５〜１７円の３種類・・・というふうに、払えない金額の幅が１つずつ少 なくなります。 というわけで、払えない金額の総数は、
　　５＋４＋３＋２＋１＝１５種類、
払えない最大の金額は、
　　　６×５−１＝２９円


コメント

一般に、互いに素(最大公約数が１)な整数ａ、ｂに対して、（ａ−１）（ｂ−１）以上の整数は、 ａｍ＋ｂｎ（ただし、ｍ、ｎは自然数）と表すことができます。
迷子の雄猫さんが証明してくださいました。
今回の場合、６と７は互いに素ですから、５×６＝３０以上の整数は、 ６ｍ＋７ｎ（ただし、ｍ、ｎは自然数）と表すことができますので、２９以下の整数について、 調べればよいことになります。

top