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,.....,n².

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