MHB Which fractions can you make (with proof)?

[cshao123]

Suppose you have the fraction 1/1. If you can make a fraction x/y, you can also make y/(2x). Also, if you can make x/y and a/b where GCD(x,y)=GCD(a,b)=1, you can make (x+a)/(y+b). Which fractions can you make?

 

[Greg]

Which fractions can I make?! From what?? :)

 

[cshao123]

Which fractions can I make?! From what?? :)

Sorry I didn't word this very well! So you can make 1/2 by using the y/2x rule, and continue using the rules in the question to make more fractions.

 

[topsquark]

Suppose you have the fraction 1/1. If you can make a fraction x/y, you can also make y/2x. Also, if you can make x/y and a/b where GCD(x,y)=GCD(a,b)=1, you can make (x+a)/(y+b). Which fractions can you make?

I'm stuck, too but I'll give it a shot.

Okay, so we have 1/1 = x/y right? So are we taking x = 1 and y = 1? But where did the x/(2y) thing come in? Under what rules do we admit 1/(2 * 1) = 1/2.

Guessing time. You have GCD(x, y) = 1. Now, x = 1, y = 1 works... 1/1. So does x = 1, y = 2 mean the fraction 1/2 follows the rules? That would imply that any combination of x, y where GCD(x, y) = 1 holds true. So it's true for any x and y that are relatively prime. That would mean that we can choose x = 6, and y = 11 and create the fraction 6/11?

Am I on the right track here?

-Dan

 

[I like Serena]

Suppose you have the fraction 1/1. If you can make a fraction x/y, you can also make y/(2x). Also, if you can make x/y and a/b where GCD(x,y)=GCD(a,b)=1, you can make (x+a)/(y+b). Which fractions can you make?

Hi cshao123! Welcome to MHB! (Wave)

Starting with 1/1, we can find 1/(2.1)=1/2.
Then we can add them (1+1)/(2+1)=2/3.
Invert again for 3/(2.2)=3/4.
Keep adding 1/1 for 4/5, 5/6, 6/7, 7/8, ...

Anyway, it looks like we can make all fractions $x/y$ with $\frac y2 \le x \le y$, doesn't it?
We can verify that those production rules will only generate new fractions within those bounds.
It's a bit more difficult to check that we won't 'miss' any fractions.
At least I can find all of them up y=13. (Thinking)

 

[cshao123]

Hi cshao123! Welcome to MHB! (Wave)

Starting with 1/1, we can find 1/(2.1)=1/2.
Then we can add them (1+1)/(2+1)=2/3.
Invert again for 3/(2.2)=3/4.
Keep adding 1/1 for 4/5, 5/6, 6/7, 7/8, ...

Anyway, it looks like we can make all fractions $x/y$ with $\frac y2 \le x \le y$, doesn't it?
We can verify that those production rules will only generate new fractions within those bounds.
It's a bit more difficult to check that we won't 'miss' any fractions.
At least I can find all of them up y=13. (Thinking)

Thank you! How would you go about proving you can't make any fractions below 1/2?

 

[I like Serena]

Thank you! How would you go about proving you can't make any fractions below 1/2?

We start with 1/1 which satisfies the condition.

Suppose we have created a set of possible fractions $x/y$ that all satisfy $1/2\le x/y \le 1$ (the initial set does).
Then $1 \le y/x \le 2$, so that $1/2 \le y/(2x) \le 1$, which again satisfies the condition.
And with $b/2 \le a \le b$ and $y/2 \le x \le y$, we have $b/2 + y/2 \le a + x \le b + y$, so that $1/2 \le (a+x)/(b+y) \le 1$, which again satisfies the condition.
So all fractions that can be generated are between 1/2 and 1/1.

 

[cshao123]

We start with 1/1 which satisfies the condition.

Suppose we have created a set of possible fractions $x/y$ that all satisfy $1/2\le x/y \le 1$ (the initial set does).
Then $1 \le y/x \le 2$, so that $1/2 \le y/(2x) \le 1$, which again satisfies the condition.
And with $b/2 \le a \le b$ and $y/2 \le x \le y$, we have $b/2 + y/2 \le a + x \le b + y$, so that $1/2 \le (a+x)/(b+y) \le 1$, which again satisfies the condition.
So all fractions that can be generated are between 1/2 and 1/1.

Ah ok that’s nice! Any ideas how to prove no fractions are left out?