Thread: Extra Credit Discrete Math HW Help Needed

Hello,
My professor gave the class an extra credit HW question in which I need help in. I have to write a close form function f(p/q) = y.

The problem is I have to prove that the rational #'s Q are countable such that
positive Q = { p/q | p , q exist a positive Z}

She gave us a chart:

p/q 1 2 3 4 5

1 1/1 1/2 1/3 1/4 1/5

2 2/1 2/2 2/3 2/4 2/5

3 3/1 3/2 3/3 3/4 3/5

4 4/1 4/2 4/3 4/4 4/5

5 5/1 5/2 5/3 5/4 5/5

She said if we count horizontal it won't work cause we will have infinity and same goes for vertical, so she said if we go diagonally we can do it.

Q = {1/1, 1/2, 2/1, 1/3, 2/2, 3/1.....}
N = {1,2,3,4,5,6.....} <- countable

She want us to come up with a function such that if she wanted to find out what fraction is the 34th number is, she would know.

Ive been staring at this for quite a while and decided I need help. If anyone can hint me anything that would help, would be appreciated.
Thanks in advance.

Originally Posted by ff4930

Hello,
My professor gave the class an extra credit HW question in which I need help in. I have to write a close form function f(p/q) = y.

The problem is I have to prove that the rational #'s Q are countable such that
positive Q = { p/q | p , q exist a positive Z}

She gave us a chart:

p/q 1 2 3 4 5

1 1/1 1/2 1/3 1/4 1/5

2 2/1 2/2 2/3 2/4 2/5

3 3/1 3/2 3/3 3/4 3/5

4 4/1 4/2 4/3 4/4 4/5

5 5/1 5/2 5/3 5/4 5/5

She said if we count horizontal it won't work cause we will have infinity and same goes for vertical, so she said if we go diagonally we can do it.

Q = {1/1, 1/2, 2/1, 1/3, 2/2, 3/1.....}
N = {1,2,3,4,5,6.....} <- countable

She want us to come up with a function such that if she wanted to find out what fraction is the 34th number is, she would know.

Ive been staring at this for quite a while and decided I need help. If anyone can hint me anything that would help, would be appreciated.
Thanks in advance.

The trouble with this is that in your table each rational appears an infinite
number of times, for instance 1 appears at every place on the diagonal.

Means you may be in for some messy bookkeeping.

RonL

I can see a pattern with counting it diagonally but I can't seem to come up with a function that will me to look up any specific number.

1/1, 1/2, 2/1, 1/3, 2/2 ,3/1 ,1/4 ,2/3 ,3/2 ,4/1 ,1/5 ,2/4, 3/3, 4/2, 5/1

the numerator counts up meaning 1 then it goes 1,2, then 1,2,3

and the denominator counts down.