Xi'an's Og

Another permutation-based Le Monde mathematical puzzle:

Given the integers 1,…n, a “perfect” combination is a pair (i,j) of integers such that no other pair enjoys the same sum. For n=33, what is the maximum of perfect combinations one can build? And for n=214? 

A rather straightforward problem, or so it seemed: take the pairs (2m,2m+1), their sums all differ, and we get the maximal possible number of sums, ⌊n/2⌋… However, I did not read the question properly (!) and the constraint is on the sum (i+j), namely

How many mutually exclusive pairs (i,j) can be found with different sums all bounded by n=33? n=2014?

In which case, the previous and obvious proposal works no longer… The dumb brute-force search

[sourcecode language=”r” gutter=”false”]
T=10^6
sol=0
for (t in 1:T){
perm=sample(1:sample(seq(20,32,2),1))
sal=sum(unique(apply(matrix(perm,ncol=2),1,sum))<33)
if (sal>sol){
sol=sal;laperm=perm}
}
[/sourcecode]

leads to a solution of

[sourcecode language=”r” gutter=”false”]
> sol
[1] 12
> laperm
[1] 6 9 1 24 13 20 4 7 21 14 17 3 16 11 19 25 23 18 12 26 15 2 5 10 22
[26] 8
> unique(apply(matrix(laperm,ncol=2),1,sum))
[1] 17 28 26 47 31 32 30 22 23 19 27 25 24
[/sourcecode]

which is close of the solution sol=13 proposed in Le Monde… It is obviously hopeless for a sum bounded by 2014. A light attempt at simulated annealing did not help either.

This entry was posted on June 1, 2014 at 12:14 am and is filed under Books, Kids, Statistics with tags Le Monde, mathematical puzzle, permutations, simulated annealing. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.