All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Getting Maps In 2080 (Posted on 2007-08-17) Difficulty: 4 of 5
Let S = {1; 2; 3; 4; 5; 6; 7}

Analytically determine the number of maps f from S to S such that f2080(x) = x for every x belonging to S.

Note: The iteration is denoted by the superscript, such that f1(x) = f(x) and
fn(x) = f(fn-1(x)) for all n > 1.

See The Solution Submitted by K Sengupta    
Rating: 4.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution one case missing--computer lists all combinations Comment 4 of 4 |
(In reply to solution by Charlie)

The cases were supposed to show all combinations of 5, 4, 2 and 1 that add up to 7, but one was left out: 4, 1, 1, 1. It was found by the following:

FOR no5s = 0 TO 1
FOR no4s = 0 TO (7 - 5 * no5s) / 4
FOR no2s = 0 TO (7 - 5 * no5s - 4 * no4s) / 2
  no1s = 7 - 5 * no5s - 4 * no4s - 2 * no2s
  FOR i = 1 TO no5s: PRINT "5, "; : NEXT
  FOR i = 1 TO no4s: PRINT "4, "; : NEXT
  FOR i = 1 TO no2s: PRINT "2, "; : NEXT
  FOR i = 1 TO no1s: PRINT "1, "; : NEXT
  PRINT
NEXT
NEXT
NEXT

whose output was:

1, 1, 1, 1, 1, 1, 1,
2, 1, 1, 1, 1, 1,
2, 2, 1, 1, 1,
2, 2, 2, 1,
4, 1, 1, 1,
4, 2, 1,
5, 1, 1,
5, 2,

The contribution of 4, 1, 1, 1 is given as follows:

There are C(7,4)= 35 ways of choosing the participants in the cycle of 4. Again, any cycle of 4 can done in 6 different ways, as the lowest of the four can go to any of 3 numbers, and that number can go to either of 2 numbers.

So this accounts for 35*6=210 functions.

Added to the 1870 functions (permutations) found previously, this brings the total to 2080, in fact the same 2080 as in the title.


  Posted by Charlie on 2007-08-20 10:36:24
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information