1

My attempt:

Suppose $\sigma \in S_{n}$ such that $|\sigma|$. We know that every element of $S_{n}$ can be written as a product of disjoint cycles, that is:

$\sigma = \theta_{1}... \theta_{i}$ .

Now we know that the order of any element in $S_{n}$ will be the least common multiple of the disjoint sets, that is:

Order($\sigma$)$=12=lcm{|\theta_{1}|...|\theta_{i}|}$.

Note, the prime factorization of 12 would be 2*2*3. As we know $lcm(4,3)=12$, therefore the following permutation would have order 12,

$(1234)(567)\in S_{7}$.

Here is where my problem arises, I know that 7 will be the answer but I don't know how to properly justify it. I know I need to show that any other set of numbers with an LCM of 12 can't have a sum of less than 7, I just don't know how to do it.

Parcly Taxel
  • 103,344
mizkid45
  • 47

1 Answers1

1

Any minimal-size permutation of a given order must have two properties:

  • It has no fixed points, which can be removed (both from the permutation and the set it acts on) without changing the order.
  • It has no pair of cycles with non-coprime lengths; the GCD of the lengths could then be factored out from one of the cycles without changing the order. This means that all multiple prime factors of the target order must be incorporated into one cycle.

Given the factorisation of 12, there are two blocks, the two factors of 2 and the factor of 3. They are either together, in which case a 12-cycle is obtained, or they are apart, in which case a 3-cycle and 4-cycle acting together on 7 letters is obtained. Thus the minimum size of the underlying set is 7.

Parcly Taxel
  • 103,344