As the evens chosen --> oo , the probability that r=s will become less and less probable.

I'm in Calculus 2, so excuse me if I'm completely wrong. But this is just how my feeble mind sees it :).

Note that this assumes that you are picking the original numbers 'at random'. This is not at all the same as picking r or s at random, which is what you seem to have done. r and s are much more likely to be small numbers than big numbers simply because not many numbers are divisible by large powers of two but loads are odd. For example, the probability that r=100 is absolutely tiny; about 0.0000000000000000000000000000004. So although there are, as you say, a crapload of such numbers, there is a much, much larger crapload of numbers with r < 100.

Thankyou

sfwc
<><

I didn't mean to come off and say that the possibility of r being equal to s is an absolute 0. I meant that for infinite numbers, the chances are so small, that it is esentially 0.

Take for the moment just the first 100 natural numbers. 50 are odd (2k+1), and 50 even (2k).

Of those 50, 25 are 2 times an odd number (odd*2^r, r=1)
25 are 2 times an even number (odd*2^r, r>1).

So in 1 in 2 cases r=0 (the number is odd). In 1 in 4 cases, r=1 and in the remaining 1 in 4 r>1. In half of the remainder, the number is 4 times an odd number, so r=2 in 1 case in 8. And so on. The proportion of cases where r=n is 1 in 2^(n+1).

Those proportions remains constant (approximately) no matter how many numbers you take. They apply to both the numerator and the denominator, so that the probability that r=s=1 = 1/4*1/4 = 1/16.
The probability that r=s=2 = 1/8*1/8 = 1/64. So the total probability that r=s is given by the sum of the series
1/16 + 1/64 + 1/256.... or sum(i=1..inf) 1/(4*i)^2 = 1/12.

The probability of odd/odd is therefore 1/4 + 1/12 = 4/12 = 33%

Occasionally teachers are right.

(This is only an expansion of what sfwc wrote but I hope this helps.)

The mistake you make in assuming the probability that r=s tends to zero as n tends to infinity is akin to the mistake of assuming that the proportion of numbers ending in 5 tends to zero. You're effectively trying to get a probability by dividing infinity by infinity, which is undefined, and indeed, forbidden.

A moderately useful but inelegant tip in this sort of situation is to calculate the probability for the first 100 numbers, the first 1000, and so on, and see if it does indeed reduce in the increasing finite cases.

This will give some complications, since, for example, if N is odd then you won't have N/2 even numbers (there will be (N-1)/2 of them). I think the answer 1/3 will still be valid, but you have to carefully prove that those corrections can be neglected for large N.

That's why I weaselled out with "Those proportions remains constant (approximately) no matter how many numbers you take."

> So what is usually done here is to take the set {1,2,...,N} and
> then to consider the asymptotics as N goes to infinity.
>
>This will give some complications, since, for example, if N
>is odd then you won't have N/2 even numbers (there will be
>(N-1)/2 of them).

And the proportion of odds (r=0 as earlier) after N numbers will be (N-1)/2N. In the limit that looks pretty much like 1/2. It's more complicated for r>0, but for r=1 the relevant expressions are (writing n as 4k + x, x=0..3) k/(4k+x), which again is 1/4 in the limit.

In fact, the general expression for r, writing n as 2^(r+1)*k + x, x=0..2^(r+1)-1, is
k/(2^(r+1)*k+x)
which always has limit 1/2^(r+1).

> I think the answer 1/3 will still be
>valid, but you have to carefully prove that those
>corrections can be neglected for large N.

Thanks guys!

P=limit(Sum(p_r(N),r=0..infinity),N->infinity).

The catch is that we have to prove that limit and Sum can be swapped to pass to

P=Sum(1/2^(2*r+2),r=0..infinity).

I don't follow that at all. What we're looking for is (2*k+1)*2^r/N for FIXED r as N --> infinity and 0<=2*k+1<=N/2*r.

You can if you like rewrite that as (2*k+1)*2^r/(2*j+1)*2^s, but ir's wrong to have the same power of 2 in the denominator as in the numerator. And it's unnecessarily confusing to have n and N representing two different values.

Sum that over r and you get 1. (Or you better had.)
>
>The catch is that we have to prove that limit and Sum can be
>swapped to pass to
>
>P=Sum(1/2^(2*r+2),r=0..infinity).

Now, to get an irreducible fraction of the form (2*i+1)/(2*j+1) we have to start with (2*i+1)*2^r/((2*j+1)*2^r), for which we should pick two numbers divisible by 2^r but not by 2^(r+1). I denoted the probability of this event by p_r(N) -- it depends both on r and on N. For this we just have to square the ratio found above, so we get a value -- again, vaguely speaking -- close to (1/2^(r+1))^2. So the answer to the original problem (probability that we get an irreducible fraction odd/odd) is

P(N)=Sum(p_r(N),r=0..infinity).

All the terms starting from some r0 are zero, but r0 depends on N. Now we want to find the limit(P(N), N->infinity). If we can change the order of sum and limit operations, we get what we want:

limit(p_r(N),N->infinity)=1/2^(2*r+2),

sum(1/2^(2*r+2),r=0..infinity)=1/3.

But we gotta have uniform convergence for that.

{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, ...

then each ODD multiple of 2 occurs in exactly one set of the partition.

Similarly the ODD multiples of 4 occur with probaility 1/8 by considering a partition of the natural numbers into sets of 8 consecutive numbers.

I meant to mention this in my previous message. Cheers.

Tony