maths proofs

[Phantom-II]

Hey guys,  on my assighment:

Find the 125th number in the bijection of the positive rational numbers with the natural numbers
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, 1/7, 3/5, ...

okay I just dont really understand it, what does this even mean? the 125th number in that sequence?

[nubs]

Hmm let's see if I remember this correctly:

Say we have two sets: X=(1,2,3,4) and Y=(a,b,c,d)
If there is a function that exists that directly pairs the elements of these two functions, it is said to be a bijective function, otherwise known as a bijection.
i.e
1->a
2->b
3->c
4->d
As you can tell each element in the first set can be uniquely paired with an element in the second set and there are no unpaired elements. This is a bijection.
A function that takes X->Y, where each element in X can be uniquely mapped to Y, and no element is left out
So f(1)=d etc etc

This question is asking for the bijection of the positive rational numbers with the natural numbers
So we have our two sets of numbers. The set of rational numbers and the set of natural numbers.

Someone will have to pick up my slack, because it's been almost a year since I've even heard of the term 'bijection', but I believe this is the way to go about finding the 125th number in this particular sequence.

      1      2      3      4     ...
1  1/1   2/1   3/1   4/1
2  1/2   2/2   3/2   4/2
3  1/3   2/3   3/3   4/3
4  1/4   2/4   3/4   4/4
.
.
.
Now f(1)=1
f(2)=1/2
f(3)=2/1 etc etc as given in the question
So I've mapped it out in a way that might be easier to follow
The ordering is diagonal, from bottom right to top left, if you compare it to the order of terms in the question you'll see what I mean
So according to my map, the first term is 1/1
Now I'll go down one row to 1/2 (which is my second term) and move upwards in a diagonal fashion to the next number, which is 2/1 (which will be my third term)
Then I'll go down another row to row 3, start at the left most number (1/3, which would be my fourth term) and move upwards in a diagonal direction to 3/1, which would be my 5th term.

The numbers in bold are kind of just a guide, you use them to make up the fractions. So if you're in the column number 5 and the row numbered 2, the number in that 'slot' would be 5/2, follow?

The numbers I have crossed out are numbers that have already been stated. So consider 2/2. If I did not cross it out and left it in the sequence, it would have been the 5th term (remember the ordering). So f(5)=2/2=1/1
But we already f(1)=1/1, and as we said earlier, to have a bijection you need to have a one to one mapping, so one element can't map onto two different elements. As a result we cross out all the numbers that can be simplified to something that has already been mapped.

Now all you need to do is continue what I have done until you get to the 125th number. I remember my AM1 tutor last year saying this is the only written way of solving it. So from where I left off, add the number 5 to the bold row and column, fill in the new 'slots' with the fractions, cross out the fractions that have already been mapped out and keep doing it until you have 125 numbers.

Sorry if I haven't explained it too well, it's just been ages since I covered this stuff :/
If someone could confirm what I've done that'd be greattt

Also there would be a few bits and pieces I've missed out on in terms of formally wording the stuff. They get pretty pedantic over that, I think you need to mention something about the sets being countable or something, but you should've gone through the formal method in your tutorials or lectures I reckon

[Phantom-II]

Hi, thanks for the reply. after a while of tediously writing it out i think iv got the answer. I srsly can not believe theyd make us do something like this

iv got another question with proof by mathematical induction:
for every positive integer, prove that (x-y) is a factor of (x^n - y^n)

so far iv got P(1) is true
if P(k) is true;
P(k-1) = (x^(k+1) - y^(k+1))
P(k-1) = (x*x^k - y*y^k)
......
any sort of help would be welcome :p

[brightsky]

P(n): (x-y) divides (x^n - y^n)
P(1): (x-y) divides (x-y) is true
assume P(k) is true.
P(k): (x-y) divides (x^k - y^k). that is, x^k - y^k = m*(x-y)
P(k+1): (x-y) divides (x^(k+1)-y*(k+1))
now x^(k+1) - y*(k+1) = x*x^k - y*y^k = x*x^k - x*y^k + x*y^k - y*y^k = x(x^k-y^k) + y^k*(x-y) = m*x*(x-y) + y^k*(x-y) = (x-y)(mx+y^k) which is obviously divisible by (x-y)

so P(k+1) is true so by PMI, P(n) is true.

[Fluttershy]

Accelerated Maths 1? I just finished the assignment today, I was so confused with the bijections thing for about a week 

Conformal mapping, though, that has got to be the most obscure and frustrating question ever -_- I spent all day on it and I'm not even sure my answer is correct... I'll ask you guys about it once we've handed it in, in order to avoid cheating/collusion

[Phantom-II]

ahh i see. thanks brightsky!

haha yeaahhh i was questioning whether i really needed to just write out a huge square for that question.

i thought the conformal mapping was alright, took me less time than some other questions. It sounds amazing to actually be able to apply it too, the graphs were so hektik.

[Special At Specialist]

Hey guys,  on my assighment:

Find the 125th number in the bijection of the positive rational numbers with the natural numbers
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, 1/7, 3/5, ...

okay I just dont really understand it, what does this even mean? the 125th number in that sequence?

I haven't studied this topic and I don't know what a bijection is, but I noticed a pattern in the series of numbers, so I decided to follow through with it until I reached the 125th number. The answer I got was 7/13.

The pattern I noticed was this: everytime you reach x/1, the following number will be 1/(x + 1). So if you reach 3/1, the next number will be 1/4. If you reach 9/1, the next number will be 1/10, etc.

Also, your aim is to go from 1/x to x/1 before you can proceed to 1/(x + 1), but you must follow these rules: every pair of numbers between and including 1/x and x/1 must add to the same number, which is x + 1. Whatever you add to the first number, you must subtract from the second number, so you could turn a 1/x into a 2/(x - 1) or a 3/(x - 2) for example.

But the key is that you must choose the lowest number to add to 1 which will reach x after a multiple of times, without repeating the same numbers. What I mean by that is: if you had 1/6 and you want to get to 6/1, you can proceed by going 2/5, 3/4, 4/3, 5/2, 6/1. But if you had 1/13, you must get to 13/1 without ending up on 7/7.

There is a trick to this: if you have 1/x, then use the number (x - 1) as the maximum number of "leaps" to get to x/1. So if you are on 1/13, then there are a maximum of 12 leaps to get there. The problem is that you cannot land on a double square, which is (x + 1) / 2, or in this case, 7. A double square will always be a result of hitting half the maximum number of leaps. So in this case, with a maximum of 12 leaps to get from 1/13 to 13/1, you cannot land on the 6th leap. How can you do this? Well if you count by 1's, you will land on 6. If you count by 2's, you will land on 6. If you count by 3's, you will land on 6. But if you count by 4's, you will skip 6, so that's what you have to do. Add 4 to the first number and subtract 4 from the second number. To get from 1/13 to 13/1, you must go: 1/13, 5/9, 9/5 and then 13/1.

With an odd number of leaps (ie. where x is an even number in the case of 1/x to x/1), you can just count by 1's, since you will never hit a fractional leap (half of an odd number is a fraction). So if you were on 1/8 for example, you would just go to 2/7 then 3/6 then 4/5 etc. So it's only when you go from something like 1/11 to 11/1, or 1/13 to 13/1, when you actually have to stop and figure out what you're doing.

So with that said, I will show you how to hit the 125th number in the sequence:

1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, 1/7, 3/5, 5/3, 7/1, 1/8, 2/7, 3/6, 4/5, 5/4, 6/3, 7/2, 8/1, 1/9, 9/1, 1/10, 2/9, 3/8, 4/7, 5/6, 6/5, 7/4, 8/3, 9/2, 10/1, 1/11, 3/9, 5/7, 7/5, 9/3, 11/1, 1/12, 2/11, 3/10, 4/9, 5/8, 6/7, 7/6, 8/5, 9/4, 10/3, 11/2, 12/1, 1/13, 5/9, 9/5, 13/1, 1/14, 2/13, 3/12, 4/11, 5/10, 6/9, 7/8, 8/7, 9/6, 10/5, 11/4, 12/3, 13/2, 14/1, 1/15, 3/13, 5/11, 7/9, 9/7, 11/5, 13/3, 15/1, 1/16, 2/15, 3/14, 4/13, 5/12, 6/11, 7/10, 8/9, 9/8, 10/7, 11/6, 12/5, 13/4, 14/3, 15/2, 16/1, 1/17, 17/1, 1/18, 2/17, 3/16, 4/15, 5/14, 6/13, 7/12, 8/11, 9/10, 10/9, 11/8, 12/7, 13/6, 14/5, 15/4, 16/3, 17/2, 18/1, 1/19, 3/17, 5/15, 7/13

So the 125th number is 7/13, the 126th number would be 9/11 and so on.

Perhaps there's a better way of doing this, I'm not sure. For example, if it asked me to find the 1000th number in the sequence, I'd look for some kind of shortcut. I could save some time by skipping the even numbers, so when you go from 1/12 to 12/1, you know that there are 12 numbers involved, when you go from 1/14 to 14/1, you know that there are 14 numbers involved etc. So that method saves a bit of time, rather than writing them all out. However, it would still take a while.