Le Monde puzzle [#977]
A mild arithmetic Le Monde mathematical puzzle:
Find the optimal permutation of {1,2,..,15} towards minimising the maximum of sum of all three consecutive numbers, including the sums of the 14th, 15th, and first numbers, as well as the 15th, 1st and 2nd numbers.
If once again opted for a lazy solution, not even considering simulated annealing!,
[sourcecode language=”r” gutter=”false”]
parme=sample(15)
max(apply(matrix(c(parme,parme[-1],
parme[1],parme[-(1:2)],parme[1:2]),3),2,sum))
[/sourcecode]
and got the minimal value of 26 for the permutation
14 9 2 15 7 1 11 10 4 12 8 5 13 6 3
Le Monde gave a solution with value 25, though, which is
11 9 7 5 13 8 2 10 14 6 1 12 15 4 3
but there is a genuine mistake in the solution!! This anyway shows that brute force may sometimes fail. (Which sounds like a positive conclusion to failing to find the proper solution! But trying with a simple simulated annealing version did not produce any 25 either…)
October 7, 2016 at 8:14 pm
I found a 25! Using branch&bounding of linear programming instances, similar to an integer optimization algorithm. Since I’m not sure whether spoiling here would be OK, the solution is at http://www.juhokokkala.fi/permutation.txt (just the number sequence, an explanation of the method to be written later.)
October 7, 2016 at 9:41 pm
Thank you, Juho, great news that you found a sequence. (I am adept at spoiling so I would not have minded, but thanks too for the attention.)
October 3, 2016 at 9:02 pm
I hate riddles but when I saw the first version of this post (where neither of the series fitted the announcement – one was too short and the other had two 2’s in it) I actually got going until I quickly had my own sequence with a 26 and then grudgingly decided that other duties were even more urgent…: the reported Le Monde series starts with a 27 – how do I get 25 ? Too lazy for SA myself ;-)
October 3, 2016 at 7:47 am
Hi,
I don’t think the sequences are correct. There are numbers missing.
Cheers,
Anne