Difference between revisions of "2005 PMWC Problems/Problem I3"
(→Solution) |
m (→See also) |
||
(One intermediate revision by the same user not shown) | |||
Line 34: | Line 34: | ||
==See also== | ==See also== | ||
+ | {{PMWC box|year=2005|num-b=I2|num-a=I4}} | ||
[[Category:Introductory Combinatorics Problems]] | [[Category:Introductory Combinatorics Problems]] |
Latest revision as of 10:30, 18 September 2008
Problem
Let be a fraction between and . If the denominator of is and the numerator and denominator have no common factor except , how many possible values are there for ?
Solution
We let .
We find the ranges for , disregarding the restriction that must be relatively prime with 455.
, .
,
Since must be relatively prime to 455, it cannot have any prime factors equal to any in . Thus we use the Principle of Inclusion-Exclusion and complementary counting:
There are 43 multiples of 5 in that range.
There are 31 multiples of 7 in that range.
There are 16 multiples of 13 in that range.
There are 6 multiples of 7*5=35 in that range.
There are 3 multiples of 5*13=65 in that range.
There are 2 multiples of 7*13=91 in that range.
There aren't any multiples of 455 in that range.
Now there are numbers total, so subtracting the unsuccessful numbers(79) from that we get possible values of .
See also
2005 PMWC (Problems) | ||
Preceded by Problem I2 |
Followed by Problem I4 | |
I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 |