The user-friendly version of this content is available here.
The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.
This problem trains for: AMC-10, AIME, Math Kangaroo 9-10.
A sequence of numbers contains all consecutive integers from 1 to 41 in increasing order. An operation consists of splitting the first 20 numbers and placing them, in order, in the 'spaces' between the remaining 21 numbers. How many distinct sequences can be obtained by repeating this operation any number of times?
Let us work with a simpler example such as one with just 9 consecutive numbers. For the operation to make sense, the number of terms in the initial sequence must be odd.
Let us arrange these numbers on a circle, like this:
The result of applying the operation one time is:
Notice that the 'distance' between any two consecutive numbers has increased to 2.
Define the distance as the difference in the respective ranks of the terms.
Apply the operation a second time:
and notice how the distance between any two consecutive numbers has increased to 4.
After each application of the operation, the distance between consecutive numbers (with 9 'consecutive' to 1) doubles.
Since the length of the sequence is finite the distance cannot double indefinitely.
Indeed, at some point, the distance will exceed the number of terms and then will wrap around.
The number of possible distances is equal to the number of distinct remainders that we get by dividing successive powers of 2 by the number of terms:
In other words, we have to seek the smallest positive power of 2 that is equivalent to 1 modulo the number of terms:
For a sequence of 41 numbers, we have:
Multiply by 2 to obtain the following:
we can square the last congruence to obtain:
there are 20 distinct sequences that can be generated by performing the operation any number of times.