Challenge!

問題177　支払いの問題
Weekend Mathematics／問題／問題177　支払いの問題

問題177　支払いの問題

１円玉、10円玉、100円玉、1,000円札を合わせて60枚使って、 ちょうど　10,000円を支払うことができるでしょうか。

問題の出典

パズル気分で算数オリンピック

東大算数研究会　編集

第２回算数オリンピック　決勝問題

解答

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

解答・その1

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

可能だとすると...
　　1000*a+100*b*10*c+d=10000
　　a+b+c+d=60
が同時に成り立つはず...but...
　　d=60-(a+b+c)
　　999*a+99*b+9*c=9940
左辺は9の倍数
右辺は9の倍数でない
これは矛盾するので...不可能 ^^

解答・その2

（ペンネ－ム：浦岡）

1円,10円,100円,1000円をそれぞれa枚,b枚,c枚,d枚(a,b,c,d∈自然数)を使うと仮定すると 題意より、次式が成り立つ。
　　a + 10b + 100c + 1000d = 10000 …(1)
　　a + b + c + d = 60 …(2)
(1)より
　　(a + b + c + d) + 9(b + 11c + 111d) = 10000
　　60 + 9(b + 11c + 111d) = 10000 (∵(2))
　　9(b + 11c + 111d) = 9940
　　b + 11c + 111d = 9940/9 …(※)
ここで、(※)において 左辺は自然数であるが、右辺は自然数ではない。
∴題意のような支払い方は不可能である。

解答・その3

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

１円玉　i個、１０円玉　j個、１００円玉　k個、１０００円札　m枚を使ったとする。総額　S は、

　　

条件から　i+j+k+m=60だから、S は 必ず3 の倍数である。
10000は、３の倍数ではないので、ちょうど60枚を使って、10000円にすることはできない。

解答・その4

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

1円玉をa枚、１０円玉をb枚、１００円玉をc枚、１０００円札をd枚使って （ a,b,c,d はいずれも０以上６０以下の整数） ちょうど１００００円を支払うことができるものとすると 次の(1)、(2)が成り立つ
　　a+b+c+d=60 ・・・・・(1)
　　a+10b+100c+1000d=10000　・・・・・(2)
(2)－(1)より
　　9ｂ＋99ｃ＋999ｄ＝9940　・・・・・(3)
(3)の左辺は９の倍数であるが、右辺は９の倍数でない
これは矛盾である
この矛盾は「ちょうど10000円を支払うことができるものとした」ことに起因する
よって、ちょうど10000円を支払うことはできない

解答・その5

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

１円玉，１０円玉，１００円玉，１０００円札の個数，札数をそれぞれａ，ｂ，ｃ，ｄとすると，条件から，
　　ａ＋ｂ＋ｃ＋ｄ＝６０………(1)
　　ａ＋１０ｂ＋１００ｃ＋１０００ｄ＝１００００………(2)
(2)－(1)から，
　　９ｂ＋９９ｃ＋９９９ｄ＝９９４０
　　∴９(ｂ＋１１ｃ＋１１１ｄ)＝９×１１０４＋４
左辺は９の倍数であり，右辺は９の倍数でないので，矛盾する．
故に条件を満たす整数ａ～ｄは存在しない．
故にちょうど１００００円を支払うことはできない．

とりあえずこのように解いたが，これは私に期待されている解答ではないだろう．いつものように，エクセルのマクロで解いてみる．
Option Explicit
Sub Macro1()
    Sheets("Sheet1").Select
    Cells(1, 1).Value = 0
    Range("A1").Select
    Dim x1 As Integer
    Dim x10 As Integer
    Dim x100 As Integer
    Dim x1000 As Integer
    For x1000 = 0 To Application.Min(Int(10000 / 1000), 60)
       For x100 = 0 To Application.Min(Int((10000 - 1000 * x1000) / 100), 60 - x1000)
          For x10 = 0 To Application.Min(Int((10000 - 1000 * x1000 - 100 * x100) / 10), 60 - x1000 - x100)
             x1 = 60 - x1000 - x100 - x10
             If 0 <= x1 And x1 <= 60 And 1000 * x1000 + 100 * x100 + 10 * x10 + 1 * x1 = 10000 Then
                Cells(1, 1).Value = Cells(1, 1).Value + 1
                Cells(Cells(1, 1).Value, 2).Value = x1
                Cells(Cells(1, 1).Value, 3).Value = x10
                Cells(Cells(1, 1).Value, 4).Value = x100
                Cells(Cells(1, 1).Value, 5).Value = x1000
             End If
          Next x10
       Next x100
    Next x1000
End Sub
このマクロにより，解は表示されなかったので，やはり支払うことはできないという結論に達する．

解答・その6

（ペンネ－ム：Part Marty）

答え：10,000円を支払うことができない

１円玉 a個、10円玉 b個、100円玉 c個、1,000円札 d枚とすると
a+10*b+100*c+1000*d=10000
a+b+c+d=60

a,bについて解くと、いかなる正の整数c,dをとっても、a,bは整数にならない。
a=110*d+10*c-9400/9,b=-111*d-11*c+9940/9

a,cについて解いても、同様
a=(100*d)/11-(10*b)/11-4000/99,c=-(111*d)/11-b/11+9940/99
a,dについて解いても、同様
a=-(100*c)/111-(110*b)/111+50000/999,d=-(11*c)/111-b/111+9940/999
b,cについて解いても、同様
b=10*d-(11*a)/10-400/9,c=-11*d+a/10+940/9
b,dについて解いても、同様
b=-(10*c)/11-(111*a)/110+5000/99,d=-c/11+a/110+940/99
c,dについて解いても、同様
c=-(11*b)/10-(111*a)/100+500/9,d=b/10+(11*a)/100+40/9

解答・その7

（ペンネ－ム：you）

10,000円を合計枚数が低い順の表を以下に作成する。

　1101001000 計
10001010
20010919
30109928
・・・　　　　


上記の表の通り9の倍数+1枚のコインが必要となる。
したがって、60枚で10,000円にすることは、9の倍数+1枚で60枚は 割り切れないためできない。

解答・その8

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

答え　１００００円を支払うことは出来ません

試しに次の方法をしてみました。
下一桁が０なので１円は最低１０円を１０枚使う事になります。
次に１０円を使い二桁目を０にするには９枚使う事になります。
次に１００円を使い三桁目を０にするには９枚を使う事になります。
ここでまでで２８枚１０００円になります。３０枚にするため１０００円を２枚使ます。
合計は３０枚３０００円になります。
６０枚は６０００円になります。
ここで使っている種類は次の通りです。
１円→２０枚　１０円→１８枚　１００円→１８枚　１０００円→４０００円
６０枚使用して合計６０００円となります。
ここで不足額は１００００円―６０００円＝４０００円ですので
使用した６０枚数を変えないで両替して４０００円に増やすことが出来るか考えてみます。
１円から１００円までの金額を上位の金額に両替すると９という数字が １００位、１０位、１位に出てきますので６０枚で１００００円は支払えない事になります。

解答・その9

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

【解法１】代数方程式を使う方法
１円、１０円、１００円及び１０００円の使用枚数をそれぞれ、ａ、ｂ、ｃ、ｄとすると、
　（ａ、ｂ、ｃ、ｄは、それぞれ１以上の整数）
題意より、以下の式(1)、(2)が成り立つ。
　　ａ＋ｂ＋ｃ＋ｄ＝６０ ・・・(1)
　　ａ＋10ｂ＋100ｃ＋1000ｄ＝10000　 ・・・(2)
式(1)より、
　　ａ＝６０－ｂ－ｃ－ｄ
式(2)に代入して整理すると、
　　９ｂ+９９ｃ+９９９ｄ＝９９４０
　　９（ｂ+１１ｃ+１１１ｄ）＝２×２×５×７×７１　・・・(3)
式(3)の左辺は約数として９を含むが、右辺には含まない。
∴式(1)(2)を同時に満たす整数ａ、ｂ、ｃ、ｄは存在しない
∴題意を満たす支払い方法は不可能である

【解法２】代数方程式を使わない方法
１００００円を１０００円と９０００円に分けて、１０００円は１円、１０円及び１００円の組合せで、 ９０００円は１０００円を９枚で支払うとき、硬貨及び紙幣の使用枚数を最少にしようとすると 下表のケースＡとなる。
同様にしてケースＢ～Ｄについて求めると、ケースＤは与件の枚数である６０を超えることが分かるので、 以後、ケースＡ～Ｃについてのみ検討すれば良い。

１）ケースＣについて、使用枚数が次に多い組合せは１００円の使用枚数を １枚減らして、 １０円の使用枚数を１０枚増やす場合である。　
結果、与件の枚数６０を超えてしまうため、ケースＣの可能性は無い。



２）ケースＢについても同様に、使用枚数が次に多い組合せを順次求めて整理すると 下表の通りである。より高額の硬貨を１枚減らして、低額の硬貨１０枚増やすので、 合計では９枚増えることになる。
結果、与件の枚数６０にはならないため、ケースＢの可能性は無い。



３）ケースＡについても同様、９枚ずつ増えていって６０にはならないので、ケースＡの可能性も無い。 表には、１００円の枚数を減らして１０円の枚数を増やした場合を示した。

∴題意を満たすケースは無く、指定の支払い方法は不可能である。

解答・その10

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

不可能。
1,000円札を10枚使って、ちょうど　10,000円を支払うことができる。
さてここで、1,000円札を100円玉に、100円玉を10円玉に、10円玉を１円玉に、 それぞれ両替したとする。
どの方法で両替しても、札／硬貨の枚数の合計が9枚増えるので、 10枚、19枚、28枚、37枚、46枚、55枚、64枚（以下略）でしか ちょうど　10,000円を支払うことができない。
よって、60枚使って、ちょうど　10,000円を支払うことはできない。

解答・その11

（ペンネ－ム：けんたん）

答え　できません。
ちょうど10,000円支払うことができるとして、1円玉、10円玉、100円玉、1,000円札の枚数をそれぞれ ａ、ｂ、ｃ、ｄとおくと
　　ａ、ｂ、ｃ、ｄは全て整数
　　ａ+ｂ+ｃ+ｄ＝６０　　　　　　　　　　　　・・・(1)
　　ａ+１０ｂ+１００ｃ＋１０００ｄ＝１００００・・(2)

(2)－(1)
　　９ｂ+９９ｃ+９９９ｄ＝９９４０
　　９（ｂ+１１ｃ+１１１ｄ）＝９９４０・・・(3)

ここで、ｂ、ｃ、ｄは整数であるから、ｂ+１１ｃ１１１ｄも整数。・・・(4)
しかし、(3)より
　　ｂ+１１ｃ１１１ｄ＝９９４０／９
となり、　　整数とならない。　　　　　　　　　　　・・・(5)
よって、(4) (5)が矛盾するため支払うことができない。

解答・その12

（ペンネ－ム：エルドス）

Ｃ言語で組んでみました。60枚では１００００円になることはないですね。

#include
main()
{
int i,j,k,l,m;
for (i=0;i<=60;i++){
 for (j=0;j<=60;j++){
  for (k=0;k<=60;k++){
   l=60-(i+j+k);
   if (l<0) {continue;}
   m=i+10*j+100*k+l*1000;
   if (m==10000) {printf("%d%d%d%d%d",m,i,j,k,l);}
  }
 }
}
return 0;
}

解答・その13

（ペンネ－ム：haya）

答： 不可能

【解き方】
￥1000札を4枚まで減らすと、最大金額でも、
　　54*100 + 1*10 + 1*1 = 9411 ＜ 10000
と、金額不足となる。　逆に￥1000札を10枚適用すれば金額超過となることから、
　　4 ＜ ￥1000札の枚数 ＜ 10
である。　それぞれの場合について合計金額が￥10000に接近する組合せを調査すると、
下のFig.1の如く、11個の場合があるが何れも丁度￥10000とはならず、 合計金額（Sum列）が￥10000を跨いでしまうので「不可能」が答えとなる。

このことは、9の倍数とならないことからも説明できる。
例えば、①では￥1000札を5枚使っているから、残りの￥100, ￥10, ￥1 をそれぞれ x, y, z として

　　

左辺は9の倍数であるが右辺は9の倍数ではないので、x, y に整数解はない
（他の場合についてはFormula列の当該式参照）。

解答・その14

（ペンネ－ム：もげぴ）

枚数はさておき，合計金額が１０，０００円である状態で，ある金種の枚数を変えるには， 例えば１０００円札を１枚減じたら１００円玉を１０枚増やす必要 があり（＝総枚数９枚増加）， 逆に１００円玉を１枚増やすなら１０円玉を１０枚減らすことになる（＝総枚数９枚減少）。 つまり，ある金種を１枚減じた （または増やした）場合， その１０分の１の金種を１０枚増やす（または減ずる）必要がある（この作業を「両替」と言うことにする。）。
例えば，１，０００円札１０枚の状態（合計１０，０００円）をスタートに任意の回数両替を続けることで， 合計額が１０，０００万円になる金種と枚数のあ らゆる組み合わせが作れるが，両替のたび総枚数は９枚ずつ増減するため，どれだけ両替を続けても，総枚数が６０枚になることはない。

解答・その15

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

●1円玉を x 枚、10円玉を y 枚、100円玉を z 枚、1000円札を w 枚とします。
題意から、　

上の方程式から 、x = 60 - y -z -w 、 これを下の方程式に代入すると、

となります。
この方程式の左辺は9の倍数ですが、右辺はそうではありません。
は整数なので、(*)の方程式は解がありません。
つまり、1円玉、10円玉、100円玉、1000円札の合計が60枚で10000円は支払えません。

●(10000－枚数)が9の倍数であることが必要です。
例えば64枚ならば、
　　9×(y + 11z + 111w) = 10000 - 64 = 9936 = 9×1104
　 なので、

のように支払いが可能です。

解答・その16

（ペンネ－ム：Ryu1128）

１円玉から千円札の各枚数をｎ1、ｎ2、ｎ3、ｎ4とし 合計をＮとします （ｎiは0か正の整数です)
ここではＮ＝60
さらに、合計金額をＳとしＳは０ではない正の10000円の倍数とします

題意から、次の式が成り立ちます
　　　ｎ1+10 ｎ2+100 ｎ3+1000 ｎ4＝Ｓ　　　ここではＳ＝10000
　　　ｎ1+ｎ2+ｎ3+ｎ4＝Ｎ　　　ここではＮ＝60
ここで次のようにおきます（ｍiは0か正の整数*1です)
　　　ｍ1＝ｎ1/10
　　　ｍ2＝（ｎ1+10 ｎ2）/100
　　　ｍ3＝（ｎ1+10 ｎ2+100 ｎ3）/1000
　　　ｍ4＝（ｎ1+10 ｎ2+100 ｎ3+1000 ｎ4）/10000　　 ；ｍ4＝Ｓ/10000
　　　　　　ここではｍ4＝1
上記から下記式が導かれます
　　　１０ｍ1＝ｎ1
　　　１０ｍ2＝ｍ1+ｎ2
　　　１０ｍ3＝ｍ2+ｎ3
　　　１０ｍ4＝ｍ3+ｎ4
上記辺々足すと、
　　　10（ｍ1＋ｍ2＋ｍ3＋ｍ4） ＝（ｍ1+ｍ2+ｍ3） +（ｎ1+ｎ2+ｎ3+ｎ4）
　　　10（ｍ1＋ｍ2＋ｍ3）＋10ｍ4 ＝（ｍ1+ｍ2+ｍ3）+Ｎ

　　　ｍ1＋ｍ2＋ｍ3＝ｋとおくと（ｋは0か正の整数…(1)）
　　　ｋ＝（Ｎ-10ｍ4）/9・・・・・ｋのとりうる値の必要条件
題意に沿ってＮとｍ4を代入すると
　　　ｋ＝（60-10）/9＝50/9…(2)

(2)は(1)に反するので不可能・・・・・回答

*1 ｍiが０か正の整数で無ければならないのは各桁が繰り上がって 最終的に合計がSにならなければならない事から自明。
因みにｍ4=１とした時のNで可能な場合は
　　　N=10、19、28、37、46、55、64・・・・、10000
で、N-10が９で割り切れ且つN≦S・・・・必要充分条件 下記表でも確かめましたが、Sの値でＮが定まり、 ｋ値によりｎiが一意に決まるというのは少し感動的でした。

解答・その17

（ペンネ－ム：ＡＮＤ）

解答：　払えません。

仮に、1000円札をa枚、100円玉をｂ枚、10円玉をｃ枚、1円玉をｄ枚使うとすると、 上記を満たすには、以下の2式を同時に満たす、０以上の整数a,b,c,dの組合せが 存在する必要があります。
　　　式1) 1000a + 100b + 10c + d = 10000
　　　式2) a + b + c + d = 60
ここで式１から式２）を引くと、以下の通りとなります。
　　　式3) 999a + 99b + 9 c = 9940
ここで左辺を９で括り、右辺を素数分解すると以下のようになります。
　　　式3)’　9*(111a + 11b + c) = 22 * 5 * 7 * 71
式3)’の左辺は９の倍数となりますが、右辺は9の倍数ではありません。
従って、式３）’を満たす a,b,c,dの0以上の整数の組合せは存在しません。

故に、１円玉、10円玉、100円玉、1,000円札を合わせて60枚使って、ちょうど　 10,000円を支払うことは、できないと言えます。

解答・その18

（ペンネ－ム：オヤジ）

１円玉X枚、１０円玉Y枚、１００円玉Z枚、１０００円札W枚、で１万円を支払おうとすると。
　　X+１０Y＋１００Z＋１，０００W＝１０，０００　・・・（１）
（１）を満たす支払い方法は、無数にあって、例えば
｛（X，Y，Z，W）｜（０，０，０，１０），（０，０，１０，９），（０，１０，９，９）， （１０，９，９，９），（３０，１７，１８，８），ｅｔｃ・・｝
１０円玉～１０００円札までどれを１枚（あるいは、１個）減らすと金額が同じであれば 一桁下の位の１円玉～１００円玉が１０個増えるので、９の倍数個増える事になる， Ｎを，０以上の整数とすると、１０，０００円支払うには、
　　X+Y＋Z＋W＝１０＋９Ｎ　・・・・（２）
　　１０＋９Ｎ＝６０　・・・（２）
を満たす０以上の整数は、存在しない。

∴１円玉、１０円玉、１００円玉、１０００円を合わせて６０枚使って、 １０，０００円を支払うことは、出来ない。　

解答・その19

（ペンネ－ム：atsuhiro）

1円玉，１０円玉，100円玉，1000円札をそれぞれx,y,z,w枚とし
　　x+10y+100z+1000w=10000…(1)
　　x+y+z+w=60…(2)
として、(1)，(2)を満たす0以上の整数（x,y,z,w）の組が存在すると仮定すると
　　(1)‐(2)：9y+99z+999w=9940
は、(左辺)≡0（mod9） であるが、(右辺)≡4 (mod9) であるので矛盾
よってこのような組みは存在しない

解答・その20

（ペンネ－ム：T_Tatekawa）

結論は「支払うことが出来ない」です．

まず10,000円を1,000円札だけで払う事を考えると，10枚必要です．
1,000円札1枚を100円玉に両替すると，合計19枚です．
つまり9枚増えます．
2桁小さいお金に両替すると99枚増えるのでアウトです．
そこで1桁小さいお金に両替する事を考えると，両替するたびにお金は 9枚ずつ増えます．

つまり，10,000円を4種類の貨幣で支払おうとすると，枚数を9で割ったときの あまりはいつも同じ（余り1）です．
ところで60を9で割ると余りは6です．
このため4種類の貨幣で10,000円を支払う事は出来ません．

解答・その21

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

１円玉，10円玉，100円玉，1000円札の数を x，y，z，u とすると
　　　x＋ y＋ z＋ u＝60 …(1)
　　　x＋10y＋100ｚ＋1000u＝10,000 …(2)
(2)－(1)： 9(y＋11z＋111u)＝9,940 …(3)

(1)(2)を満たす整数 x，y，z，u があるとすると，y＋11z＋111u は整数で，(3)より 9,940 は 9 の倍数でなければならないが，9,940 は 9 の倍数ではないので，(1)(2)を満たす整数 x，y，z，u は存在しない。
よって，１円玉，10円玉，100円玉，1000円札を合わせて60枚使って 10,000円を支払うことは できない。[証明了]

コメント

１円玉、10円玉、100円玉、1,000円札を合わせて60枚使って、 ちょうど　10,000円を支払うことは、できません。

多くの方が、正の整数を９で割ったときの剰余（余り）があるかどうかに着目して、 不可能であることを示してくださいました。正の整数を９で割ったときの剰余は、０から８までのいずれかになります。 この剰余によって、グループ分けすると、重複のない９つの集合に分けられます。 これを、９の剰余類といいます。異なる剰余類に属している整数は、当然、等しいはずはありませんね。

剰余類といえば「曜日」、 これは７の剰余類にラベルをつけたものと考えることができます。 表計算ソフトExcel(Windows版)では、日付は、1900年１月１日をシリアル値「１」として、順に番号が割り振られています。 因みに2011年10月１日は、「40817」です。この数値を７で割ると剰余は０で、土曜日ですから、 日付のシリアル値を７で割った余りと、曜日との関係は次のようになっていると考えられます。
　　剰余０・・・土曜日
　　剰余１・・・日曜日
　　剰余２・・・月曜日
　　剰余３・・・火曜日
　　剰余４・・・水曜日
　　剰余５・・・木曜日
　　剰余６・・・金曜日

これによると、基準値である1900年１月１日は日曜日、 私の誕生日は木曜日でした。(記憶にないけど。)

因みに、今日の日付と自分の誕生日の日付とで、引き算をすると、 生まれてから何日生きているかがわかります。
*　Excelでのシリアル値の表示の仕方
　　例：「2011/10/1」と入力し、セルの書式設定→表示形式で、「数値」とします。

top