harsh.champ wrote:find the number of all rational numbers m/n such that
(1) 0 < m/n < 1
(2) m and n are relatively prime
(3) m * n = 25!
(1)255
(2)256
(3)128
(4)64
(5)None of these
Really don't think this can reasonably be solved in under 5 minutes, but hey, let's try.
Ok, given that relatively prime means no primes in common:
If m*n = 25!, then m and n must share all the primes between 2 and 23, namely:
2, 3, 5, 7, 11, 13, 17, 19 and 23.
However, there are multiples of many of those primes, so we really need to think about all the other numbers as well:
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24 and 25.
Now, since m and n can't have any primes in common, certain of these numbers must be paired together.
For example, whichever one of them has 2 also has to have 3, since 6, 12, 18 and 24 are multiples of both of those numbers. Similarly, 10 is a multiple of 2 and 5, so that also must be included. 14 is 2*7, 18 is 2*9, 22 is 2*11, so:
2, 3, 5, 7, 9 and 11 must all be factors of the same one of m or n.
This means that 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24 and 25 must all be factors of one of m or n, leaving only:
13, 17, 19 and 23 up for grabs.
Given that m/n is a proper fraction, we know that m < n, so:
n MUST be a multiple of 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24 and 25.
With 4 numbers left, each one can be assigned to either m or n (after all, we could have m=1 and n = 25!).
There are 16 ways to distribute 4 objects to 2 different groups, so 16 is our final answer... choose (5).
I'd love to see the official explanation - where is this from?
