mardi 28 septembre 2010

A Martin Gardner problem

Here is a Gardner problem that was posted today on this site
The solution I found manually is really ugly. I would be happy if someone could tell me an elegant way to solve it. In case you want to check your solution here is a google cp-solver model:

from constraint_solver import pywrapcp

solver = pywrapcp.Solver('Gardner')
dx = [solver.IntVar(range(10),'x'+str(i)) for i in range(2)]
dy = [dx[1],dx[0]]
x = solver.IntVar(range(1,100),'x'+str(i))
y = solver.IntVar(range(1,100),'x'+str(i))

m = solver.IntVar(range(1,100000),'m')

solver.Add(x == 10*dx[0]+dx[1])
solver.Add(y == 10*dy[0]+dy[1])

solver.Add(x*x - y*y == m*m)

solution = solver.Assignment()
collector = solver.AllSolutionCollector(solution)

solver.Solve(solver.Phase(dx, solver.INT_VAR_DEFAULT,

for i in range(collector.solution_count()):
current = collector.solution(i)
x = current.Value(x)
y = current.Value(y)
m = current.Value(m)
print "sol:",x+y+m,"x:",x,"y:",y,"m:",m

print "#fails:",solver.failures()
print "time:",solver.wall_time()

3 commentaires:

  1. something like finding 11 x_1 + 11 x_2 + m
    where 99(x_1²-x_2²)=m²
    and x_1,x_2 in 0..9
    and m in 0..10000

    x1 and x2 being the two digits of x

  2. I came to the same but this didn't drive me to a neat solution. I had to do trials to find perfect squares after that (very ugly ;-) )

  3. Let x = ab and y = ba where a, b in [1..9]
    Note that a != b and a > b
    Since x^2 - y^2 = m^2 hence (ab - ba) * (ab + ba) = m^2
    So the square roots of (ab - ba) and (ab + ab) must be an integer
    Note that (a - b) is in [1..8]
    By inspection realize that (ab + ba) is a multiple of 11 so the only plausible value is 121 (square of 11)
    The difference (ab - ba) follows a pattern of 9 (if a-b=1), 18 (if a-b=2), 27, 36, 45, ...
    Only 9 and 36 are square numbers and only 9 satisfies a+b = 121 and a-b=9