BrainDen.com - Brain Teasers

Question

A huge bin contains distinctly numbered balls, and you choose two of them at random.

I give you 2 to 1 odds that the numbers will be relatively prime.

For example,

You pick 6 and 13. I win \$1.

You pick 5 and 25. You win \$2.

Do you take the bet?

Recommended Posts

• 0

it looks like the probability of two numbers being relatively prime is almost 60%. If I win 2 dollars 40% of the time and lose \$1 60% of the time then I should make 20 cents on average. right? If that is true, then i will play.

Share on other sites

• 0

Yes, I would take the bet ... but I do not have a strong proof

Just based on odd and even numbers if we get 2 even numbers they are
relatively prime. So 1/4 of the time you would expect a positive pay off. If
for a moment we rule out any odd number as being
co-prime, we would get -1 three times out of four

The worst expected pay off [based on this poor assumption] would be

P*min = (1*(+2) + 3*(-1))/4 = -1/4

If just 1 out of 9 combinations involving an odd number were relatively
prime, the Pay off would  go to zero [making it a fair game].

[this is where things get shaky].

I have examined numbers up to 65 and found that if at least one number is
odd, the chances of the pair being relatively prime is closer to 2/9 which would
return a positive expected pay off.

I am sure that someone out there has an elegant solution, that I look forward
to seeing!

Share on other sites

• 0

So, if I am correct in assuming "relatively prime" simply means that one number is not evenly divisible by the other, then here are my initial thoughts:

You have a 1/n chance of first drawing a "1"...in which case, you will win automatically (1/1 chance)

You have a 1/n chance of first drawing a "2"...in which case, you will win if the second number is even OR a factor of 2 (aka: 1)

You have a 1/n chance of first drawing a "3"...in which case, you will win if the other number is a multiple of 3 OR a factor of 3 (aka: 1)

You have a 1/n chance of first drawing a "4"...in which case, you will win if the other number is a multiple of 4 OR a factor of 4 (aka: 1 or 2)

...

You have a 1/n chance of drawing "x"...in which case, you will win if the other number is a multiple of x OR a factor of x

So let FACT(x) = number of factors of number x...we can then write our chance of winning to be:

SUM (1/n * (1/x + FACT(X)/n)), x=1..n

Which clearly just get worse and worse the more balls there are in the bin...in which case, I would only take the bet if there were visibly "few" (less than 20 or so) balls in the bin.

Now, I suppose my above reasoning only holds if we assume all the numbers 1-n are in the bin...if you have completely random/arbitrary numbers...then, my reasoning probably completely falls through. Again, just my first thoughts. I am also curious to see what others come up with.

Share on other sites

• 0

100% loss

if the bin contains even numbers starting at 4

Share on other sites

• 0

i'd take the bet.

assuming an even distribution of numbers, say the numbers from 1 to 10,000.

you have a 1/4 chance of getting both diviable by 2, a 1/9 chance of both divisable by 3, a 1/25 chance of both diviable by 5, and so on.

the first one in of itself however gives you break even expected payout. the remaining ones increases it.

Share on other sites

• 0

There's a 1/4 probability that both numbers are even. If they are not both even, there is still a 1/9 probability that they are both divisible by 3. Perhaps the key feature here is realizing that divisibility by one prime is independent of divisibility by other primes. Anyway, this yields a probability of 1/4+3/4*1/9 = 3/12+1/12 = 1/3 that 2 or 3 is a common prime factor. As there are more possible common prime factors, the probability of winning the bet is >1/3. So I'd take the bet.

Share on other sites

• 0

Where did the bin come from?

Suspecting that bonanza was trying swindle me out of my money, I would refuse the bet.

Share on other sites

• 0

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

This time the skeptics missed a chance to win some coin. Edit: Since the coprime probability is so close to 60% (slightly larger) I pondered making the odds 3:2,

forcing a calculation in order to be sure. It's not a simple calculation.

But I decided to be nice. yeah I believe it is actually 6/pi2.

How do you arrive at this answer? If I'm not mistaken, the answer is approximated by running the following program indefinitely, given a full list of primes in order P1 = 2, P2 = 3, P3 = 5, and so on:

1: set S = 0, i = 1

2: set S = S + (1-S)/Pi2

3: set i = i+1

As this program keeps going, S should tend to the desired probability. Not being a programmer, I haven't been able to run this for large numbers, but it seems to me that it would converge closer to 0.4 than 0.6. I would be very surprised if it converged at exactly 6/pi2, as this would indicate a clear correlation between pi and the set of primes.

Share on other sites

• 0

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.

Share on other sites

• 0

Most of you got it.

BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.

That checks with 6/pi2 = 0.607927101854.....

Share on other sites

• 0

Suppose you pick two random numbers less than n, then

• [n/2]2 pairs are both divisible by 2.
• [n/3]2 pairs are both divisible by 3.
• [n/5]2 pairs are both divisible by 5.
• ...

(Here [x] is the greatest integer less than or equal to x, usually called the floor function.) So the number of relatively prime pairs less than or equal to n is (by the inclusion/exclusion principle):

2 - sum([n/p]2) + sum([n/pq]2) - sum([n/pqr]2) + ...

here the sums are taken over the primes p,q,r,... less than n. Letting mu(x) be the möbius function this is

so the desired constant is the limit as n goes to infinity of this sum divided by n2, or sum(mu(k)/k2)

(sum over positive integers k).

But this series times the sum of the reciprocals of the squares is one, so the sum of this series, the desired limit, is 6/ 2. This number is approximately sum(mu(k)[n/k]2)

(sum over positive integers k

60.7927...%

• 1
Share on other sites

• -1

Most of you got it.
BMAD made a close estimate of the probability, which is actually just slightly greater than 60% to be co-prime.

This time the skeptics missed a chance to win some coin. Edit: Since the coprime probability is so close to 60% (slightly larger) I pondered making the odds 3:2,

forcing a calculation in order to be sure. It's not a simple calculation.

But I decided to be nice. Edited by bonanova

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.