中学校の入試問題を pulp を使って線型計画法で解いてみる。

中学校の入試問題に、「四桁の数字 ABCD に 9 を掛けると DCBA になる。ABCD は何か？」というものがあるそうです。

  A B C D
x       9
---------
  D C B A

頭の体操のつもりで解いていたら、どうもこういう問題を人間が解くのは間違っている気がしてきたので、pulp を使って線型計画法で解いてみました。

まず問題を作ります。LpMinimize で最小値問題にしましたが、答えはおそらく一つでしょうから、最大値問題でもどちらでも良いのでしょう。

from pulp import *

problem = pulp.LpProblem('ABCD', LpMinimize)

変数は A, B, C, D の 4 つです。それぞれ 1 桁の整数値ですが、A だけは 0 を除外しないと 4 桁にならないので(そして A=B=C=D=0 が答えになってしまう)、「1 以上」にしておきます。

a = LpVariable('a', lowBound=1, upBound=9, cat='Integer')
b = LpVariable('b', lowBound=0, upBound=9, cat='Integer')
c = LpVariable('c', lowBound=0, upBound=9, cat='Integer')
d = LpVariable('d', lowBound=0, upBound=9, cat='Integer')

そして制約を与えます。ABCD * 9 = DCBA を素直に書き下しました。

problem += (a*1000+b*100+c*10+d) * 9 == d*1000+c*100+b*10+a

最後に問題を解いて、結果を表示させます。

problem.solve()

print(problem)
print("A=%u, B=%u, C=%u, D=%u" % tuple(x.value() for x in [a,b,c,d]))

さて、実行してみます。

% python 1089.py
Welcome to the CBC MILP Solver 
Version: 2.9.0 

(...中略...)

ABCD:
MINIMIZE
None
SUBJECT TO
_C1: 8999 a + 890 b - 10 c - 991 d = 0

VARIABLES
__dummy = 0 Continuous
1 <= a <= 9 Integer
0 <= b <= 9 Integer
0 <= c <= 9 Integer
0 <= d <= 9 Integer

A=1, B=0, C=8, D=9

答えは ABCD=1089 とのことです。検算してみます。

% python
>>> 1089 * 9
9801

確かに逆順になっています。正しく解けたようです。

最後に今回問題を解くために書いたコードの全体を載せておきます。

from pulp import *

problem = pulp.LpProblem('ABCD', LpMinimize)
a = LpVariable('a', lowBound=1, upBound=9, cat='Integer')
b = LpVariable('b', lowBound=0, upBound=9, cat='Integer')
c = LpVariable('c', lowBound=0, upBound=9, cat='Integer')
d = LpVariable('d', lowBound=0, upBound=9, cat='Integer')

problem += (a*1000+b*100+c*10+d) * 9 == d*1000+c*100+b*10+a

problem.solve()

print(problem)
print("A=%u, B=%u, C=%u, D=%u" % tuple(x.value() for x in [a,b,c,d]))

別解

たかだか 10000 くらいまでなら力まかせでもいけるかな? と試しに総当たりで計算するコードも書いてみました。

for i in range(1000, 10000):
    r = (i % 10) * 1000
    r += (i // 10 % 10) * 100
    r += (i // 100 % 10) * 10
    r += (i // 1000)
    if i * 9 == r:
        print(i, r)

あっさり、一瞬で答えが出てきました。短いし速いしエンジニアリング的観点からはこちらのコードの方が正解ですね...。