use everything you want
8
✅ Answers
? Favorite Answer
The proof is straightforward.
Let’s use the greedy algorithm that bites from the fraction as much as it can. That means that for fraction a/b we select such n that 1/n < a/b < 1/(n-1)
Left ineqaulity means na >b or na-b>0
Right inequality means (n-1)a < b, or na-b<a.
Finally
0 < na-b < a
Now consider the left-over a/b-1/n = (an-b)/bn.
As you can see this fraction is < 1/n and at the same time numerator becomes less (an-b<a).
First property would result to the fact that on next iteration we select m>n. Second property would result to the fact that numerator would decrease at every step, until it reaches 0 in at most ‘a’ steps (a is numerator in original fraction).
So I proved that there is such decomposition and it can be reached by no more than ‘a’ fractions (a is numerator in original fraction).
I can prove even more, that ANY positive fraction can be presented this way.
There is a well known property of the sum of harmonic sequence S(n) = 1+1/2+1/3+1/4+… that it is unbounded. It means that for every fraction a/b there is such n, that S(n)<=a/b<S(n+1)
It is easy to see that a/b-S(n) < S(n+1)-S(n) = 1/(n+1).
Now we just need to split this fraction a/b-S(n) as we discussed above and we can see that all denominators will be unique and more than (n+1).
This problem has a lot of blind alleys, but one way to prove this is to consider a rational fraction of the form:
a/(an-b)
where n > a > b are integers. Subtracting 1/n from it, we have:
a/(an-b) – 1/n = (an – an + b)/(n(an-b)) = b/(an² – bn)
where we replace an² – bn with bn’ – c, where b > c. Thus, we have a remainder fraction where b < a, and this process can be repeated until we’re left with a fraction of the form 1/n”, and the algorithmic process ends with a finite sum of fractions. It should be noted that for any given rational fraction 0 < x < 1, there is a multiplicity of ways it can be expressed in the form 1/a + 1/b + 1/c + …, where a, b, c… are all distinct integers.
This problem reminds me of Turing’s Halting Problem, in that what we’re being asked to do is to show that if we subtract fractions of the form 1/n successively from the original rational fraction, the process will halt eventually. It’s kind of fun to try doing it using random fractions, eventually it halt with sometimes some pretty far out fractions.
Addendum: If for any reason during the algorithmic process we come up with 2 fractions that are alike, we can use amir11elad’s method of replacing one of the fractions with two others, and if that causes another match, we can repeat, until after a finite number of step there will be no further matches and all the fractions would be distinct.
Addendum 2: Here’s the proof again, more concisely:
1) Subtract fractions of the form 1/n from the rational number 0 < x < 1 successively (with distinct n) until we are left with a fraction of the form a/(an-b), where n > a > b are integers.
2) Subtract 1/n from this fraction, so that we are left with a fraction of the form b/(bn-c), where n > b > c are integers.
3) Continue until we’re left with the fraction of the form 1/n. If you have a series of integers a > b > c > …., eventually, you will end up with 1. That’s why the series will always be finite.
Addendum 3: Hear ye, Alexey V
************REVISED*************
I’ve added a little which I hope you’ll agree points to a proof
A very good problem.
For any integer n, I’ve changed this to not only finitely many, but n – 1 sets, which is all we need, (***1/n has infinitely many sets***) A1, A2, . . . , A(n-1) associated with it such that for each k,
Ak = {reciprocals of a finite no. of distinct integers the sum of which is 1/n} and furthermore Ai and Aj are pairwise disjoint.
Now if we can show the existence of such Ak for each 1/n then we’ve solved your little puzzle since
p/n = 1/n + . . . + 1/n (p < n times 1/n)
= A1 + . . . + Ap . . . Et voila!
Now for the real work::
for any integer n > 1,
A1 = {1/n}
1/n = 1/(n + 1) +1/n(n+1). So, here,
A2 = {1/(n + 1), 1/n(n+1)}
But now we can break up each of the two terms using the same formula
1/n = 1/(n +2) + 1/(n+1)(n+2) + 1/(n^2 + n + 1) +
1/(n^2 + n)((n^2 + n + 1) and A3 has the 4 terms
We can keep on doing this. Let me give you a feel for the way things progress:
Starting with A1 = {1/n},
A2,A3, A4 . . . will contain respectively 1/(n + 1), 1/(n +2), A(n+ 3) . . . , as well as
(respectively, 1/(n^2 +n),1/(n^2 +3n + +2), . . .
I can go further but I doubt if there’s anyone still following this,
In any case, it appears to work but needs some bright trick to make things a lot less unwieldy.
These are called Egyptian fractions. Your question was proved by Fibonacci. Sorry, I don’t have his proof but here is a link discussing the fractions.
http://mathworld.wolfram.com/EgyptianFraction.html
And here is a link to an Egyptian fraction calculator. It provides two methods for calculating it. The first method is called the “greedy algorithm”. Using this method you always extract the largest unit fraction (i.e. the fraction of the form 1/n that has the lowest possible denominator) and then make successive similar extractions from the remainder until the remainder is itself a unit fraction. This is the most intuitive method, but does not always give the “best” answer. The second method produces the shortest sequence of unit fractions that add to the desired fraction.
Do you mean every rational 0<a/b<1 can be written in the form:
1/n_1 + 1/n_2 + … + 1/n_k, where n_1,…,n_k are all natural numbers and pairwise different?
For example 2/3 = 1/2+1/6
3/4 =1/4+1/2
2/5 = 1/5+1/6+1/30
3/5 =1/10+1/2 ; 4/5=1/5+1/2+1/10
Let me think…
let’s look at this one: 1/n – 1/(n+1) = 1/(n(n+1))
if we leave the 1/n on the left side we get:
1/n = 1/(n+1) + 1/(n(n+1))
this is a proof that every rational, can be written as sum of 1/n fractions with different denominator.
Amir
Every rational number can be
written in two ways as decimal
number.Either with finite number
of decimal digits(i.e. 1/4=0.25)
or as a periodic decimal number
(i.e. 1/3=0.333….)
Starting from the second case
you can write
1/3=3/10+3/10^2+3/10^3+……
=1/[10/3]+1/[(10^2)/3]+….
or another example
25/99=0.252525…=
25/10^2+25/10^4+……=
1/[(10^2)/25]+1/[(10^4)/25]+..
Now if we have the first case
i.e 3/10=0.3 and knowing that
1=0.999999….. we have
3/10=(3/10)*1=(3/10)*0.9999…=
(3/10)*(9/10+9/10^2+…..)=
27/10^2+27/10^3+…=
1/[(10^2)/27]+1/[(10^3)/27]+….
.5??? its been a while since i hav done that stuff. it has to be ne where between 0-1 (0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9)