**A**n “mildly interesting” Le Monde mathematical puzzle that eventually had me running R code on a cluster:

*Within the set {1,…,56}, take 12 values at random, x*_{1},…,x_{12}. Is it always possible to pick two pairs from those 12 balls such that their sums are equal?

**I**ndeed, while exhaustive search cannot reach the size of the set,

fowler=function(i=1,pred=NULL){
pred=c(pred,i)
for (j in (1:N)[-pred]){
a=outer(c(pred,j),c(pred,j),"+")
if ((sum(duplicated(a[lower.tri(a)]))>0)){
val=FALSE
}else{
if (length(pred)==n-1){
print(c(pred,j))
val=TRUE
}else{
val=fowler(j,pred)}}
if (val) break()
}
return(val)
}
fowler(i=N,pred=1)

with N=35 being my upper limit (and n=9 the largest value inducing double sums), the (second) easiest verification goes by sampling as indicated and checking for duplicates.

mindup=66
for (t in 1:10^7){
#arguing that extremes should be included
x=c(1,56,sample(2:55,10))
A=outer(x,x,"+")
mindup=min(mindup,sum(duplicated(A[lower.tri(A)])))
if (mindup==0) break()}

**T**he values of mindup obtained by running this code a few times are around 5, which means a certain likelihood of a positive answer to the above question…

**T**his problem raises a much more interesting question, namely how to force simulations of those 12-uplets towards the most extreme values of the target function, from simulated annealing to cross-entropy to you-name-it… Here is my simulated annealing attempt:

target=function(x){
a=outer(x,x,"+")
return(sum(duplicated(a[lower.tri(a)])))}
beta=100
Nmo=N-1
nmt=n-2
nmo=n-1
x=sort(sample(2:Nmo,nmt))
cur=c(1,x,N)
tarcur=target(cur)
for (t in 1:10^6){
dex=sample(2:nmo,2)
prop=sort(c(cur[-dex],sample((2:Nmo)[-(cur-1)],2)))
tarprop=target(prop)
if (beta*log(runif(1))<tarprop -tarcur){
cur=prop;tarcur=tarprop}
beta=beta*.9999
if (tarcur==0) break()}

**A**part from this integer programming exercise, a few items of relevance in this Le Monde Science & Medicine leaflet. A portrait of Leslie Lamport for his Turing Prize (yes, the very same Leslie Lamport who created **LaTeX**!, and wrote this book which stood on most mathematicians’ bookshelves for decades, with the marginally annoying lion comics at the head of each chapter!). A tribune on an interesting book, *The Beginning and the End*, by Clément Vidal, discussing how to prepare for the end of the Universe by creating a collective mind. And the rise of biobanks…

### Like this:

Like Loading...