## Le Monde puzzle [#8]

Another 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 than min(x,y)] from both x and y or multiply either x or y by 2. Is it always possible to obtain equal entries by iterating calls to this calculator?

While 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=sum(prop[1,]^2)+diff(prop[1,])^2
prop[2,]=c(2*a,b)
targ=sum(prop[2,]^2)+diff(prop[2,])^2
prop[3,]=c(a,2*b)
targ=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)
 9 2
 8 1
 8 2
 7 1
 7 2
 7 4
 6 3
 5 2
 4 1
 4 2
 3 1
 3 1
 3 1
 3 1
 3 1
 3 2
 2 1
 2 1
 2 1
 2 1
 2 1
 2 2
```

### One Response to “Le Monde puzzle [#8]”

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.