During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

Difference between revisions of "2005 PMWC Problems/Problem I3"

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


Let $x$ be a fraction between $\frac{35}{36}$ and $\frac{91}{183}$. If the denominator of $x$ is $455$ and the numerator and denominator have no common factor except $1$, how many possible values are there for $x$?


We let $x=\frac{y}{455}$.

We find the ranges for $y$, disregarding the restriction that $y$ must be relatively prime with 455.

$\frac{91}{183}\leq \frac{y}{455}$

$183y\geq 91*455=41405$, $y\geq 227$.

$36y\leq 35*455=15925$, $y\leq 441$

Since $y$ must be relatively prime to 455, it cannot have any prime factors equal to any in $455=5*7*13$. 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 $441-227+1=215$ numbers total, so subtracting the unsuccessful numbers(79) from that we get $\boxed{136}$ possible values of $x$.

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
Invalid username
Login to AoPS