Le Monde puzzle [#872]

An “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₁,…,x₁₂. Is it always possible to pick two pairs from those 12 balls such that their sums are equal?

Indeed, 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()}

The 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…

This 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()}

Apart 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…