Author |
Topic: A 2080 Puzzle (Read 764 times) |
|
K Sengupta
Senior Riddler
Gender: 
Posts: 371
|
 |
A 2080 Puzzle
« on: Jun 29th, 2007, 7:57am » |
 Quote  Modify
|
Let S = {1; 2; 3; 4; 5; 6; 7}
Analytically determine the number of maps g from S to S such that g2080(x) = x for every x (- S.
Note: The superscript denotes iteration: g1(x) = g(x) and gn(x) = g(gn-1(x)) for all n > 1.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: A 2080 Puzzle
« Reply #1 on: Jun 29th, 2007, 8:55am » |
Quote Modify
|
It looks like 7!/10 = 504
[edit] ... well ... I thought it did before Sengupta's reply . 
What happened is that I dismissed length 1 cycles.[/edit]
|
| « Last Edit: Jul 3rd, 2007, 2:57am by Grimbal » |
IP Logged |
|
|
|
K Sengupta
Senior Riddler
Gender:
Posts: 371
|
|
Re: A 2080 Puzzle
« Reply #2 on: Jul 2nd, 2007, 8:31am » |
Quote Modify
|
The solution to the foregoing puzzle is furnished hereunder as follows:
SOLUTION:
At the outset, each g must be one-to-one in S, since there would otherwise exist an x^2(- S such that there is no y^ 2(- S with g(y) = x, which would contradict g(g2079(x)) = g2080(x) = x.
g must therefore be a permutation of the elements of S.
We know that every permutation of a finite set can be expressed uniquely as the product of cyclic permutations with no common elements. The problem is therefore equivalent to finding the number of such products of cycles, such that the 2080-th iteration is the identity.
In order for this to be the case, the length of each cycle must be a divisor of 2080. The lengths of such cycles can therefore be either 1, 2, 4 or 5. We now consider three cases.
(I) There exists a cycle of length 5.
There are Comb(7, 5) ways to select the 5 numbers in the cycle, and 4! ways to build a cycle of 5 given numbers. Since the remaining numbers can either build a cycle of length two, or two of length one, there are comb(7, 5)*4!*2 = 1008
such maps.
(II) There exists a cycle of length four.
There are comb(7, 4) ways to select the four numbers in the cycle, and 3! ways to build a cycle of four given numbers. The remaining three numbers can either each build a cycle of length one, or there are three ways in which to
choose two to build a cycle of length two, leaving the other to build a cycle of length one. There are therefore comb(7, 4)*3!*4 = 840 such maps.
(III) The only other cycles that exist are of lengths one and two.
There is one such map with no cycle of length two (the identity).
There are comb(7, 2) = 21 such maps with precisely one cycle of length two. There are ˝*comb(7,2)*comb(5,2) = 105 such maps with precisely two cycles of length two (choosing2 from 7, then 2 from the remaining 5, and then dividing by the number of repetitions of the chosen cycles).
Finally there are (1/(3!))*comb(7, 2)*comb(5,2)*comb(3,2) = 105 such maps with precisely three cycles of length two (for the analogous reason as for two such cycles).
Summing, we thus obtain:
1008 + 840 + 1 + 21 + 105 + 105 = 2080
|
| « Last Edit: Jul 2nd, 2007, 8:50am by K Sengupta » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print