## Le Monde puzzle [#8]

**A**nother mathematical puzzle from ** Le Monde** that relates to a broken calculator (skipping the useless tale):

Given a pair of arbitrary positive integers

(x,y)a calculator can either substract the same integer [lesser thanmin(x,y)] from bothxandyor multiply eitherxoryby2. Is it always possible to obtain equal entries by iterating calls to this calculator?

**W**hile the solution provided in this weekend edition of ** Le Monde** is to keep multiplying

*x=min(x,y)*by

*2*until it is larger than or equal to

*y=max(x,y)/2*, at which stage subtracting

*2x-y*leads to

*(y-x,2y-2x)*which is one multiplication away from equality, I wrote a simple R code that blindly searches for a path to equality, using as a target function

*exp{x²+y²+(x-y)²}*. I did not even include a simulated annealing schedule as the optimal solution is known. Here is the R code:

#algorithm that brings two numbers (x,y) to be equal by #operations x=2*x and (x,y)=(x,y)-(c,c) emptied=function(a,b){ mab=min(a,b)-1 a=a-mab b=b-mab prop=matrix(0,3,2) targ=rep(0,3) targ0=a^2+b^2+(a-b)^2 stop=(a==b) while (!stop){ prop[1,]=c(a,b)-sample(0:(min(a,b)-1),1) targ[1]=sum(prop[1,]^2)+diff(prop[1,])^2 prop[2,]=c(2*a,b) targ[2]=sum(prop[2,]^2)+diff(prop[2,])^2 prop[3,]=c(a,2*b) targ[3]=sum(prop[3,]^2)+diff(prop[3,])^2 i=sample(1:3,1,prob=exp(targ0-targ)) a=prop[i,1];b=prop[i,2];targ0=targ[i] stop=(a==b) print(c(a,b)) } }

For instance,

> emptied(39,31) [1] 9 2 [1] 8 1 [1] 8 2 [1] 7 1 [1] 7 2 [1] 7 4 [1] 6 3 [1] 5 2 [1] 4 1 [1] 4 2 [1] 3 1 [1] 3 1 [1] 3 1 [1] 3 1 [1] 3 1 [1] 3 2 [1] 2 1 [1] 2 1 [1] 2 1 [1] 2 1 [1] 2 1 [1] 2 2

March 30, 2011 at 9:23 am

[...] Le Monde puzzle [#8] « Xi'an's Og [...]