2005 PMWC Problems/Problem I3

From AoPSWiki

Revision as of 15:30, 18 September 2008 by 1=2 (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Problem

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$ ?

Solution

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.

$43+31+16-6-3-2+0=79$

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$ .

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

Personal tools

Navigation

Search

Toolbox

2005 PMWC Problems/Problem I3

From AoPSWiki

Problem

Solution

See also