SERVING THE QUANTITATIVE FINANCE COMMUNITY

katastrofa
Posts: 8772
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: permutation of {1,2,..,15}

ps.: outrun, did you try to find an upper bound on minmax S by induction?

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: permutation of {1,2,..,15}

ps.: outrun, did you try to find an upper bound on minmax S by induction?
That's indeed interesting to investigate, haven't tried that. Have you?

katastrofa
Posts: 8772
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: permutation of {1,2,..,15}

I'm not sure what's your definition of brute force and I didn't have the patience to read all those responses, but a partial solution is straightforward and allows to find the final result much faster then the actual brute force approach. You only need to notice that the average sum of triple S is 24. This means that the minmax S cannot be smaller than 24, because if any triple has S<=23, then there must be some another triple for which S>=25. Simples! This observation already spares some computational time. Next, you notice that minmax S = 24 would require a uniform S over the whole "ring", because if S = 24 for any triple a, b, c, then the "adjacent" triple must be b, c, a, while you have only one a at your disposal.  This makes you start the search from 25 and quickly find the solution.
I think I can guess in what textbook you came across this task and indeed most problems in this field are NP-hard.
Nope   BTW, I posted some reasoning (above) which can speed up brute force methods on the previous page, but it got lost in spam.

outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

### Re: permutation of {1,2,..,15}

When I was a student I had to prove if some problem was NP complete or not, ..horrible... I also had a oral exam where I got questions like "can you give an example of an NP-hard problem and how it not intersects with co-NP-space-complete?". It's often non-intuitive, when I was a student "primarily test" was not known to be in either P or NP, later it was discovered to be in P.

The puzzle comes from the Le Mond newspaper that has regular entertaining math puzzles. I found out about it while reading this excellent blog: https://xianblog.wordpress.com/