1
$\begingroup$

Disclaimer: Sorry in advance if I make stupid mathematic assumptions or no-sense questions

I have a list of 25 numbers (from 1 to 25) and I need to generate 36 different groups/combinations of 4 numbers using exactly 6 times each number.

By my tests so far, only 24 differents combinations are possible, since 24 time you have to repeat at least 2 numbers (if I'm not wrong), so the goal, if this assumption is correct, is to place (repeat) numbers is the same group as less as possible.

I have an algorithm written in JS but I just only been able to generate the groups with some numbers not used 6 times and with more repetitions than desired.

Whith the described conditions, which I repeat:

  • 30 Different groups of 4 numbers and 5 differents groups of 5 numbers
  • No repetitions (or the less possibles): Whenever possible, same numbers MUST no coincide in the same group more than once,
    • e.g: if a group is (1,2,3,4), any of these numbers can coincide in other group again.
  • Related to previous point, when mathematically is not possible (as we have to generate 36 groups), the next aproach is that any number can coincide with only another number (max) that have already coincide.
    • e.g: if a group is (1,2,3,4), another group could be (1,2,X,X), (1,3,X,X), (1,4,X,X), (2,3,X,X), (2,4,X,X), (3,4,X,X), but not, for instance, (1,2,3,X)
  • If we face again into a mathematical limit, the next approach will be 3 repetitions in a group...etc.
  • Use each number 6 times (this is a MUST, no more, no less)

Which would be the better approach taking into account that conditions?

$\endgroup$
7
  • $\begingroup$ If each of the 25 numbers is used exactly 6 times, then you have 25*6=150 number instances. But if you only form 36 groups of 4 numbers, then that sounds like 36*4=144 number instances. These conditions seem incompatible. If you had 24 numbers instead of 25, then 24*6=144=36*4, but it sounds like that's not the case. $\endgroup$
    – Mark S.
    Oct 22, 2019 at 22:08
  • 1
    $\begingroup$ what about generating 30 groups of 4 numbers and 6 of 5? that way I think it would be possible. Anyway, I don't know how to achieve it $\endgroup$ Oct 23, 2019 at 6:39
  • $\begingroup$ Can you add more explanations about "No repetitions"? Is $(1,1,2,3)$ allowed? Are $(1,2,3,4)$ and $(1,2,6,7)$ allowed? Are $(5,6,7,8)$ and $(5,6,7,9)$ allowed? $\endgroup$
    – mathlove
    Oct 24, 2019 at 11:49
  • $\begingroup$ @mathlove explanation improved! thank you! $\endgroup$ Oct 24, 2019 at 14:16
  • $\begingroup$ I'm not sure if this is the best we can achieve, but I've just got an example such that (1) 30 different groups of 4 numbers and 6 differents groups of 5 numbers (2) no "3 repetitions" (3) 9 "2 repetitions" (4) use each number 6 times. $\endgroup$
    – mathlove
    Oct 26, 2019 at 12:14

2 Answers 2

2
+100
$\begingroup$

No repeated pairs or trios:

{1,2,6,17,21}
{1,4,7,14,19}
{1,5,8,16}
{1,9,13,24}
{1,10,23,25}
{1,12,15,22}
{2,3,19,23,24}
{2,4,10,15}
{2,5,11,13}
{2,7,22,25}
{2,8,14,18}
{3,4,18,20}
{3,5,7,10}
{3,6,15,25}
{3,9,12,16,21}
{3,13,14,17}
{4,5,9,25}
{4,6,8,13,22}
{4,11,17,24}
{5,12,14,24}
{5,15,17,19}
{6,7,16,24}
{6,9,11,14}
{6,10,12,19,20}
{7,11,12,18}
{7,13,20,23}
{8,9,15,20}
{8,10,11,21}
{8,12,17,23}
{9,18,22,23}
{10,13,16,18}
{11,16,19,22}
{14,15,21,23}
{16,17,20,25}
{18,19,21,25}
{20,21,22,24}

I used integer linear programming with a binary variable for each possible group of 4 or 5 numbers.

$\endgroup$
1
  • $\begingroup$ 6 and 19 are in groups with 21 other numbers. 5,11,15,18,25 are in groups with only 18 other numbers. Here is the adjacency matrix: i.stack.imgur.com/RSJ6y.png $\endgroup$
    – Mark S.
    Oct 28, 2019 at 11:46
0
$\begingroup$

Edit: This is certainly not best possible, but I believe I have arguably beaten the near-solution mathlove mentioned in a comment. I have 6 groups of 5 numbers, and 30 groups of 4 numbers, and there are no repeated trios, and only 6 instances of repeated pairs, while still using each number exactly 6 times.


The method I used is extremely ugly and ad-hoc, but I'll try to summarize it. Firstly, since there are 25 numbers, in all of my work I used the letters from "a" through "y", in order to see things by eye more easily.

I started with the groups of five, and figured it would be the best for the first 5 of them to be "abcde,fghij,klmno,pqrst,uvwxy". Then I figured I would start going across these to get a base going, so I entered these manually: "afkpu,ubgl,qvch,mrwd,insx,ejot". I think I also entered "yagm" to have "agm" go diagonally and include a second "y".

Then for a little while I asked a computer program to give me counts so I could use letters that have been used the least, and to make sure I didn't have any repeated pairs. This worked well for four or five more words past "yagm", building "bfnq,cikr,dhlp,esvf,djxq,owbh" this way (checking with the computer all along), but I had trouble with "djxq". I think the first convenient letter after d didn't seem to work at all.

Around this point, I switched to going not by the count of the letter in the words, but by the least-connected letters (making a graph and asking the computer for the lowest degree letters). That worked very easily for the next 11 groups of four (a total of 23 groups of four and 6 groups of five).

With tedious trial and error, I got 3 more groups that worked, but then found out that even though b/2 had low degree, no group of four would avoid a repeated pair. Somewhat arbitrarily, I chose to put b/2 together with a/1 and discovered that "abtx" only had one repeated pair. Moving forward, allowing myself another repeated pair, I found "dgsy" worked with repeated pair "gy".

At this point, there were only two groups of four left for the eight letters/numbers that had only been used 5 times. There were only 35 possibilities modulo swapping the two groups, so I asked the computer to try them all and tell me how many repeated pairs (or worse) I had. The best only had 4 more repeated pairs, for a total of six.

Since I started arbitrarily and did a lot by hand, I wouldn't be surprised if there were a better solution. Edit: A perfect solution exists, see this answer by Rob Pratt.


My repeated pairs are: (1,2),(7,25),(11,12),(6,11),(11,17),(6,17). But (6,11,17) is not a repeated trio.

(1, 2, 3, 4, 5)

(6, 7, 8, 9, 10)

(11, 12, 13, 14, 15)

(16, 17, 18, 19, 20)

(21, 22, 23, 24, 25)

(1, 6, 11, 16, 21)

(2, 7, 12, 21)

(3, 8, 17, 22)

(4, 13, 18, 23)

(9, 14, 19, 24)

(5, 10, 15, 20)

(1, 7, 13, 25)

(2, 6, 14, 17)

(3, 9, 11, 18)

(4, 8, 12, 16)

(5, 6, 19, 22)

(4, 10, 17, 24)

(2, 8, 15, 23)

(3, 12, 20, 25)

(5, 7, 14, 18)

(9, 13, 20, 22)

(1, 10, 19, 23)

(3, 15, 16, 24)

(2, 10, 11, 25)

(4, 9, 15, 21)

(5, 8, 13, 24)

(7, 11, 17, 23)

(1, 12, 18, 22)

(8, 14, 20, 21)

(3, 13, 19, 21)

(6, 15, 18, 25)

(5, 9, 16, 23)

(1, 2, 20, 24)

(4, 7, 19, 25)

(6, 11, 12, 17)

(10, 14, 16, 22)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .