SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

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

October 6th, 2016, 9:37 pm

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.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 7th, 2016, 10:07 pm

What about 

1,15,8,2,14,7,3,13,9,4,12,6,5,11,10?
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 7th, 2016, 10:08 pm

Edit: a slight permutation fo the above groups of 3 should improve the cycle-end sums
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

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

October 7th, 2016, 10:21 pm

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!)
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 8th, 2016, 12:56 pm

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.
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

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

October 8th, 2016, 2:25 pm

We need proof! :-) E.g. that 25 can't exist?
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 8th, 2016, 4:41 pm

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.
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

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

October 8th, 2016, 9:24 pm

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...
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 8th, 2016, 10:22 pm

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.
 
User avatar
Alan
Posts: 10211
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

October 11th, 2016, 5:59 am

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
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: April 29th, 2016, 1:40 pm

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

October 11th, 2016, 6:55 am

OMG!
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 11th, 2016, 11:16 am

Very nice ... and a more sophisticated construction of triplets around each of the largest 5 numbers than my construction of constant pairs.
 
User avatar
Traden4Alpha
Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

October 11th, 2016, 1:00 pm

What's fascinating about this puzzle is that it says something about the variance of short-term subsequences within long-term trajectories.

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?
 
User avatar
Alan
Posts: 10211
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

October 11th, 2016, 2:46 pm

 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.  
 
User avatar
Paul
Posts: 10789
Joined: July 20th, 2001, 3:28 pm

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

October 11th, 2016, 3:06 pm

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

P
ABOUT WILMOTT

PW by JB

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


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

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


GZIP: On