Original -> Grain oil

We can decompose $\gamma$ into cycles and we have that the period of $\gamma$ is given by the least common multiple of the periods of the cycles. The period of a cycle is given by the number of elements that contains. $\gamma$ could have cycles with $1$ element, cycles with $2$ elements, cycles with $3$ elements,..., and cycles with $8$ elements. So we have that $lcm(1,2,3,4,5,6,7,8)=840$ is a multiple of the period and it is the minimum number of repetitions that ensure us that the set is back in its original configuration. So we must apply other $839$ permutations.

We use standard notation to write a permutation on eight elements in terms of its cycles. For example, (1 2 3 4 5)(6 7 8) is a permutation with two cycles. One cycle sends 1 to 2, 2 to 3, 3 to 4, 4 to 5, and 5 back to 1, and the other cycle sends 6 to 7, 7 to 8, and 8 back to 6.

First consider the answer to the problem for a single, given permutation on eight elements. If you start with a set of eight elements, the minimum number of times you must apply the permutation to get the set back to its original configuration is the least common multiple of the cycle lengths. For example, if the permutation is (1 2 3 4 5)(6 7 8), you must apply it 15 times to return the set to its original configuration. This is because the elements in the cycle of length 5 return to their original configuration every 5 times, and the elements in the cycle of length 3 return to their original configuration every 3 times. So it takes 15 times to get the elements in both cycles to both return to their original configuration simultaneously.

But the problem is asking for the minimum number of times needed to return ANY permutation to its original configuration. So we must look at all the cycle lengths that could occur in ANY permutation of eight elements, and take the least common multiple of all of those. This just turns out to be the least common multiple of the numbers 1 through 8 (since these are all the possible lengths of any cycle), which is $2*2*2*3*5*7$ , or 840.

Finally, reading the problem carefully, we see that one permutation has already been applied, so you need to apply the permutation 839 more times to make sure you always get back to the original configuration. The answer is 839.

A permutation results in some subsets to be shuffled amongst each other. More specifically, those subsets form a partition of the original set. For example, a permutation of 12345678 into 45768132 involves 164 being rotated, 285 being rotated, 37 being swapped.

So when considering minimum number of times to guarantee a return to the original order, we need to first consider the subsets. Each subset of size n requires n applications of the permutation to return the subset to the original order. Then for the entire set to return to its original order, it requires each subset to return to its original order on the same application of the permutation. This occurs at the least common multiple of the subset sizes. In the example given in the first paragraph, it would be 6 applications, to return subsets of 2 and 3 to their original orders simultaneously.

With all that established, we can now look at the partitioning of the 8-element set, and look at all the possible subset sizes. Clearly, the possible subset sizes are 1 through 8. So to guarantee that any permutation would return to the original state, we need to guarantee that any possible subset would return to the original subset at the same time. So LCM of 1 through 8 is 840. Subtracting out the original application to get 839.

Within each permutation there must be at least one "cycle" where a certain n number of elements are confined to n number of positions. For example, a permutation may have 3 elements cycling around 3 different positions, and the other 5 elements cycling around 5 positions, while another may simply have all 8 elements cycling around all 8 positions.

To guarantee that we get back our initial permutation, we need to ensure that all cycles have been gone through a whole number of times. Since $1 \leq n \leq 8$ , the answer is lcm(1, 2, 3, 4, 5, 6, 7, 8) - 1 = 839.

First, note that every permutation can be written as a product of distinct cycles.

We can then write $\gamma=S_1 \cdots S_k$ where $S_1, \cdots ,S_k$ are disjoint cycles. Define $n_i= |S_i|$ for $i \in {1, \cdots,k}$ . Now $\gamma^{n_i}$ fixes the elements of $S_i$ .

For example, if $\gamma = (132)(45678)$ , then $\gamma^3 = (132)(78456)$ .

So the smallest number which fixes all elements of $\gamma$ is $|\gamma| = lcm[n_1,…,n_k]$ .

Now, if $\gamma$ is a permutation on 8 elements, then to determine the order of $\gamma$ , we need to only consider the possible disjoint cycle structure of $\gamma$ . For simplicity, denote a permutation with order $n$ as $(n)$ . Then we have

$(8)$

$(7)(1)$

$(6)(2)$

$(6)(1)(1)$

$(5)(3)$

$(5)(2)(1)$

$(5)(1)(1)(1)$

$\vdots$

The mentioned possibilities of $\gamma$ have orders $8, 7, 6, 5, 15$ and the unmentioned possibilities of $\gamma$ have orders $12, 4,3,6,2,1$ . Thus the order of $\gamma$ is $lcm[8,7,6,5,15,12,4,3,2,1] = 840$ . Because $\gamma$ has been applied once already, $\gamma$ needs to be applied $840 - 1 = 839$ more times.

The period (minimum number of repeated invokations required to get back) of a permutation is the least common multiple of the lengths of the constituent cycles. To garantee to get back to the original configuration we must apply the same unknown permutation for n times, where n is the least common multiple of the period of each possible permutation. So n must be the least common multiple of all possible lenght of a costituent cycle. Becouse all integer from 1 to 8 can be a valid lenght, n = lcm(1,..,8)=840

Just as an example, consider $\gamma$ as the permutation with the following mapping: $1 \rightarrow 2 \rightarrow 3 \rightarrow 1, 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 4$ . Notice that there are two separate "loops," and that an element from one loop stays in its own loop all the time. Let the size of a loop be the number of elements involved in it, e.g., this example has two loops of size $3$ and $5$ .

In general, $\gamma$ will have $n$ loops (with $n \leq 8$ ) of size $x_1, x_2, ..., x_n$ , such that $\sum x_i = 8$ . The period of a permutation (the number of times required for the set to return to its original configuration) will be the lowest common multiple of the $x_i$ 's because each individual loop must each be in its original configuration, and this simultaneously happen for all loops at the lowest common multiple of the loop sizes.

Thus, for a particular $\gamma$ , the required number of times we must apply it for the set to return to its original configuration, the period, is $\lcm(x_1, x_2, ..., x_n)$ . But since we do not know which permutation $\gamma$ is, the number of times we must apply $\gamma$ to guarantee that the set is in its original configuration is the lowest common multiple of the periods of all possible $\gamma$ .

However, this is simple because $1 \leq x_i \leq 8$ for every $\gamma$ . Furthermore, there is a $\gamma$ with a loop of size $k$ for all $k$ from $1$ to $8$ (namely, they are the permutations with loops of size $(x_1,x_2)=(1,7),(2,6),(3,5),(4,4)$ and the permutation with loop of size $x_1=8$ ). So the answer is the lowest common multiple of all integers from $1$ to $8$ minus the single initial application of $\gamma$ , which is $2^3 \times 3 \times 5 \times \times 7 - 1 = 839$ .

Denote the eight elements 1,2,...,8. I will first give an example that illustrates my notation for a permutation.

[(123),(45),(67)]

This permutation takes 1 to 2, 2 to 3, 3 to 1, 4 to 5, 5 to 4, 6 to 7, 7 to 6, and 8 stays put.

Iterating any permutation will eventually put the set back into its original order. The question is, how many times must we iterate any one permutation? Put yet another way, given a natural number, n, is there a permutation that requires a minimum of n iterations to put the set back in order? I will list permutations requiring n iterations

1. The identity permutation (no element is moved).
2. [(12)]
3. [(123)]

4. [(1234)] and so on like this through

5. [(12345678)]

6. No permutation requires exactly 9 iterations.
7. [(12)(34567)]. (12) requires 2 iterations, (34567) requires 5, so if we execute them simultaneously we will need 10 permutations to get back to where we started. It should now be more clear why there is no permutation requiring 9 iterations.
8. None
9. [(123)(4567)]
10. None
11. None
12. [(123)(45678)] No permutations for n \geq 16

Since we don't know which permutation \gamma is, it could require any of the above number of iterations to return the set to its starting point. Therefore, we need the least common multiple of all the numbers on the list, which is 840.

Since \gamma has already been applied one time, the correct answer is to apply it 839 more times.

The cycles of $\gamma$ could be of any length from 1 to 8. Thus, the total number of times we apply $\gamma$ must be divisible by every number from 1 to 8. The least common multiple of the set $\{1,2,3,4,5,6,7,8\}$ is $8 \times 7 \times 5 \times 3 = 840$ , so $\gamma$ must be applied a multiple of 840 times in order to be sure we are back at the starting configuration. Since $\gamma$ has already been applied once, we need only apply if $839$ times.