中学生の穴埋め問題。

中学生の娘が持ち帰ってきた宿題です。3桁同士の引き算で

○○○-○○○=○○○

○には１～９の異なる数字を入れる　というシンプルな
問題なのです。

例: 459-173=286

答えの組み合わせは300個強あり、1個の組み合わせを見つければ
よいのだそうですが・・・・よい探し方はありますか？

No.1 回答者： stand1998 回答日時： 2013/12/31 16:49

これは組み合わせの総数を問う問題ですか？ それならば729通りあると思うのですが

この回答への補足

>これは組み合わせの総数を問う問題ですか？
いえ、組み合わせを1個見つければ終わりです。
つまり手計算で組み合わせをいくつか見つける手法があれば
OKです。

>それならば729通りあると思うのですが

手元で、プログラムで総当りチェックしてみましたが、
総数は 336個だと思います。

違うかな？

補足日時：2013/12/31 17:05

No.2 ベストアンサー 回答者： ticket_012 回答日時： 2013/12/31 20:01

ベストな方法かは分かりませんが、

まず、足し算の筆算にしたほうが考えやすいです。

例の４５９－１７３＝２８６であれば、
　 ２８６
＋１７３
　 ４５９　にして考えます。

　 ＡＢＣ
＋ＤＥＦ
　 ＧＨＩ　とすると、

(1)まず、４以上の数をＧに入れます。
　（例えばＧ＝５）
(2)次に、ＧとＨとＩの和が１８になるようにＨとＩを決めてください。
　（例えばＨ＝４、Ｉ＝９）
(3)次に、ＣとＦの和がＩと等しくなるようにＣとＦを決めてください。
　（例えばＣ＝２、Ｆ＝７）
(4)次に、ＡとＤの和がＧより１小さくなるようにＡとＤを決めてください。
　（例えばＡ＝１、Ｄ＝３）
(5)ここまでできれば、残り２つの数字がＢとＥに自動的に埋まるはずです。
　（例えばＢ＝６、Ｅ＝８）
※(3)または(4)で数字が重複してしまう場合は、(2)に戻って考えます。

この方法で２１通りの組み合わせが見つかるはずです。
（試していないので間違っているかもしれません）

　ちなみに、Ａ⇔Ｄ、Ｂ⇔Ｅ、Ｃ⇔Ｆはそれぞれ入れ替え可能なため、
１つ組み合わせが見つかれば、入れ替えによって８倍の組み合わせが見つかります。

　さらに、ＣＦＩの列をＡＤＧの列の左に持ってきてもこの筆算は成り立つため、
これによってさらにその２倍の組み合わせが見つかります。

これで、２１×８×２＝３３６通りの組み合わせが見つかることになります。

この回答へのお礼

G+H+I=18は了解です。1回桁あがりがある場合
たしかにこうなりますね。これで探索範囲を大幅に減らせます。

ところで桁上がりが十の桁なのは何故でしょう？
1の桁もあり得るきもしますが、排除してよい
理由があるのでしょうか?

お礼日時：2014/01/01 12:15

No.3 回答者： staratras 回答日時： 2014/01/01 14:35

足し算で考えた方がわかりやすいと思います。

100a+10b+cを(abc)と書くことにします。(abc)+(def)=(ghi)と置くと、繰り上がる場合も考慮して
c+f=i　または　c+f-10=i …(1)(2)
b+e=h または　b+e+1=h　またはb+e-9=h またはb+e-10=h …(3)(4)(5)(6)
a+d=g または　a+d+1=g 　…(7)(8)が成り立ちます。

一の位は下からの繰り上がりがないので(2)のみです。
十の位は一の位からの繰り上がりだけがあると(4)、一の位から繰り上がりがありさらに十の位でも繰り上がりがあると(5)、一の位からは繰り上がりがなく十の位で初めて繰り上がりがあると(6)が成り立ちます。
百の位は十の位からの繰り上がりだけしかないので(8)のみです。

ここですべて繰り上がりがない場合(1)(3)(7)は同時には成り立たないことが分かります。
なぜならば、(1)(3)(7)を辺辺加えると、a+b+c+d+e+f=g+h+i …(9)となりますが、a+b+c+…h+i=45(１から9までの整数の和)は奇数なので、45をどのように2つに分けても奇数と偶数にしか分けられず、(9)が奇数=偶数になってしまうからです。

ところで奇数から偶数または偶数から奇数に変わるのは、奇数を加えたり引いたりした場合だけなので(9)のような式を成り立たたせるには、(4)か(5)か(8)が一つだけ含まれなければなりません。(2つ含まれると元に戻ります。また(4)(5)は同時には成り立たないので3つ含まれることはありません）

ここで(8)が含まれる場合を考えますと、他の位は(1)と(6)が成り立たなければなりません。
a+d+1=g b+e-10=h,c+f=i この3つの式を辺辺加えるとa+b+c+d+e+f-9=g+h+i　a+b+c+…h+i=45よりg+h+i=18　…(10)

gの最大値9で考えると、a+d=8なので、例えばa=3,d=5 とすると残りの使える数字は1,2,4,6,7,8です。、h+i=9とb+e-10=h を同時に満たすことを考えるとb=4,e=7,h=1,i=8を思いつきます。(bとeは逆でも可)さらに残りの数字２と6の和が8なので、c=2,f=6 (逆でも可）です。まとめると３４２＋５７６＝９１８　引き算に直せば、９１８ー５７６＝３４２

ところで(4)が含まれる場合を考えると他の位は(2)と(7)が成り立たなければなりません。これは辺辺加えると(10)が成り立ちます。上の解に少し手を加えた３２４＋５６７＝８９１　８９１ー５６７＝３２４　もその一例です。

また(5)が含まれる場合を考えると他の位では(2)と(8)が成り立たなければなりません。これは辺辺加えるとa+b+c+d+e+f-18=g+h+i　となり(9)が成りたたないの同様の理由で成り立ちませんのでこの場合はありません。

No.4 回答者： ticket_012 回答日時： 2014/01/01 17:56

回答者No.2です。

>ところで桁上がりが十の桁なのは何故でしょう？
>1の桁もあり得るきもしますが、排除してよい
>理由があるのでしょうか?

最後の「ＣＦＩの列をＡＤＧの列の左に持ってきてもこの筆算は成り立つ」
によって、桁上がりが一の位の場合が網羅できます。

この回答への補足

ありがとうございます。

1の桁の繰り上がりパターンの解は
10の桁の繰り上がりパターンの解から機械的に変換できるということですね。
よくわかりました。

手間を減らすため機械的に変換できる16パターンのセット中から1個づつを探索する
手順を考えると

----------

全ての手順において、数字は 1～９、で 同じ数字は2個使用できないことを前提に
作業することとする。

1) G >= 4でGを選ぶ (G, 1, 2, 3 は解がないのはちょっと試せば明らかなので)。

2) 17>=G+H>=9, で G, H を選び I=18-G-H で I を決定する。

3) G = A + D + 1, A < D で A, D を選ぶ。

4) H + 10 = B + E, B < E で B, E を選ぶ。

5) 残った数字を C < F となるように C, F に割り当て、C+F=I をチェックする。

#直感的に 「C+F=I をチェックする。」は不要のような気もしますが、検討中です。


5)まで成功したら答えを1個発見。

ある手順で可能なパターンを全て試し終わったら、ひとつ前の手順に戻り、その手順
の「次」のパターンを試す。

例1
1) G=4, H=5, I=9
2) A=1, D=2(これしかない)
3) B=7, E=8(B=6, E=9 では 9が重複するのでこれしかない)
4) C=3, F=6 で C+F=I なので OK。

解 173 + 286 = 459

例2
1) G=4, H=6, I=8
2) A=1, D=2(これしかない)
3) B=7, E=9(これしかない)
4) C=3, F=5 で C+F=I なので OK。

解 173 + 295 = 468

補足日時：2014/01/02 13:08

この回答へのお礼

全21パターンを確認できました。ありがとうございました。

お礼日時：2014/01/02 13:50