Combination problem

Hybz

New member
Joined
Jan 20, 2013
Messages
14
Hi all,

I've recently started playing the lottery, and thought it would be an idea to play using a system which covers as many possible number combinations with as little amount of played games as possible. The lottery I play has 45 numbers in the field. Each game played requires the player to choose 6 numbers. I decided to play as many games as was required in order to cover all 2-number combinations.

I wrote down all 2-number combinations (1-2, 1-3, 1-4...... 43-44, 43-45, 44-45), and removed them from the list as they became part of any 6-number subset I had selected. This strategy ensures that when the first 2 numbers are drawn in the lottery, I am guaranteed to have them both within the same game (6-number subset).

With 45 numbers, the number of 2-number combinations is 990. The first 6-number subset chosen will have 15, unique 2-number combinations in it, but as subsequent subsets are selected, the number of unique combinations declines, as repetition (in my experience) becomes somewhat unavoidable.

I was wondering if there was any possible way to formulate an algorithm so that the minimum number of 6-number subsets was selected in order to ensure all 2-number combinations were included; or even to check what the minimum would be.

I played around with smaller fields/subsets to try and estalish if there was some kind of pattern I could observe, but I was unsuccessful.


Thanks in advance for any light you may be able to shed on this.
 
With 45 numbers, the number of 2-number combinations is 990. The first 6-number subset chosen will have 15, unique 2-number combinations in it, but as subsequent subsets are selected, the number of unique combinations declines, as repetition (in my experience) becomes somewhat unavoidable.

I was wondering if there was any possible way to formulate an algorithm so that the minimum number of 6-number subsets was selected in order to ensure all 2-number combinations were included; or even to check what the minimum would be.
The only way I can see to proceed is to write a computer program that follows the steps as you describe them, using a good random number generator, and run it a few thousand times and recording how many subsets are used each time. That should tell us the minimum. Might find the time to do that...
 
The only way I can see to proceed is to write a computer program that follows the steps as you describe them, using a good random number generator, and run it a few thousand times and recording how many subsets are used each time. That should tell us the minimum. Might find the time to do that...

Yeah, I thought maybe a MATLAB script might work, albeit it's been a few years since I've used MATLAB.
I hadn't considered doing the random option with a large number of iterations.
I guess that would produce a quantity for the minimum number of subsets required per case. I am kind of interested though, in whether or not any definitive relationship would exist whereby an exact number could be found using formulae.
I thought maybe a relationship may already have been discovered that I had not been aware of.
 
Assuming a 4:16 Lotto (120 pairs)...

Buy these 4:
1 2 3 4 : 5 6 7 8 : 9 10 11 12 : 13 14 15 16 ; 6 * 4 = 24 pairs
Then these 4 (using 1 number from each of above):
1 5 9 13 : 2 6 10 14 : 3 7 11 15 : 4 8 12 16 ; 24 more!

S'that what you mean?

The problem is not concerned with mean.

I am not sure that I completely understand what you're asking.


Basically, assuming a 3:6 lottery (for simplicity in explanation)...

Combinations:
1, 2; 1, 3; 1, 4; 1, 5;
1, 6; 2, 3; 2, 4; 2, 5;
2, 6; 3, 4; 3, 5; 3, 6;
4, 5; 4, 6; 5, 6;

Subsets:
1: 1,2,3. Includes 3 unique combinations.
2: 3,4,5. Includes 3 unique combinations.
3: 1,5,6. Includes 3 unique combinations.
4: 1,2,4. Includes 2 unique, 1 repeated (1, 2) combination.
5: 2,5,6. Includes 2 unique, 1 repeated (5, 6) combination.
6: 3,4,6. Includes 2 unique, 1 repeated (3, 4) combination.

So here, I've included all combinations using 6 subsets. With such a small field size (6), and subset size (3), I think it can be assumed that 6 is the minimum number of subsets required to accomplish this. However, is there a method that is not an assumption, and that can be used to verify minimum subsets where the numbers (field size and subset size) are significantly larger.
 
The only way I can see to proceed is to write a computer program that follows the steps as you describe them, using a good random number generator, and run it a few thousand times and recording how many subsets are used each time. That should tell us the minimum. Might find the time to do that...
Ran 100,000 cases.
Minimum number of tickets = 191
Maximum number of tickets = 288
Mean = 214.17
Standard deviation = 5.88

You could check this code to see if it does what I think you want to do. This is the subprogram that generates one set of tickets. I will run again and record the distribution (pdf) for NTICKETS.
Code:
      INTEGER*4 FUNCTION NTICKETS(TICKETS, NMAX)
C
C     Find a set of six-number tickets (values from 1-45) which includes
C       all possible pairs of values; return the number of tickets in the set.
C       If NTICKETS > NMAX, not all pairs were found.
C
      INTEGER*4 NMAX, TICKETS(6,NMAX), IMAX, PMAX
      PARAMETER (IMAX=45, PMAX=990)
C
      INTEGER*4 ISEED, VALUES(8), I, J, K, L, NPAIRS, TICKET(6)
      LOGICAL LPAIRS(IMAX,IMAX), LNEW
      DATA ISEED/0/
      SAVE ISEED
C
C     First time, randomize ISEED by clock
      IF (ISEED .EQ. 0) THEN
C        Use 0 as a flag to randomize the starting ISEED
         CALL DATE_AND_TIME(VALUES=VALUES)
         ISEED = VALUES(8)/2 + 500*(VALUES(6) + 60*(VALUES(7) +         &
     &           60*(VALUES(5) + 24*VALUES(3)))) + 12345678
         IF (IAND(VALUES(2),1) .EQ. 1) ISEED = -ISEED
      END IF
C
C     Starting new case; initialize all pairs to .FALSE.
      DO I=1,IMAX
         DO J=1,IMAX
            LPAIRS(I,J) = .FALSE.
         END DO
      END DO
      NTICKETS = 0
      NPAIRS = 0
C
      DO WHILE (NPAIRS.LT.PMAX .AND. NTICKETS.LT.NMAX)
C        Don't have all pairs yet, create another ticket
         TICKET(1) = INT(FLOAT(IMAX)*RAN(ISEED)) + 1
         DO I=2,6
C           All numbers in the ticket must be unique
20          CONTINUE
            K = INT(FLOAT(IMAX)*RAN(ISEED)) + 1
            DO J=1,I-1
               IF (K.EQ.TICKET(J) .OR. K.GT.45) GO TO 20
            END DO
            TICKET(I) = K
         END DO
C        Mark all new pairs that occur on this ticket, if any
         LNEW = .FALSE.
         DO I=1,5
            K = TICKET(I)
            DO J=I+1,6
               L = TICKET(J)
               IF (.NOT. LPAIRS(K,L)) THEN
                  LPAIRS(K,L) = .TRUE.
                  LPAIRS(L,K) = .TRUE.
                  NPAIRS = NPAIRS + 1
                  LNEW = .TRUE.
               END IF
            END DO
         END DO
         IF (LNEW) THEN
C           This ticket has at least 1 new pair, so we will keep it
            NTICKETS = NTICKETS + 1
            DO I=1,6
               TICKETS(I,NTICKETS) = TICKET(I)
            END DO
         END IF
      END DO
C
      IF (NPAIRS .LT. PMAX) NTICKETS = NMAX + 1
      RETURN
      END
 
Ran 100,000 cases.
Minimum number of tickets = 191
Maximum number of tickets = 288
Mean = 214.17
Standard deviation = 5.88

You could check this code to see if it does what I think you want to do. This is the subprogram that generates one set of tickets. I will run again and record the distribution (pdf) for NTICKETS.

I think there may be an error somewhere, albeit it's hard for me to check because I am unfamiliar with this language syntax.

I was able to manually achieve a minimum of 94, so it seems odd that out of 100,000 cases, 191 was the minimum achieved.

Now that I think about it, though, it may be unlikely that the minimum would ever be achieved if random numbers are selected. Perhaps the program needs to reject all games where a specific number of unique combinations are not included, at least initially, until it progresses and then becomes more lenient to accepting repetitions.
 
"mean" is simply highlighted by system...in case it's related to math;
I was asking: is that what you are saying? OK?


Hmmmm....well, make it larger: a 3:9 lottery; 9 pick 3 = 84;

buying only these 12 combos covers EXACTLY all the 36 pairs:
123, 147, 159, 168, 249, 258, 267, 348, 357, 369, 456, 789

...no duplicates whatsoever! Agree?

Correct. That's what I am trying to achieve.

Do you know if there is an "algorithm" or direct set of steps to follow that ensures this occurs, and for much larger sets?
Duplcates are not a problem, so long as they don't contribute to requiring extra subsets, as I believe no duplication would probably only be possible for when the subset size is wholly divisible into the field size.
 
I think there may be an error somewhere, albeit it's hard for me to check because I am unfamiliar with this language syntax.

I was able to manually achieve a minimum of 94, so it seems odd that out of 100,000 cases, 191 was the minimum achieved.

Now that I think about it, though, it may be unlikely that the minimum would ever be achieved if random numbers are selected. Perhaps the program needs to reject all games where a specific number of unique combinations are not included, at least initially, until it progresses and then becomes more lenient to accepting repetitions.
I tried that - first only accepting tickets with 15 new pairs. Any time I tried 30 in a row without finding a ticket with the current criterion, I dropped the test by 1. That didn't help a lot.

Hunting for a deterministic algorithm - best I have done is 125 tickets.

I started by counting through all 45 numbers sequentially, then by taking every 7th number (modulo 45), then every 17th, then every 13th. By the end of those four rounds I have 30 tickets and a total of 421 unique pairs. The way I chose the increments on each round was to be relatively prime to 45 and to each other. That method runs out of steam for a 5th round (I tried increment = 23 and/or 19). So then I switched to selecting K as a value with minimum number of associated pairs remaining, and then looking up (K,L) pairs that had not yet been found. That guarantees five new pairs on a ticket - but unfortunately very seldom produced more than 5 new pairs. Now I wonder if a stochastic (random number) method could be used on the remaining pairs.

What procedure led you to 94?
 
I tried that - first only accepting tickets with 15 new pairs. Any time I tried 30 in a row without finding a ticket with the current criterion, I dropped the test by 1. That didn't help a lot.

Hunting for a deterministic algorithm - best I have done is 125 tickets.

I started by counting through all 45 numbers sequentially, then by taking every 7th number (modulo 45), then every 17th, then every 13th. By the end of those four rounds I have 30 tickets and a total of 421 unique pairs. The way I chose the increments on each round was to be relatively prime to 45 and to each other. That method runs out of steam for a 5th round (I tried increment = 23 and/or 19). So then I switched to selecting K as a value with minimum number of associated pairs remaining, and then looking up (K,L) pairs that had not yet been found. That guarantees five new pairs on a ticket - but unfortunately very seldom produced more than 5 new pairs. Now I wonder if a stochastic (random number) method could be used on the remaining pairs.

What procedure led you to 94?


The procedure I used was fairly random. I manually wrote them down, and then selected 6 numbers crossing off each combination covered as I did so. Each time I would choose 6 numbers, I would just look at what pairs I had left and choose 6 numbers based on what I could see would give me the most amount of combinations. It wasn't a very scientific method, but I didn't know how else it could be approached.
 
Phil, methinks you're way "over" (191) because of this:
"This ticket has at least 1 new pair, so we will keep it"

Say ticket is 2 3 4 5 6 7 and 3 5 is a "new pair": it is kept.
But if later you hit 3 5 9 10 11 12 and 9 11 is a "new pair",
then you'll keep this one...but the other one can be removed,
which I don't think is being done...
Indeed I did start that way, but I put in a more restrictive test after Hybz suggested it. I started by requiring a set to generate 15 new pairs (the maximum possible), and counted rejects. Any time I had 30 rejected in a row, I dropped the criterion by 1 and continued.

Code:
         IF (NNEW .GE. NEWTEST) THEN
C           This ticket has enough new pairs to keep it
            NPAIRS = NPAIRS + NNEW
 . . .
            NTRY = 0
         ELSE
C           If we fail to meet NEWTEST in 30 tries, allow one less
            NTRY = NTRY + 1
            IF (NTRY .GE. 30) THEN 
               NEWTEST = MAX(NEWTEST-1, 1)
               NTRY = 0
            END IF
         END IF


That still didn't lower the lower limit anywhere close to 94! Here is the pdf I got that way:
pdf.jpg
I don't keep a record of which previous ticket a particular pair was in, so it would be difficult to go back and delete a set. Generally, earlier tickets have more new pairs than later ones. As I mentioned in my preceding post, I have a deterministic algorithm that gives me 421 pairs with the first 30 tickets - but I don't know where to go from there. Any suggestions?

Are we having fun with this?
 
Last edited:
As you say, main difficulty is "checking if current pair is missing".
I did that by setting up an array with all elements = 0,
then changing the corresponding element to 1;
like when I hit (as example) pair 4:8, then element(48) = 1.

Problem is array has to be size 89, to accomodate highest pair.
Therefore, need to use a size 89 array to accomodate only 36 pairs.

Not much of a problem with 89, but trying same approach with
6:45 would require an array size 4445 (highest pair being 44:45)
to accomodate only 990 pairs. Haven't found a way around that yet...
I think it is easier to use a 2D array, which is also less than half that size - but memory is cheap these days. When I find a new pair, I increment PAIRS(K,L) [and also (L,K)] - zero tells me not yet found.

Corresponding to your step 1, the first sets I use are
{1 2 3 4 5 6}, {7 6 9 10 11 12}, . . . {43 44 45 7 14 21}
where the 8th ticket has been filled out using increment 7 (mod 45). The next pass gives
{28 35 42 4 11 18}, . . . {10 17 24 31 38 45}
At that point I have 15 tickets and 225 pairs - perfect score so far.
Next I use increment 17, and finish off with increment 13:
{17 34 6 23 40 12}, . . . {11 28 45 13 26 39}
{7 20 33 1 14 27}, . . . {25 38 6 19 32 45}
Then I have generated 30 tickets with 421 unique pairs - not quite half.

Contemplation concerning "step 3".
a) choose a value K which has fewest pairs recorded
b) chose L such that (K,L) has not yet been found.
c) try to find M such that both (K,M) and (L,M) are "new"
else select different L and repeat
d) try to find N such that (K,N), (L,N) and (M,N) are all new
else select different M and repeat
e) fall into infinite loop and go have a rum & coke.

Concerning Fortran as a programming language.. For compute-bound applications, Fortran (arguably) produces the fastest execution times. It is faster than C because (by default) variables are passed by reference instead of by value. When running Monte Carlo simulations that take several hours, the difference may be significant [e.g., my Neutron Instrument Simulation Package, NISP, at PASeeger.com].
 
Last edited:
DrPhil said:
Are we having fun with this?

It is interesting to se the different approaches. I must admit, I wish I hadn't gone so rusty on my MATLAB so that I may be able to better assist. At first thought, I hadn't anticipated that this would have been as difficult as it is proving to be.
 
Not just that. If the lotto is not a "nice lotto!", like 3:9 or 6:48
and the likes (a:b , b divisible by a) then getting a complete set
with no duplicates "seems" impossible...like Hybz's 6:45.

Solution may be to perform work on a 6:48, then don't buy any
of the tickets containing a 46, 47 or 48!

After playing around with a few more values, it would seem that repetition is unavoidable only when a:b is such that b^-0.5 = a.
ie: To do 6:45, one may be better off approaching it as a 6:36, then somehow working in the other 9.
Assuming that 6:36 can be done without repetition, this would represent 630 pairs from 42 games.
Then by grouping the numbers into triples, A=[37 38 39], B=[40 41 42], C=[43 44 45], as well as grouping the remaining 1 - 36 into triples (named D to O), we can play two sets of triples per subset to get 9 unique pairs, and 6 repetitions, for the remaining games.

The 3 triples (A, B, and C) are matched up with each of the other 12 triples (C through to O) to give 36 more games.
The 3 triples (A, B, and C) are then matched with each other for an additional 3 games.

This means, that if Denis' theory is right about no repetitions possible for a 'nice lotto', then 6:45 can be achieved in 81 games.
 
85
But now I have to look at your latest algorithm... Looks like I got beat...

Code:
   N              TICKET             New  Sum
   1       1   2   3   4   5   6      15   15
   2       7   8   9  10  11  12      15   30
   3      13  14  15  16  17  18      15   45
   4      19  20  21  22  23  24      15   60
   5      25  26  27  28  29  30      15   75
   6      31  32  33  34  35  36      15   90
   7      37  38  39  40  41  42      15  105
   8      43  44  45   7  14  21      15  120
   9      28  35  42   4  11  18      15  135
  10      25  32  39   1   8  15      15  150
  11      22  29  36  43   5  12      15  165
  12      19  26  33  40   2   9      15  180
  13      16  23  30  37  44   6      15  195
  14      13  20  27  34  41   3      15  210
  15      10  17  24  31  38  45      15  225
  16      17  34   6  23  40  12      14  239
  17      29   1  18  35   7  24      14  253
  18      41  13  30   2  19  36      13  266
  19       8  25  42  14  31   3      14  280
  20      20  37   9  26  43  15      14  294
  21      32   4  21  38  10  27      14  308
  22      44  16  33   5  22  39      13  321
  23      11  28  45  13  26  39      13  334
  24       7  20  33   1  14  27      12  346
  25      40   8  21  34   2  15      12  358
  26      28  41   9  22  35   3      13  371
  27      16  29  42  10  23  36      13  384
  28       4  17  30  43  11  24      13  397
  29      37   5  18  31  44  12      12  409
  30      25  38   6  19  32  45      12  421
  31       5   7  13  23  25   4      14  435
  32      28   1  10  19  34  37      15  450
  33      38   1   9  13  44  29      14  464
  34       2   7  16  28  31  20      14  478
  35       8   4  16  19  12  26      13  491
  36      11   1  16  21  41  25      14  505
  37      32   2  11  14  22  37      15  520
  38      35   2  10  25  43  18      14  534
  39      40   1  22  30  31  45      14  548
  40       3   7  15  19  11  29      13  561
  41       6   7  22  26  42  17      14  575
  42      24   2  12  27  39  42      14  589
  43      36   1  17   3  21  26      12  601
  44      33   3  10  30  12  15      13  614
  45       5   8  17  20  35  27      14  628
  46      38   2  23   3  18  45      12  640
  47       6   8  13  24  33  28      14  654
  48      32   3  16  24  40  43      14  668
  49      41   4  14  29   6  31      13  681
  50       9   4  34  39  14  30      13  694
  51      36   4  15  44  20  40      13  707
  52       5   9  21  42  30  32      13  720
  53      38   5  11  34  26  14      12  732
  54      18   6   9  27  36  11      13  745
  55      45   4  33  37  29   8      12  757
  56      35   6  15  21  39  23      11  768
  57      41   5  10  15  24  26      11  779
  58      43   1  23   8  41  33      11  790
  59      18   8  22  30  38  20      11  801
  60      17   2  29  32  44  28      11  812
  61      44  19  27  31  43  39      11  823
  62      25   9  17  24  37  36      11  834
  63      35  12  13  14  40  10      11  845
  64      12  20  25  32  41  45      10  855
  65      35  16  38  45   9  15       9  864
  66      34  22  25  44  10  24       9  873
  67      28   5  40   7  36  38       9  882
  68      23   9  31  11  26  32       9  891
  69      18  21  33  11  40  25       8  899
  70      42  13  43  34  45   1       8  907
  71      39  10  20   6  29   3       8  915
  72      21  12  28   1  13  31       7  922
  73      27  15  22   4  13  37       7  929
  74      44  26  35   3  37   7       7  936
  75      14  23  28  15  19  42       7  943
  76      27  45  16   5  19  17       5  948
  77      36  45   8  14  24  39       5  953
  78       7  30  35  32  13  18       5  958
  79       7  34  16  18  29  39       6  964
  80       7  41  17  18  44   8       5  969
  81      11  20  42  44  12  38       5  974
  82      21  29  40  37  23  27       5  979
  83      28  43  38  31  33  42       4  983
  84      17  33  39  18  19  35       4  987
  85       6  43  15  31  18  26       3  990
 
Distribution of # of new pairs:
   15   17
   14   16
   13   14
   12    8
   11    8
   10    1
    9    4
    8    3
    7    4
    6    1
    5    6
    4    2
    3    1
    2    0
    1    0
 
    1 pairs repeated 5 times
    2 pairs repeated 4 times
   26 pairs repeated 3 times
  223 pairs repeated 2 times
  738 pairs not repeated
    0 missing pairs

 
Last edited:
85
But now I have to look at your latest algorithm... Looks like I got beat...

Code:
   N              TICKET             New  Sum
   1       1   2   3   4   5   6      15   15
   2       7   8   9  10  11  12      15   30
   3      13  14  15  16  17  18      15   45
   4      19  20  21  22  23  24      15   60
   5      25  26  27  28  29  30      15   75
   6      31  32  33  34  35  36      15   90
   7      37  38  39  40  41  42      15  105
   8      43  44  45   7  14  21      15  120
   9      28  35  42   4  11  18      15  135
  10      25  32  39   1   8  15      15  150
  11      22  29  36  43   5  12      15  165
  12      19  26  33  40   2   9      15  180
  13      16  23  30  37  44   6      15  195
  14      13  20  27  34  41   3      15  210
  15      10  17  24  31  38  45      15  225
  16      17  34   6  23  40  12      14  239
  17      29   1  18  35   7  24      14  253
  18      41  13  30   2  19  36      13  266
  19       8  25  42  14  31   3      14  280
  20      20  37   9  26  43  15      14  294
  21      32   4  21  38  10  27      14  308
  22      44  16  33   5  22  39      13  321
  23      11  28  45  13  26  39      13  334
  24       7  20  33   1  14  27      12  346
  25      40   8  21  34   2  15      12  358
  26      28  41   9  22  35   3      13  371
  27      16  29  42  10  23  36      13  384
  28       4  17  30  43  11  24      13  397
  29      37   5  18  31  44  12      12  409
  30      25  38   6  19  32  45      12  421
  31       5   7  13  23  25   4      14  435
  32      28   1  10  19  34  37      15  450
  33      38   1   9  13  44  29      14  464
  34       2   7  16  28  31  20      14  478
  35       8   4  16  19  12  26      13  491
  36      11   1  16  21  41  25      14  505
  37      32   2  11  14  22  37      15  520
  38      35   2  10  25  43  18      14  534
  39      40   1  22  30  31  45      14  548
  40       3   7  15  19  11  29      13  561
  41       6   7  22  26  42  17      14  575
  42      24   2  12  27  39  42      14  589
  43      36   1  17   3  21  26      12  601
  44      33   3  10  30  12  15      13  614
  45       5   8  17  20  35  27      14  628
  46      38   2  23   3  18  45      12  640
  47       6   8  13  24  33  28      14  654
  48      32   3  16  24  40  43      14  668
  49      41   4  14  29   6  31      13  681
  50       9   4  34  39  14  30      13  694
  51      36   4  15  44  20  40      13  707
  52       5   9  21  42  30  32      13  720
  53      38   5  11  34  26  14      12  732
  54      18   6   9  27  36  11      13  745
  55      45   4  33  37  29   8      12  757
  56      35   6  15  21  39  23      11  768
  57      41   5  10  15  24  26      11  779
  58      43   1  23   8  41  33      11  790
  59      18   8  22  30  38  20      11  801
  60      17   2  29  32  44  28      11  812
  61      44  19  27  31  43  39      11  823
  62      25   9  17  24  37  36      11  834
  63      35  12  13  14  40  10      11  845
  64      12  20  25  32  41  45      10  855
  65      35  16  38  45   9  15       9  864
  66      34  22  25  44  10  24       9  873
  67      28   5  40   7  36  38       9  882
  68      23   9  31  11  26  32       9  891
  69      18  21  33  11  40  25       8  899
  70      42  13  43  34  45   1       8  907
  71      39  10  20   6  29   3       8  915
  72      21  12  28   1  13  31       7  922
  73      27  15  22   4  13  37       7  929
  74      44  26  35   3  37   7       7  936
  75      14  23  28  15  19  42       7  943
  76      27  45  16   5  19  17       5  948
  77      36  45   8  14  24  39       5  953
  78       7  30  35  32  13  18       5  958
  79       7  34  16  18  29  39       6  964
  80       7  41  17  18  44   8       5  969
  81      11  20  42  44  12  38       5  974
  82      21  29  40  37  23  27       5  979
  83      28  43  38  31  33  42       4  983
  84      17  33  39  18  19  35       4  987
  85       6  43  15  31  18  26       3  990
 
Distribution of # of new pairs:
   15   17
   14   16
   13   14
   12    8
   11    8
   10    1
    9    4
    8    3
    7    4
    6    1
    5    6
    4    2
    3    1
    2    0
    1    0
 
    1 pairs repeated 5 times
    2 pairs repeated 4 times
   26 pairs repeated 3 times
  223 pairs repeated 2 times
  738 pairs not repeated
    0 missing pairs


You didn't get beat. After playing around with it some more, I think we may be wrong. Whilst 3:9 is possible to do without repetition, I don't think this applies for larger cases, even if the field size is the square of the subset size. I wasn't able to do 4:16 without repetitions. The best I could get was 72 pairs from 12 games. After that repetition seems unavoidable.

I think 85 may be the best we can get for 6:45!
 
...surprised?!

Not really surprised, but kind of interested in what the numerical criteria would be for no repetitions now, as there does not seem to be any clear relationship that I can find.

Were you able to do 4:16 without any repetitions? or 5:25?
 
The 4:16

Step 1:
1: 1 2 3 4
2: 5 6 7 8
3: 9 10 11 12
4: 13 14 15 16
Step 2:
5: 1 5 9 13
6: 2 6 10 14
7: 3 7 11 15
8: 4 8 12 16
Step 3:
loop a from 1 to 4
loop b from 5 to 8
loop c from 9 to 12
loop d from 13 to 16
retain [a,b,c,d] if ALL related 6 pairs haven't been taken
I tried the same procedure for 6:36, and got nowhere with it

Code:
   N              TICKET             New  Sum
   1       1   2   3   4   5   6      15   15
   2       7   8   9  10  11  12      15   30
   3      13  14  15  16  17  18      15   45
   4      19  20  21  22  23  24      15   60
   5      25  26  27  28  29  30      15   75
   6      31  32  33  34  35  36      15   90
   7       7  14  21  28  35   6      15  105
   8      13  20  27  34   5  12      15  120
   9      19  26  33   4  11  18      15  135
  10      25  32   3  10  17  24      15  150
  11      31   2   9  16  23  30      15  165
  12       1   8  15  22  29  36      15  180
  13       1   7  13  19  25  31      15  195
  14       1   9  14  20  26  32      15  210
  15       1  10  16  21  27  33      15  225
  16       1  11  17  23  28  34      15  240
  17       1  12  18  24  30  35      15  255
  18       2   7  15  24  26  34      15  270
  19       2   8  17  19  27  35      15  285
  20       2  10  18  20  28  36      15  300
  21       2  11  13  21  29  32      15  315
  22       2  12  14  22  25  33      15  330
Step 1 gave the first 6 tickets, step 2 the next 6, but all I got from step 3 was another 10 tickets
Step 3
loop a from 1 to 6
loop b from 7 to 12
loop c from 13 to 18
loop d from 19 to 24
loop e from 25 to 30
loop f from 31 to 36
retain [a,b,c,d,e,f] if ALL related 15 pairs haven't been taken

I broadened the limits to a(1,31), b(a+1,32), c(b+1,33), d(c+1,34), e(d+1,35), f(e+1,36) but it didn't make any difference at all!. Starting this way, I DID get down to
83 tickets
and twice as many "15s"
Code:
Distribution of # of new pairs:
   15   35
   14    9
   13    3
   12    4
   11    7
   10    6
    9    3
    8    3
    7    2
    6    2
    5    4
    4    4
    3    0
    2    1
    1    0
 
    2 pairs repeated 4 times
   22 pairs repeated 3 times
  205 pairs repeated 2 times
  761 pairs not repeated
    0 missing pairs
 
Step 2 (7 to 12) is not same as mine:
7: 1,7,13,19,25,31
....
12: 6,12,18,24,30,36
(in other words, the "columns" from N = 1 to 6)
Yes I did misunderstand that - but is there a particular advantage of 6 as the increment? I used 7.
On this:
2 pairs repeated 4 times
22 pairs repeated 3 times
205 pairs repeated 2 times
761 pairs not repeated
0 missing pairs
That's 990 pairs (45C2); shouldn't it be 630 (36C2) ?
the 990 is after completing 6:45, with 83 tickets.
On this:
I broadened the limits to a(1,31), b(a+1,32), c(b+1,33), d(c+1,34), e(d+1,35), f(e+1,36) but it didn't make any difference at all!.

It will NOT make any difference: like, 1 to 6 has already been entirely paired up in Step 1....
so a and b cannot both be < 7
I finally figured that out! Then I modified step 1 to that every sequential pair is included:
Code:
   N              TICKET             New  Sum
   1       1   2   3   4   5   6      15   15
   2       6   7   8   9  10  11      15   30
   3      11  12  13  14  15  16      15   45
   4      16  17  18  19  20  21      15   60
   5      21  22  23  24  25  26      15   75
   6      26  27  28  29  30  31      15   90
   7      31  32  33  34  35  36      15  105
   8      36  37  38  39  40  41      15  120
   9      41  42  43  44  45   1      15  135
Then the groups a,b,c,d,e,f can have arbitrary lengths, e.g. a=(1-8), b=(9-15),. . . f=(39-45). Nothing I have done has gotten me below 83 tickets.
 
83 is awfully close to what I theorised as the minimum of 81 (considering that no repetitions of a:b does now seem possible for b=a^2).

Looking at the options you guys have covered, I am not sure that there is really any better.

Athough I am starting to wonder if the same algorithms would apply with similar results for b<a^2, or b>2a^2.

To be honest, I am still trying to work out your methods of looping.
 
83 is awfully close to what I theorised as the minimum of 81 (considering that no repetitions of a:b does now seem possible for b=a^2).

Looking at the options you guys have covered, I am not sure that there is really any better.

Athough I am starting to wonder if the same algorithms would apply with similar results for b<a^2, or b>2a^2.

To be honest, I am still trying to work out your methods of looping.
82
My "algorithm" is brute force - totally independent of IMAX. I gave up on a looping "step 3" that was limited to 36×36, but instead looked at the whole 45×45 at once, using a scheme to try to find maximum number of new pairs for each ticket. I started by accepting 12 or more, then when those dried up accepted tickets with fewer new pairs.

After looping by 1's and by 7's to get the first 15 tickets with 15 pairs each, the procedure is:
Code:
1. Find a value M that has been used in fewest pairs so far.
2. Find a value I which has not yet been paired with M.
3. Look for J that has not been paired with M or with I: 
   if none found, try another I with same M
   if no more (M,I) pairs can be found, try a different M
4. For all K, count number of new pairs in set (M,I,J,K) and use K that is max
5. For all L, count number of new pairs in set (M,I,J,K,L) and use L that is max
6. for all N, count number of new pairs in set (M,I,J,K,L,N) and use N that is max
7. If number of new pairs [U]>[/U] current criterion, keep the ticket
   else try again from step 1.
8. If 10 in a row fail, decrease criterion by 1.
This method runs runs into trouble (that is, infinite loop) when the remaining number of pairs is less than 60 or so, so at that point I switch to finding pairs that haven't yet been used, and trying to find some with common values. About the last 10 tickets are found that way.

Every possible pair occurs in some ticket with 4 other "random" values. That makes the probability of having any specific set of 3 values P(3) = 4/43. Is that enough to skew the odds in your favor? Is there a payout for getting 3 hits?
 
Top