You don't need to express symmetry of Sn, but I don't understand what you mean by this: "given a permutation that has a k-cycle, you can always extend it so that you have m! ones".
I'd express it like this:
Permutations in Sn\S have at least one cycle of length k, k>m. Two permutations p and q are in the same class if q can be formed from p as follows: Let C be the cycle in p containing the smallest number which is contained in a cycle of length greater than m. In C, take the smallest m numbers. Then q is formed from p by permuting these m numbers. Note that every permutation of these m numbers results in a distinct permutation, because at least one number in C is fixed.
The elements of Sn\S are partitioned by these classes, since every permutation is contained in exactly one class. Every class has size m!. Therefore, m! divides |Sn\S|=|Sn|-|S|. Since m! divides |Sn|, then m! divides |S|.
Here's another question:
Let n>3 and k>2. Take a sequence of integers (a
i) of length n, where each integer is between 0 and k inclusive. Apply the following step to this sequence over and over:
Take any four consecutive numbers in the sequence and call them a,b,c,d from left to right. Do one of the following two:
* Replace a with a-1, b with b+2, and d with d-1, provided all numbers remain between 0 and k.
* Replace a with a+1, c with c-2, and d with d+1, provided all numbers remain between 0 and k.
Prove that eventually, the whole procedure must come to an end (only finitely many steps can be taken) no matter what.