Somebody else with the math problems now
June 3rd, 2014 at 5:12:34 PM
permalink
Here's one (although it's not exactly original):
A function F can take any of the integers 1 through 5 and return an integer from 1 through 5. For example, F(n) = 1 and F(n) = n are both valid functions.
How many distinct such functions are there if, for any particular function F, F(F(n)) = F(F(1)) for all integers n from 2 to 5?
(Two functions are "distinct" if there exists at least one n such that F(n) <> G(n).)
A function F can take any of the integers 1 through 5 and return an integer from 1 through 5. For example, F(n) = 1 and F(n) = n are both valid functions.
How many distinct such functions are there if, for any particular function F, F(F(n)) = F(F(1)) for all integers n from 2 to 5?
(Two functions are "distinct" if there exists at least one n such that F(n) <> G(n).)
June 3rd, 2014 at 5:31:27 PM
permalink
Another way of saying this, every value in the codomain is mapped to the same value.
If they're all mapped to the same value, this is fulfilled trivially. There are five such functions.
If they're mapped to two values, there are two ways those two values could be mapped, seven ways the other three could be mapped - since they can't all be mapped to the final number - and 10 such partitions, for 140 possibilities.
If they're mapped to three values, there 10 partitions, three ways those three values could be mapped, and only two ways the other two could be mapped, since neither can be mapped to the final number or there wouldn't be three values. That's another 60.
They can't be mapped to four or five values, since those would have to be mapped to the same number, which creates a contradiction. There are 205 such functions.
If they're all mapped to the same value, this is fulfilled trivially. There are five such functions.
If they're mapped to two values, there are two ways those two values could be mapped, seven ways the other three could be mapped - since they can't all be mapped to the final number - and 10 such partitions, for 140 possibilities.
If they're mapped to three values, there 10 partitions, three ways those three values could be mapped, and only two ways the other two could be mapped, since neither can be mapped to the final number or there wouldn't be three values. That's another 60.
They can't be mapped to four or five values, since those would have to be mapped to the same number, which creates a contradiction. There are 205 such functions.
The trick to poker is learning not to beat yourself up for your mistakes too much, and certainly not too little, but just the right amount.
June 3rd, 2014 at 7:30:38 PM
permalink
That is the correct answer, although I got it in a different way:
In case anyone is wondering, this was taken from one of the American Invitational Mathematical Examinations, except that the original had the domain and range from 1 to 7 instead of from 1 to 5.
First, show that there is exactly one N under the conditions such that F(N) = N:
If two (or more) F(N) = N, then let F(A) = A and F(B) = B; as a result, F(F(A)) = F(A) = A and F(F(B)) = F(B) = B, but that contradicts the "all F(F(N)) values are equal" condition.
If no F(N) = N, then let F(1) = A <> 1; if F(A) = 1, then F(F(1)) = F(A) = 1 and F(F(A)) = F(1) = A, but again, that means that not all F(F(N)) values are equal. If F(A) = B <> 1 and <> A, then F(F(1)) = F(A) = B, but F(F(A)) = F(B) and F(B) <> B, so F(F(1)) = B and F(F(A)) <> B.
Assume F(1) = 1; this means F(F(1)) = 1, so F(F(N)) = 1 for all N.
If none of the other F(N)s = 1, then F is not valid as F(F(N)) <> 1 for N <> 1.
If one other F(N) = 1, then the other three Ns must equal that value; there are 4 values for N and 13 = 1 triple for the other three values (since each one can be 1 or N); this is 4 functions.
If two other F(N)s = 1, then the other two Ns must equal one of the two values; there are 6 pairs for the two Ns and 22 = 4 pairs for the other two values; this is 24 functions.
If three other F(N)s = 1, then the remaining N must equal one of the three values; there are 4 triples for the three Ns and 31 = 3 values for the remaining value; this is 12 functions.
If all four other F(N)s = 1, this is valid; this is 1 functions.
Thus the total number of functions for F(1) = 1 is 4 + 24 + 12 + 1 = 41.
Since there are 5 values for N such that F(N) = N, the total number of functions is 41 * 5 = 205.
If two (or more) F(N) = N, then let F(A) = A and F(B) = B; as a result, F(F(A)) = F(A) = A and F(F(B)) = F(B) = B, but that contradicts the "all F(F(N)) values are equal" condition.
If no F(N) = N, then let F(1) = A <> 1; if F(A) = 1, then F(F(1)) = F(A) = 1 and F(F(A)) = F(1) = A, but again, that means that not all F(F(N)) values are equal. If F(A) = B <> 1 and <> A, then F(F(1)) = F(A) = B, but F(F(A)) = F(B) and F(B) <> B, so F(F(1)) = B and F(F(A)) <> B.
Assume F(1) = 1; this means F(F(1)) = 1, so F(F(N)) = 1 for all N.
If none of the other F(N)s = 1, then F is not valid as F(F(N)) <> 1 for N <> 1.
If one other F(N) = 1, then the other three Ns must equal that value; there are 4 values for N and 13 = 1 triple for the other three values (since each one can be 1 or N); this is 4 functions.
If two other F(N)s = 1, then the other two Ns must equal one of the two values; there are 6 pairs for the two Ns and 22 = 4 pairs for the other two values; this is 24 functions.
If three other F(N)s = 1, then the remaining N must equal one of the three values; there are 4 triples for the three Ns and 31 = 3 values for the remaining value; this is 12 functions.
If all four other F(N)s = 1, this is valid; this is 1 functions.
Thus the total number of functions for F(1) = 1 is 4 + 24 + 12 + 1 = 41.
Since there are 5 values for N such that F(N) = N, the total number of functions is 41 * 5 = 205.
In case anyone is wondering, this was taken from one of the American Invitational Mathematical Examinations, except that the original had the domain and range from 1 to 7 instead of from 1 to 5.
