Serving the Quantitative Finance Community

 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 11th, 2016, 3:09 pm

What's interesting about both your solution and my solution is that they share certain structural properties that seem mandatory for minimizing the maxima of the 3-number sums:

1. The five highest numbers (11-15) are spaced exactly 2 elements apart
2. The five lowest numbers (1-5) are spaced exactly 2 elements apart
3. The five middle numbers (6-10) are spaced exactly 2 elements apart

Thus both solutions are 5 triplets of a pattern [low,high,medium] (or it's reverse which is the same).

The cardinality of these patterns is quite modest, being at most (5!)^3 = 1,728,000 for a simple algorithm that tries every possible permutation of the highs, lows, and mediums to being 1/10th that number if one cleverly pre-culls the reverse sequence or congruent rotations of the sequences.

It's a separate issue whether there may be solutions that don't have this structure of five triplets. For example, might something of the form {medium,12,low,11,medium,....} lead to MinOfMaxSum of 25 or lower? Perhaps some pattern of three 5-element subsequences has the same or better MinOfMaxSum.
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: January 1st, 1970, 12:00 am

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

October 11th, 2016, 3:27 pm

There are far less unique triplets of integers that sum to 24

1 2 22
1 3 21
...
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

October 11th, 2016, 5:00 pm

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

P
Agree. Unless I am missing something, the proof seems trivial:
For 24, every triple must sum to 24 and w.l.o.g, start this putative optimum sequence at 1. But all such sequences become impossible to continue immediately:
{1,8,15, x}
{1,9,14,x}
{1,10,13,x}
{1,11,12,x}
{1,12,11,x}
{1,13,10,x}
{1,14,9,x}
{1,15,8,x}
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 11th, 2016, 5:24 pm

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

P
Agree. Unless I am missing something, the proof seems trivial:
For 24, every triple must sum to 24 and w.l.o.g, start this putative optimum sequence at 1. But all such sequences become impossible to continue immediately:
{1,8,15, x}
{1,9,14,x}
{1,10,13,x}
{1,11,12,x}
{1,12,11,x}
{1,13,10,x}
{1,14,9,x}
{1,15,8,x}
Brilliant!
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: January 1st, 1970, 12:00 am

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

October 11th, 2016, 5:53 pm

yes, really brilliant
 
User avatar
Paul
Posts: 6604
Joined: July 20th, 2001, 3:28 pm

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

October 11th, 2016, 7:19 pm

a, b, c, d

Implies a=d

P
 
User avatar
outrun
Topic Author
Posts: 4573
Joined: January 1st, 1970, 12:00 am

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

October 11th, 2016, 7:45 pm

Yes, so we can try to limit deviation by 1 (if we want to generalize)

a, b, c, a+1, ...

but don't forget that the last item is connected to the first.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 11th, 2016, 10:08 pm

a, b, c, d

Implies a=d

P
It would seem this line of argument generalizes to the n,k case for 1 < k < n to show that the min max sum for the 1 to n sequence is always greater than k*(n+1)/2.
 
User avatar
Alan
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

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

October 12th, 2016, 6:22 pm

a, b, c, d

Implies a=d

P
It would seem this line of argument generalizes to the n,k case for 1 < k < n to show that the min max sum for the 1 to n sequence is always greater than k*(n+1)/2.
Is there a simple formula for the general achievable minimum and what is a proof of that? Or, failing that, is there a proof that for the orig. problem the minimum of 25 is achievable without finding an actual sequence?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 12th, 2016, 7:00 pm

a, b, c, d

Implies a=d

P
It would seem this line of argument generalizes to the n,k case for 1 < k < n to show that the min max sum for the 1 to n sequence is always greater than k*(n+1)/2.
So, then the question becomes: is there a simple formula for the general achievable minimum and what is a proof of that? 
Indeed!

Your proof that k*(n+1)/2 is impossible relies on constructing the first k elements to have k*(n+1)/2 which then requires that the k+1 element have a value that was already used (a=d). But even if we let d = a+1 to create a triplet (or k-tuple) of k*(n+1)/2+1, there's no guarantee of avoiding some future contradictory constraint that might force a sum of k*(n+1)/2+2.

The observation that the [15,3] construction involves five triplets each with a structure of [low,high,medium] implies that the properties of the min max sum may have some relationship to the properties of 3x3 correlation matrices, the limits on the negative values in such matrices, and the geometric interpretations of the cos(theta) angles of the vectors that create these matrices. But the three vectors of the low, medium, and high subsequences must be permuted to become anti-correlated so that the variance of the sums goes to zero and the max sum is held to some minimum value. Yet these permuted subsequences lie on a lattice which implies that angles between the vectors are not quite at the theoretic values required to have perfect anticorrelation.

There's probably some frightening link between all this and cryptography -- the inability to eliminate residual variance in the sums of permuted sequences might imply an inability to eliminate leaking information between the plaintext and cryptotext...... YIPES!
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

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

October 12th, 2016, 8:35 pm

It reminded me of tasks I've read long ago in some book on graph algorithms. One I remember goes: You have a polygon with n+1 nodes numbered arbitrarily from 0 to n. A side of the polygon joining nodes with numbers i and j  has a number | i - j | assigned. What is the minimum sum of all sides and in how many ways can it be realised?
 
User avatar
savr
Posts: 6
Joined: January 21st, 2013, 3:28 pm

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

October 13th, 2016, 9:35 am

Gutted that brute force won the day. Any transformations - other than rotations/reversal - that preserve the solution property? <CaptnObvious> it seems k|n is important. For brute force, I'd rather 0)choose the target sum you're pretty sure is the right answer :) 1)seed the first pair (trying {11,9} first if lucky) 2)advance one digit at a time, trying for a sum within 1 of the target sum (being 25 here), backtracking when impossible.</> 
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 13th, 2016, 3:15 pm

Yes, It's always more satisfying to find a clever deductive solution than a brute force one. Yet it seems brute force may be required for combinatoric puzzles in which the true solution hides within a complex set of constraints on the solution pattern. In this system, small changes in the sequence create large changes in the sums. Incrementally growing a solution might find a solution. But it does not find all solutions or the best solution and it might force the algorithm to parse a large fraction of the sequence space before realizing no solution exists (e.g., if sets an impossible target sum).

Alan provided nice logic for why a solution of k*(n+1)/2 is impossible but no one has proven that k*(n+1)/2+1 is always possible or that some other upper bounds exists (although 5+10+15 = 30 certainly seems well above the worst case).

As for transformations that preserve the solution property, rotation and reversal are the only easy ones. There may be others. For example if the pattern of sums contains at least two places with some low minimum value and the elements surrounding those minima have certain properties relative to each other, then a reversal of the subsequence between two minima might be solution, too. Whether there is some other way of representing the solution space that clusters or interconnects all "good" solutions to the exclusion of all "bad" solutions is not clear to me.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

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

October 17th, 2016, 12:38 am

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.
Last edited by katastrofa on October 17th, 2016, 2:03 am, edited 2 times in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

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

October 17th, 2016, 1:21 am

Yes, the inability to form an a,b,c,a sequence does disprove the ability to reach a minimax of the triplet sums of 24, but that logic does not guarantee that a solution of 25 is feasible.

And the observation about the average of the sums of the 15 triples being 24 is also a good one but may not constrain the search as much as you might think. Alan's solution (brute forced in that he had Mathematica generate 10^8 random permutations, checked the sums, and got lucky with draw #98,864,991) was {9,11,5,8,12,4,6,15,3,7,14,1,10,13,2}. The 15 sums for that solution include 6 triples with a sum of 25, 6 triples with a sum of 24, and 3 triples with a sum of 22.

If we hypothesize that a solution of 25 exists, we can certainly avoid any branch of the search tree that generates a triple with a sum higher than 25, but the lowest possible sum for a solution of 25 may be as low as 10.

No doubt, it's a markedly restricted search although it's still a bit brutish in that the sequence-building search may be forced to back-track even back to the second element and the entire search may fail if 25 were an impossible solution which was surmised earlier in the thread.