切符の問題

2003/05/25, 06/05

電車の切符に、4桁の番号が記されている。この4つの数字を足したり引いたり掛けたり割ったりして、10になると嬉しい。
たとえば上の切符での番号は2890である。8＋2−9×0 とやると10になる。2×9−8＋0 というのもある。

さて、加減乗除と演算順序を変えるためのカッコだけを使って、4つの数から10が作れるのはどんな数字の場合だろうか。

[問 題]

0000〜9999 の 10,000の数字の中で、四則演算とカッコだけを使って10になるすべての組合せを求めよ。

[解 答]

10になるのは順列で 5,878件、組合せで 552通りある。

順列 (1234と4321は別のものとして数える) 順列のリスト
組合せ (1234と4321は同じものとして数える) 組合せのリスト

ちなみに、0000〜9999 で 10,000個だから、10にすることが可能な順列の割合は 5878÷10000＝58.78％である。

[解き方]

コンピュータ様の力をお借りする。

[STEP-1]

4つの数字を A, B, C, D とする。カッコを考慮した演算の形は 5通りある。 いずれも演算子は 3個なので、順に op1, op2, op3 とする。
  1. ((A op1 B) op2 C) op3 D
  2. (A op1 B) op2 (C op3 D)
  3. (A op1 (B op2 C)) op3 D
  4. A op1 ((B op2 C) op3 D)
  5. A op1 (B op2 (C op3 D))
演算子 op1, op2, op3 は +, -, *, / のいずれかだから、演算子の組合せは 4×4×4＝64 通りある。＋と×は交換法則が成り立つし、カッコを外しても同じ結果になることもあるが、判定が面倒なのでとりあえず総あたりすることにする。
ひとつの数字の組合せ(4桁の数)について、5×64＝320 通りの計算を試せばよい。
切符に印刷された数字は 0000〜9999 の 10,000通り可能性がある。すなわち、320×10000＝3,200,000回ループをまわすのである。
2÷3×3 は、ふつう 2 だが、コンピュータ様は 1.999... というように、多少遠慮して結果を小さくする傾向がある。そこで、演算結果の 9.999 以上 を10とみなすことにする。

結果は、結果が10になるすべての計算式と、この式から項だけを取り出したものと、２つのファイルを出力する。 プログラムは Perl で書き、ActivePerl v5.6.1 で実行した。Duron1.2GHz/Windows2000 で188秒かかった。

プログラムソース (拡張子は.txt に変更してあります) number4.pl
結果 すべての計算式 36,545件572KB result.txt
４つの項のリスト 36,545組322KB value.csv


[STEP-2]
上記 result.txt, value.csv では、下のような式が別のものとカウントされているので、これを整理する。
  1. ((1+2)+3)+4
  2. (1+2)+(3+4)
  3. (1+(2+3))+4
  4. 1+((2+3)+4)
  5. 1+(2+(3+4))
式を整理するのは面倒なので、項だけを抜出した value.csv を sort して重複を削除する。実行時間は上と同じ環境で約4秒。

プログラムソース (拡張子は.txt に変更してあります) order.pl
結果 順列リスト 5,878件52KB order.csv

同様に、組合せの場合をリストする。4つの項を sort して重複を削除する。プログラム中では動作チェックのため中間ファイルを作って、終了時に消している。前述の環境で実行時間は131秒であった。

プログラムソース (拡張子は.txt に変更してあります) assort.pl
結果 組合せリスト552件5KB assort.csv


[STEP-3]
最後に、number4.pl を改造し、任意の4つの数をあれこれして、指定の数が作れるかどうかを調べるプログラムを用意した。コマンドラインから、check.pl 1 2 3 4 10 のように 4つの数字と指定の数をパラメータとして入力する。

プログラムソース (拡張子は.txt に変更してあります) check.pl

[CGI版]

こちらは、check.pl の CGI 版。4つの数字と演算結果の値を入れて「実行」すると、その結果になる式のリストが表示されます。

4桁の数字？ 計算結果？

このようにして、たとえば 9999 や 8888 は10にできるが、7777 はできないなんてことが分かったりするとか、http://www-ku.magma.ne.jp/~akiran/men/rid/の問題なんかも解けちゃったりするのである。

なお、0000〜9999 の4桁の数字の組合せは 715通りある。10にできる組合せは 552通りだから、不可能なものは715−552＝163通りである。

不可能な組合せリスト163件 2KB differ.csv
[おまけ] 100 にできる組合せリスト98件 1KB assort100.csv
1000 にできる組合せリスト1件 − 5, 5, 5, 8

5つの式のうち、1ヵ所 (　) をつけ忘れていたところがあり、5月19日版では間違った結果を出してしまいました。138さんに感謝。実は ２ちゃんねる プログラム板 に切符の数字で１０を作れ というスレッドがあるのであった。

Windows で動く Active STATE 社の Perl = ActivePerl は、無料で下記からダウンロードできます。
http://www.activestate.com/Products/ActivePerl/