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

 Geometric Generalization (Posted on 2013-02-28)
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.)
 computer solution | Comment 4 of 6 |

For the main case of n = 8; n^2=64, there are 58 positive outcomes out of the C(64,3)=41664 possible combinations of 3 chosen numbers, making the probability 58/41664 = 29/20832 ~= 0.0013920891 or 1/718.3448275862069:

1  2  4
1  3  9
1  4  16
1  5  25
1  6  36
1  7  49
1  8  64
2  4  8
2  6  18
2  8  32
2  10  50
3  6  12
3  9  27
3  12  48
4  6  9
4  8  16
4  10  25
4  12  36
4  14  49
4  16  64
5  10  20
5  15  45
6  12  24
6  18  54
7  14  28
7  21  63
8  12  18
8  16  32
8  20  50
9  12  16
9  15  25
9  18  36
9  21  49
9  24  64
10  20  40
11  22  44
12  18  27
12  24  48
13  26  52
14  28  56
15  30  60
16  20  25
16  24  36
16  28  49
16  32  64
18  24  32
18  30  50
20  30  45
24  36  54
25  30  36
25  35  49
25  40  64
27  36  48
28  42  63
32  40  50
36  42  49
36  48  64
49  56  64

The following program produces a table of probabilities for other n up to 20 (i.e., n^2 up to 400):

DECLARE FUNCTION gcd# (a#, b#)
DECLARE FUNCTION combi# (n#, r#)
DEFDBL A-Z
FOR n = 2 TO 20
nsq = n * n
tot = 0
FOR a = 1 TO nsq - 1
FOR c = a + 1 TO nsq
b = INT(SQR(a * c) + .5)
IF b * b = a * c THEN tot = tot + 1: ' PRINT a; b; c
NEXT
NEXT
c = combi(nsq, 3)
g = gcd(tot, c)
tot2 = tot / g: c2 = c / g
PRINT USING "## ####      ####### /######### #### / ####### #.##########"; n; nsq; tot; c; tot2; c2; tot / c
NEXT n

FUNCTION combi (n, r)
c = 1
FOR i = n TO n - r + 1 STEP -1
c = c * i
NEXT
FOR i = 2 TO r
c = c / i
NEXT
combi = c
END FUNCTION

FUNCTION gcd (a, b)
dnd = a: dvr = b
DO
q = INT(dnd / dvr): r = dnd - q * dvr
dnd = dvr: dvr = r
LOOP UNTIL dvr = 0
gcd = dnd
END FUNCTION

produces the following table including the 29 / 20832 probability when n^2 = 64, as in the first part of the puzzle:

` n  n^2         ways     out of         reduced         decimal                     (combinations)    fraction       probability 2    4            1 /        4       1 /       4    0.2500000000 3    9            4 /       84       1 /      21    0.0476190476 4   16            8 /      560       1 /      70    0.0142857143 5   25           16 /     2300       4 /     575    0.0069565217 6   36           27 /     7140       9 /    2380    0.0037815126 7   49           40 /    18424       5 /    2303    0.0021710812 8   64           58 /    41664      29 /   20832    0.0013920891 9   81           80 /    85320       2 /    2133    0.000937646510  100          105 /   161700       1 /    1540    0.000649350611  121          128 /   287980      32 /   71995    0.000444475312  144          158 /   487344      79 /  243672    0.000324206313  169          198 /   790244      99 /  395122    0.000250555514  196          237 /  1235780     237 / 1235780    0.000191781715  225          278 /  1873200     139 /  936600    0.000148409116  256          336 /  2763520      21 /  172720    0.000121584117  289          382 /  3981264     191 / 1990632    0.000095949418  324          435 /  5616324     145 / 1872108    0.000077452819  361          502 /  7775940     251 / 3887970    0.000064558120  400          574 / 10586800      41 /  756200    0.0000542185`

 Posted by Charlie on 2013-02-28 12:46:10

 Search: Search body:
Forums (0)