|
To explore the number of ways of choosing r numbers out of n, with no consecutive numbers chosen, the following recursive method was used, based on the fact that after the first one is chosen as a given position, p, there remain n-p-1 available positions for the remaining r-1 to be chosen:
FUNCTION ways (n, r)
IF r = 0 THEN ways = 1: EXIT FUNCTION
t = 0
FOR posn = 1 TO n - 2 * r + 2
IF n = n - 2 * r + 2 THEN
t = t + 1
ELSE
t = t + ways(n - posn - 1, r - 1)
END IF
NEXT
ways = t
END FUNCTION
It resulted in the following table:
N \ R 0 1 2 3 4 5 6 7
0 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
2 1 2 0 0 0 0 0 0
3 1 3 1 0 0 0 0 0
4 1 4 3 0 0 0 0 0
5 1 5 6 1 0 0 0 0
6 1 6 10 4 0 0 0 0
7 1 7 15 10 1 0 0 0
8 1 8 21 20 5 0 0 0
9 1 9 28 35 15 1 0 0
10 1 10 36 56 35 6 0 0
11 1 11 45 84 70 21 1 0
12 1 12 55 120 126 56 7 0
13 1 13 66 165 210 126 28 1
14 1 14 78 220 330 252 84 8
15 1 15 91 286 495 462 210 36
16 1 16 105 364 715 792 462 120
17 1 17 120 455 1001 1287 924 330
18 1 18 136 560 1365 2002 1716 792
19 1 19 153 680 1820 3003 3003 1716
20 1 20 171 816 2380 4368 5005 3432
21 1 21 190 969 3060 6188 8008 6435
22 1 22 210 1140 3876 8568 12376 11440
23 1 23 231 1330 4845 11628 18564 19448
24 1 24 253 1540 5985 15504 27132 31824
25 1 25 276 1771 7315 20349 38760 50388
Note that a given entry equals the number directly above it plus the number two rows up and one column to the left, and in fact, Pascal's triangle is replicated, but with the rows of that triangle now slanted down to the right. Each entry is C(N-r+1,r).
And in fact we need go no farther in finding the answer to the puzzle. The only case where a given row of the table above (even extended to the right) shows one number of ways as 1.5 times another by adding 1 to r, is row 14, When there are 14 numbers on each ticket, having to select 3 of those numbers results in our player's having to buy 220 tickets, but when the number to be selected goes up to 4, he has to buy 330 in order to play every combination that doesn't use any consecutive numbers.
The following UBASIC program searches for solutions:
list
10 for N=0 to 2500
20 for R=0 to int(N/2+0.5)
26 HI=HR
27 HR=combi(N-R+1,R)
32 if HI*1.5=Hr then print "*";N;R-1;HI;R;HR
40 next
50 next
OK
It finds:
* 14 3 220 4 330
* 734 175 4090479779847205404318396321412955448120802454251513630317482872198910
80040106006731780975490735788442448594636272060552592744853522333334543909962304
176 6135719669770808106477594482119433172181203681377270445476224308298366
20060159010097671463236103682663672891954408090828889117280283500001815864943456
So if the ticket had 734 numbers and the player had to choose 175 before the change and 176 afterward, then this would also be a solution, but that's an unreasonable lottery, and an unimaginable number of tickets that player would have to buy, with 150 digits.
Based on Enigma No. 1485 by Susan Denham, New Scientist, 15 March 2008. |
