All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Geometric Generalization (Posted on 2013-02-28) Difficulty: 3 of 5
Three positive integers are chosen at random without replacement from 1,2,....,64. What is the probability that the numbers chosen are in geometric sequence?

Order of choice doesn't matter. For example, 4-1-2 would qualify as numbers in geometric sequence.

Bonus Question:
Generalise this result (in terms of n) covering the situation where three positive integers are chosen at random without replacement from 1,2,.....,n2.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
full solution Comment 6 of 6 |
I am going to answer the bonus first, then apply it to n=8.

First, the common ratio, r, must be rational.  This can see that since the first term is an integer, then any irrational ratio would result in an irrational second term.  Now since we can have the 3 terms in any order we can place them in increasing order and thus have r>1.  r can not be 1 because there is no replacement.

So now let r=p/q  with 1<=q<p  and gcd(p,q)=1.  Now if the first term is a, then the three terms will be:
a,  ap/q,  and ap^2/q^2.  Since gcd(p,q)=1 then q^2 divides a and thus we can say that a=kq^2 for some integer k>=1.  So now we can state the three terms as
kq^2, kpq, kp^2
Finally, we can place a restriction on k because we need
kp^2<=n^2 thus
1<=k<=n^2/p^2
since k>=1 then we know p^2<=n^2 or p<=n thus
2<=p<=n.  So putting all of these restrictions togeather we have
2<=p<=n
1<=q<p  with gcd(p,q)=1
1<=k<=floor(n^2/p^2)
Now we just need to count the number of possible values for q and k for each p.
q:  what we want are all the integers less than p which are coprime with p.  This is actually the definition of the Euler Phi function so this is simply Phi(p)
k:  this is simple floor(n^2/p^2)

so the number of geometric sequences is given by the following summation:
S(n)=sum[ Phi(p) * floor(n^2/p^2) ] with p=2 to n

Now to get the probability we need to know the number of ways of choosing 3 from n^2, which is simply C(n^2,3)

So the desired probability is S(n)/C(n^2,3)

Finally, placing n=8 into this equation we get 29/20832


  Posted by Daniel on 2013-02-28 13:21:38
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information