Hard counting/maximum question (1 Viewer)
- Thread starter Mahan1
- Start date
Paradoxica
-insert title here-
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.
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.
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
-insert title here-
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.
Paradoxica
-insert title here-
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.
Last edited: