Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 iTest Problems/Problem 44"

(Created page with "== Problem == A positive integer <math>n</math> between <math>1</math> and <math>N=2007^{2007}</math> inclusive is selected at random. If <math>a</math> and <math>b</math> are n...")
 
(Solution to Problem 44)
 
Line 3: Line 3:
 
A positive integer <math>n</math> between <math>1</math> and <math>N=2007^{2007}</math> inclusive is selected at random. If <math>a</math> and <math>b</math> are natural numbers such that <math>a/b</math> is the probability that <math>N</math> and <math>n^3-36n</math> are relatively prime, find the value of <math>a+b</math>.
 
A positive integer <math>n</math> between <math>1</math> and <math>N=2007^{2007}</math> inclusive is selected at random. If <math>a</math> and <math>b</math> are natural numbers such that <math>a/b</math> is the probability that <math>N</math> and <math>n^3-36n</math> are relatively prime, find the value of <math>a+b</math>.
  
−
== Solution ==
+
==Solution==
 +
 
 +
Factoring <math>2007^{2007}</math> results in <math>3^{4014} \cdot 223^{2007}</math>, and factoring <math>n^3 - 36n</math> results in <math>n(n+6)(n-6)</math>.  In order for <math>N</math> and <math>n^3 - 36n</math> to be relatively prime, then <math>n^3 - 36n</math> can not have multiples of <math>3</math> or <math>223</math>, and <math>n</math> can not be <math>6</math> away from a multiple of <math>223</math>, so use [[complementary counting]].
 +
 
 +
<br>
 +
There are <math>\frac{2007^{2007}}{3}</math> numbers in the range that are a multiple of <math>3</math>, and there are <math>3 \cdot \frac{2007^{2007}}{223} - 1</math> numbers from <math>1</math> to <math>2007^{2007}</math> that are multiples of <math>223</math> or <math>6</math> away from a multiple of <math>223</math>.  However, there are <math>3 \cdot \frac{2007^{2007}}{669} - 1</math> numbers that are a multiple of <math>3</math> and a multiple of <math>223</math> or six away from a multiple of <math>223</math>.  Using [[PIE]], there are  a total of <math>\frac{229}{669} \cdot 2007^{2007}</math>  values of <math>n</math> that do not work.
 +
 
 +
<br>
 +
That means the number of values of <math>n</math> that work is <math>\frac{440}{669} \cdot 2007^{2007}</math>, and since a number is picked at random from <math>2007^{2007}</math> values, the probability that <math>N</math> and <math>n^3 - 36n</math> are relatively prime is <math>\frac{440}{669}</math>.  Thus, <math>a+b = \boxed{1109}</math>.
 +
 
 +
==See Also==
 +
{{iTest box|year=2007|num-b=43|num-a=45}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]
 +
[[Category:Intermediate Probability Problems]]

Latest revision as of 22:24, 14 June 2018

Problem

A positive integer $n$ between $1$ and $N=2007^{2007}$ inclusive is selected at random. If $a$ and $b$ are natural numbers such that $a/b$ is the probability that $N$ and $n^3-36n$ are relatively prime, find the value of $a+b$.

Solution

Factoring $2007^{2007}$ results in $3^{4014} \cdot 223^{2007}$, and factoring $n^3 - 36n$ results in $n(n+6)(n-6)$. In order for $N$ and $n^3 - 36n$ to be relatively prime, then $n^3 - 36n$ can not have multiples of $3$ or $223$, and $n$ can not be $6$ away from a multiple of $223$, so use complementary counting.


There are $\frac{2007^{2007}}{3}$ numbers in the range that are a multiple of $3$, and there are $3 \cdot \frac{2007^{2007}}{223} - 1$ numbers from $1$ to $2007^{2007}$ that are multiples of $223$ or $6$ away from a multiple of $223$. However, there are $3 \cdot \frac{2007^{2007}}{669} - 1$ numbers that are a multiple of $3$ and a multiple of $223$ or six away from a multiple of $223$. Using PIE, there are a total of $\frac{229}{669} \cdot 2007^{2007}$ values of $n$ that do not work.


That means the number of values of $n$ that work is $\frac{440}{669} \cdot 2007^{2007}$, and since a number is picked at random from $2007^{2007}$ values, the probability that $N$ and $n^3 - 36n$ are relatively prime is $\frac{440}{669}$. Thus, $a+b = \boxed{1109}$.

See Also

2007 iTest (Problems, Answer Key)
Preceded by:
Problem 43 		Followed by:
Problem 45
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • TB1 • TB2 • TB3 • TB4
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_44&oldid=95164"