The order of a permutation is the number of times that permutation must be repeated until the objects return to their original positions. For example the permutation (2,3,1) on the letters ABC successively generates BCA, CAB and ABC, so its order is 3.
What is the highest possible order of a permutation on a list of 100 elements?
Any permutation can be divided into subpermutations that are cyclic, sending a into b's position, b into c's position, etc. until something gets into a's position. The order of the permutation is the LCM of the sizes of these subpermutations.
We want the largest number of relatively prime numbers that add up to 100, and fortuitously the first 9 actual primes do add up to 100.
These primes are
2, 3, 5, 7, 11, 13, 17, 19, 23
and their product is
223,092,870
making that the highest possible order of permutations of 100 elements.
(1,2)(3,4,5)(6,7,8,9,10)(11,12,13,14,15,16,17) ...
... (78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100)
Of course the (1,2), (3,4,5), etc. can be any set of nine subsets with the required cardinalities, not literally the ordinal numbers used here. Instead of (1,2) could be (18,16) for example and (17,92, 90) instead of (3,4,5). Each of these permutations would have the same order: the maximum: 223,092,870.
Edited on January 24, 2024, 4:42 pm
|
|
Posted by Charlie
on 2024-01-24 09:07:22 |
solution
