Le Monde puzzle [#1036]

lemondapariAn arithmetic Le Monde mathematical puzzle to conclude 2017:

Find (a¹,…,a¹³), a permutation of (1,…,13) such that

a¹/a²+a³=a²+a³/a³+a⁴+a⁵=b¹<1
a⁶/a⁶+a⁷=a⁶+a⁷/a⁷+a⁸+a⁹=a⁷+a⁸+a⁹/a⁵+a⁹+a¹⁰=b²<1
a¹¹+a¹²/a¹²+a¹³=a¹²+a¹³/a¹³+a¹⁰=b³<1

The question can be solved by brute force simulation, checking all possible permutations of (1,…,13). But 13! is 6.6 trillion, a wee bit too many cases. Despite the problem being made of only four constraints and hence the target function taking only five possible values, a simulated annealing algorithm returned a solution within a few calls:

(a¹,…,a¹³)=(6,1,11,3,10,8,4,9,5,12,7,2,13)
(b¹,b²,b³)=(1/2,2/3,3/5)

using the following code:

checka=function(a){ #target to maximise
 return(1*(a[1]/sum(a[2:3])==sum(a[2:3])/sum(a[3:5]))+
  1*(sum(a[6:7])/sum(a[7:9])==a[6]/sum(a[6:7]))+
  1*(sum(a[7:9])/(a[5]+sum(a[9:10]))==a[6]/sum(a[6:7]))+
  1*(sum(a[11:12])/sum(a[12:13])==sum(a[12:13])/
    (a[10]+a[13])))}
parm=sample(1:13)
cheka=checka(parm)
beta=1
for (t in 1:1e6){
  qarm=parm
  idx=sample(1:13,sample(2:12))
  qarm[idx]=sample(qarm[idx])
  chekb=checka(qarm)
  if (log(runif(1))<beta*(chekb-cheka)){
     cheka=chekb;parm=qarm}
  beta=beta*(1+log(1.00001))
  if (cheka==4) break()}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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