SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

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

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.

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

1,15,8,2,14,7,3,13,9,4,12,6,5,11,10?

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

Edit: a slight permutation fo the above groups of 3 should improve the cycle-end sums

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

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

Nice!
I see 3x a sequence of sum 26

The puzzle source claims that the answer they gave (11 9 7 5 13 8 2 10 14 6 1 12 15 4 3) has minmax sum 25 (which it hasn't!)

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

LOL! How can they get simple sums wrong?

The solution I gave is pretty robust-- 5 pairs of numbers from the extreme ends of the sequence that each sum to 16 and then the remaining middle numbers distributed between them. The sums range from 22 to 26 but if you look at pairwise permutations that might move a number that contributes to a high sum into a place with low sums, nothing really changes. Every number in this sequences is associated with a 3-sum of at least 25 or 26 which implies the best you can do is swap a 25 for 26 someplace.

Of course, my solution may be a local minimum and there's some complex permutation of all the numbers that produces a better solution.

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

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

We need proof! E.g. that 25 can't exist?

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

Proof....... Tricky.......

Some thoughts:
* the total sum of all 15 numbers is 120
* any given number affects the sum associated with 5 of the 15 numbers
* one of those sets must contain "15" and the sum of each of the pairs of numbers on either side of the 15 must be 10 or less
* thus, the run of 5 must have a sum of 35 or less which may are removed from the set of 15 numbers summing to 120

* thus, the 10 remaining numbers must sum to 85 or more
* yet the remaining 10 numbers include a neighborhood containing "14"
* the largest pair adjacent to the 14 must be 11 or less so that the sum of 3 numbers is 25 or less

* thus, the 7 remaining numbers must sum to 60 or more
* yet the remaining 7 numbers include a neighborhood containing "13"
* the largest pair adjacent to the 13 must sum to 12 or less so that the sum of 3 numbers is 25 or less

* thus, the 4 remaining numbers must sum to 35 or more
* yet the remaining 4 numbers include a neighborhood containing "12"
* the largest pair adjacent to the 12 must sum to 13 or less so that the sum of these 3 numbers is 25 or less

* thus, the 1 remaining number must be 10 or more

* that number could be "11" (or "10")

This is not proof of anything, only a chain of logic suggesting the plausibility of something.

In particular, the above construction may not be possible because it uses up specific low-value numbers such that the later pair-sum constraints are not possible.

For example, the first group of 5 will surely use 2 pairs drawn from {[1,9],[2,8],[3,7],[4,6]} which will constrain all subsequent pair constructions

The next pair must sum to 11 or less {[1,9],[2,8],[3,7],[4,6],[5,6],[4,7],[3,8],[2,9],[1,10]} but most these pairs will be removed by the choice made in the first group of five.

And so on....

Yet the final number must be 10 or 11 which affects all the feasible choices of prior pairs.

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

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

Cool.

Where did you get the 5 idea, because it's 2*[window size of 3] - 1?

We can try a generalization, this being n=15, k=3?

Every digit is part of k sets of size k. A specific digit is the leftmost is one set, the second in another,... the last in the kth.

A permutation where we swap 2 digits will affect a group of sets, some get the difference between the digits added, others subtracted.
Ponder ponder

Or we can look at is as a permutation matrix, every row has k ones and n-k zeros...

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

Yes, the idea came from thinking about the window of effects of an i-j swap and each element contributed to 2*[window size of 3] - 1 sums.

The generalization of MinMaxSum(n,k) is interesting. We know MinMaxSum(15,1) = 15 and MinMaxSum(15,15) = 120. It seems MinMaxSum(15,2) = 17 and MinMaxSum(15,14) = 119 . But others seem much harder to calculate due to combinatoric effects.

Alan
Posts: 9975
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

We need proof! E.g. that 25 can't exist?
{9,11,5,8,12,4,6,15,3,7,14,1,10,13,2}
25

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

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

OMG!

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

Very nice ... and a more sophisticated construction of triplets around each of the largest 5 numbers than my construction of constant pairs.

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

The 1-to-15 sequence has an average value of 8, implying the lower bound of MinOfMaxSum(15,3) is 24. But is 24 achievable? What about other 15 element sets with average value of 8? Clearly, we can permute {8,8,....,8,8} to get MinOfMaxSum(15,3)=24. And just as clearly, we cannot permute {22,7,7,....,7,7} to get MinOfMaxSum(15,3) of 24.

What 15 element sequences of average value of 8 have MinOfMaxSum(15,3)=24?

Alan
Posts: 9975
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

For 25, I just did a search through random permutations, which is a Mathematica built-in; the one I posted luckily turned up at # 98864991 in  my first run of 10^8. (A run of 10^7 did not beat 26).

To see if 24 is achievable, you might just search through all the permutations. There are too many to generate all at once on my machine and I didn't want to puzzle over how to systematically generate them one at a time.

Paul
Posts: 10093
Joined: July 20th, 2001, 3:28 pm

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

24 not achievable (but what do I know, I thought 25 wasn't either!).

P

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On