Hard counting/maximum question (1 Viewer)

[Mahan1]

if a,b,c,d,e is some order of numbers from 1 to 5. What is the maximum possible value of S=ab+bc+cd+de+ea

 

[Paradoxica]

Exhausting all 120 permutations of the set yields the set of values:

37,38,40,42,43,45,47,48

Recommended: use a computer

Not recommended: do it by hand

From which it is clear the maximum value is 48.

The 10 sets (each set cycles around 5 times and can be traversed in two directions so we expect the total number of sets which generate any value to be a multiple of 10) are:

{1, 2, 4, 5, 3} {1, 3, 5, 4, 2} {2, 1, 3, 5, 4} {2, 4, 5, 3, 1} {3, 1, 2, 4, 5} {3, 5, 4, 2, 1} {4, 2, 1, 3, 5} {4, 5, 3, 1, 2} {5, 3, 1, 2, 4} {5, 4, 2, 1, 3}

These sets are in fact the same Euler Path traversed on a pentatope with the edges designated the values of the pairwise products and the vertices designated the set members, just in both directions and cycled through all start/end vertices.

 

[InteGrand]

One shortcut you can employ for the brute force method is to note that only the cylic order of a to e matters for the value of the given expression (rather than the actual permutation). So it suffices to check 4! = 24 cases.

 

[Paradoxica]

One shortcut you can employ for the brute force method is to note that only the cylic order of a to e matters for the value of the given expression (rather than the actual permutation). So it suffices to check 4! = 24 cases.

yeah, I suppose it was just a matter of reducing it to a circular permutations problem...

wait, you could view it as a bracelets problem, then you'd only have to check 12 cases

 

[InteGrand]

yeah, I suppose it was just a matter of reducing it to a circular permutations problem...

wait, you could view it as a bracelets problem, then you'd only have to check 12 cases

Yep.

 

[InteGrand]

We can also contstruct an optimal permutation by basically using a greedy algorithm or ideas from the rearrangement inequality.

 

[Paradoxica]

We can also contstruct an optimal permutation by basically using a greedy algorithm or ideas from the rearrangement inequality.

that's not guaranteed to work 100% of the time but sure... you do you...

 

[InteGrand]

that's not guaranteed to work 100% of the time but sure... you do you...

Actually, it does always work here, and will also allow us to find an optimal permutation for any finite set (in fact, multiset) of real numbers (here the set was {1, 2, 3, 4, 5}). The interested student may wish to try proving this as an exercise.