Find the number of rational numbers r ( 0 < r < 1 ) such that when r is written as a fraction in lowest terms, the numerator and denominator sum to 1000.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
"Unsimplifyable" ...... yes, it really should be a word. :) Nice handiwork with the totient function; I did it the old-fashioned way with arithmetic progressions.
Log in to reply
lol, I thought it was already a word. I usually don't post unoriginal problems unless they are either really good or I found a really good/unique solution to it. This falls into the latter category.
... The totient function is simply then number times 1-1/each factor multiplied out and ...
Small typo. It should be each "prime factor".
oh, i forgot totient function. id did it with arithmetic.
Nice with the totient. I just used that numbers coprime with 10 (and thus 1000) are those ending in 1, 3, 7, or 9. 4/10 * 500 = 200
We have that the set of these rational numbers is from 9 9 9 1 to 5 0 1 4 9 9 where each each element m n has n + m = 1 0 0 0 and m n is irreducible.
We note that m n = m 1 0 0 0 − m = m 1 0 0 0 − 1 . Hence, m n is irreducible if m 1 0 0 0 is irreducible, and m 1 0 0 0 is irreducible if m is not divisible by 2 or 5 . Thus, the answer to the question is the number of integers between 9 9 9 and 5 0 1 inclusive that are not divisible by 2 or 5 .
We note there are 4 9 9 numbers between 5 0 1 and 9 9 9 , and
Using the Principle of Inclusion and Exclusion, we get that there are 4 9 9 − 2 4 9 − 9 9 + 4 9 = 2 0 0 numbers between 5 0 1 and 9 9 9 are not divisible by either 2 or 5 , so our answer is 2 0 0 .
Nice and simple!
I understand you came to the correct answer, but why are the 49 integers divisible by 10 being added back after subtracting the integers divisible by 2 and 5?
Log in to reply
Maybe look at the principle of inclusion exclusion wiki
If you didn't add the numbers divisible by 10 again, you would have subtracted them twice : Once in the set of numbers divisible by 2 and once in the set of numbers divisible by 5!
That is the principle of in-/exclusion to count the elements of finite sets: ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ , A , B finite sets
Log in to reply
Copied and pasted from AOPS, 2014 AIME question number 3. Not cool man!! That's called plagiarizing.
Log in to reply
@Mr. Krabs The problem header states "AIME I problem #3". While the year could have been given as well, it is pretty clear from the header that the author did not invent the problem, and gave the necessary references, wouldn't you agree?
If o < b a < 1 is in reduced form, then g c d ( a , b ) = 1 and 1 ≤ a < b . If a + b = 1 0 0 0 , then the total number should be half of Euler's Totient function at 1 0 0 0 , which gives 2 0 0 .
i do this too
Let's say that the number r takes the form p/q where p and q are coprime integers and p=1000-q (as required).So p/q takes the form (1000/q - 1).We also have Phi(1000)=400.The other requirement is that 0<r<1 => 0< (1000/q - 1)<1 => 1<1000/q<2 => 500<q<1000.Thus we have that q must fall in the range of (500,1000).We have one more requirement that r is written as a fraction in lowest terms which means q must be coprime to 1000.Therefore we need to find all such integers q which are coprime to 1000 and falls in the range (500,1000).
We know that gcd(a,b) =gcd(a-b,a) which means gcd(1000,499)=gcd(501,1000); gcd(1000,498)=gcd(502,1000);. .........gcd(1000,1)=gcd(499,1000). So we have that every coprime to 1000 in the interval [1,500] has sort of its image in [500,1000] and there are equal number of coprimes to 1000 in the intervals [1,500] and [500,1000] and because 500 is not coprime to 1000, the number of coprimes to 1000 in the interval (500,1000)=1/2(Phi 1000)= 400/2=200.Hence there are * 200* such rational numbers.
We are looking for the fractions 0 < 1 0 0 0 − a a < 1 such that g cd ( a , 1 0 0 0 − a ) = g cd ( a , 1 0 0 0 ) = 1
Thus we are looking for all 1 ≤ a ≤ 5 0 0 such that g cd ( a , 1 0 0 0 ) = 1 .
The desired number is ϕ ( 5 0 0 ) = 2 0 0
This sounds like the weak version of Erdos conjecture, and I'm using the word weak only to clarify
Problem Loading...
Note Loading...
Set Loading...
assume that the number takes the form b a .
Where a and b are coprime and a+b=1000
∴ , a = 1 0 0 0 − b
Rewriting our fraction yields
b 1 0 0 0 − b
b 1 0 0 0 − b b
Note that this means that b must be coprime with 1000, aka, not divisible by 2 or 5 since is must be unsimplifyable.)
The largest value of a is 499 and the min for b is 501, since a<b for b a < 1
Now, here's the main reason I posted this. I wanted to show a small short cut to the continuation of the problem. The first 3/4ths of my solution is the same, but the last quarter (this half) is different.
We need to find all numbers co-prime to 1000, but less than 500, using Euler's totient function ( ϕ ) on 1000 would give us numbers greater than 500, thus, to find out the answer, we will compute ϕ ( 5 0 0 ) . In the short: The totient function is simply then number times 1-1/each prime factor multiplied out and it finds the number of numbers less then n coprime to n.
ϕ 5 0 0 = 5 0 0 ( 1 − 2 1 ) ( 1 − 5 1 ) = 2 0 0