[superprismatic]

Let P be a permutation on 100 things.

For that P, let N be the smallest number

such that P^N=P. What is the largest

possible value of N over some such P?

In other words, how large a cycle can be made

by applying a 100-long permutation over and

over again?

Edited April 5, 2010 by superprismatic

[bushindo]

maximum cycle length of 100

[Guest]

i would say 100 factorial.

a permutation is simply a reordering.

for example, with 3 items you have 6 permutations before the cycle repeats.

with four items, you have 24 permutations before the cycle repeats. etc.

[Guest]

Wow! Just wrapping my mind around the problem was a great exercise...still trying to figure out an approach to the solution. I knew I should have payed attention in all those crazy math classes.

[Guest]

okay i think i understand the problem now...

http://mathworld.wolfram.com/PermutationCycle.html

so your question basically boils down to, how disordered can you make the set? and when it's disordered as it can possibly be, how many cycles can you apply before you repeat the same order?

am i understanding correctly now?

[superprismatic]

okay i think i understand the problem now...

http://mathworld.wolfram.com/PermutationCycle.html

so your question basically boils down to, how disordered can you make the set? and when it's disordered as it can possibly be, how many cycles can you apply before you repeat the same order?

am i understanding correctly now?

I don't quite see how that reference applies to this

problem. I intentionally didn't use the term 'cycle'

because that term is used in the way permutations can

be written. But your comment about disorder may be

a way of looking at it, if I understand you correctly.

I was going to post the following before I saw your

response -- it may help clarify things:

Bushindo's answer is way too small and phillip1882's is

way too big! Suppose, I had a permutation on 5 things.

Let P be the permutation that takes ABCDE to EABCD. Then

ABCDE -> EABCD -> DEABC -> CDEAB -> BCDEA -> ABCDE, and

so, P⁵=P. But what if P took ABCDE to CABED. Then,

ABCDE -> CABED -> BCADE -> ABCED -> CABDE -> BCAED -> ABCDE

shows that P⁶=P. So, 5 is too small because I found

a permutation on 5 things which requires six steps to return to

the start.

However, 5! = 120. I'd like to see someone find a permutation

on 5 things which requires 120 steps to get back to the start.

I can't.

[bushindo]

I don't quite see how that reference applies to this

problem. I intentionally didn't use the term 'cycle'

because that term is used in the way permutations can

be written. But your comment about disorder may be

a way of looking at it, if I understand you correctly.

I was going to post the following before I saw your

response -- it may help clarify things:

Bushindo's answer is way too small and phillip1882's is

way too big! Suppose, I had a permutation on 5 things.

Let P be the permutation that takes ABCDE to EABCD. Then

ABCDE -> EABCD -> DEABC -> CDEAB -> BCDEA -> ABCDE, and

so, P⁵=P. But what if P took ABCDE to CABED. Then,

ABCDE -> CABED -> BCADE -> ABCED -> CABDE -> BCAED -> ABCDE

shows that P⁶=P. So, 5 is too small because I found

a permutation on 5 things which requires six steps to return to

the start.

However, 5! = 120. I'd like to see someone find a permutation

on 5 things which requires 120 steps to get back to the start.

I can't.

You're right, it's way too small

I would say that the maximum is the product of the first 9 prime numbers

2*3*5*7*11*13*17*19*23 = 223092870

[Guest]

based on superprismatic's examples, you can group the items into prime numbers, and rotate. that would give bushido's result.

[superprismatic]

You're right, it's way too small

I would say that the maximum is the product of the first 9 prime numbers

2*3*5*7*11*13*17*19*23 = 223092870

This is not the largest cycle possible. Can anyone find a larger one?

[bushindo]

I'm not sure how to improve the cycle length. I'd like to see the solution. Nice problem, by the way.

[superprismatic]

I'm not sure how to improve the cycle length. I'd like to see the solution. Nice problem, by the way.

I have a larger cycle length than yours but I haven't proven

that it is the best. My idea was to find a partition of 100

such that the LCM of the numbers was large. So, I didn't just

stick with primes. My best was 232,792,560 using cycles of

lengths 19,17,16,13,11,9,7,5,and 3. Note that the 3 adds

nothing to the magnitude of the cycle length, it just makes

it all add up to 100. I threw the problem out there without

thinking too much about it. I know of no theory behind this

kind of thing. I don't think that Group theory addresses this

type of maximization problem.