An Identity in Permutations
Let's say that we have 100 balls and 100 boxes, both labelled by the numbers 1 to 100, and that ball 1 is in box 1, ball 2 is in box 2, etc.. Let be a uniform shifting (i.e. whatever ball in box is shifted to box , for fixed ) of the balls' positions such that no ball is in its original box, i.e. ball is shifted to a box with a number not equal to . What is the minimal number of compositions of upon the balls required so that every ball returns to its original position?
Inspired by Linus Setiabrata (pretty much his problem).
The answer is 100.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
We can view P as a permutative cycle: Let the balls' positions be p 1 , p 2 , . . . , p 1 0 0 and a shift between two positions be written as a 1 − > a 2 where a i represents some unique p i . Then we can express the whole of P as a 1 − > a 2 − > a 3 − > . . . − > a 1 0 0 − > a 1 . Since a i is arbitrary (but unique), every permutation can be expressed in this manner and so the length of every permutative cycle is 100. Interestingly, this implies that for any permutation P, the number of compositions of P required so that we have a permutative identity is equal to the number of positions P shifts.