Fit Triples into Sixtuples in the best way?

[bernd]

TL;DR

How to put given set of triples (natural numbers) into as few sixtuple as possible?

Hi, I am not sure if this can be called directly a mathematical problem but it kind of is:
Say we have the list of all (ascendingly ordered) triple with natural numbers from 1-49 (is about lotto 6 out of 49):
T={(a,b,c) | a,b,c natural numbers, 1<=a,b,c<=49, a<b<c}

Now we are given a subset of this, lets call it M.
M is basically a rather long list of triples with thos specific properties.
Now I wonder how one can put those triples together neatly in as few sixtuples as possible?
Like for example (1,2,4) and (1,4,6) can be put together into a common tuple (1,2,4,6) of length 4.

speaking the other directly any sixtuple can contain up to 20(=6 over 3) triples.
so, yeah, I was wondering if there is some smart systematic way to "merge" triples from a given list so that the total amount of needed sixtuples is as little as possible?
(I know that you cant perfectly fill all sixtuples. once all triples are used up. jsut fill the non-full sixtuples with filler numbers)

doesnt matter if mathematical method or some smart programming way (java if possible) but could use any hint on how to do this smartly.

 

[Mark44]

Like for example (1,2,4) and (1,4,6) can be put together into a common tuple (1,2,4,6) of length 4.

But aren't you asking about merging triples into 6-tuples?

speaking the other directly any sixtuple can contain up to 20(=6 over 3) triples.

A 6-tuple contains 6 elements, not 20.

Having said that, I'm not sure what you're asking.

 

[bernd]

"A 6-tuple contains 6 elements, not 20."
Well, yeah.
What I meant:
in the sixtuple (1,2,3,4,5,6) the triples
(1,2,3)(1,2,4)(1,2,5)(1,2,6)(1,3,4)(1,3,5)(1,3,6)(1,4,5)(1,4,6)(1,5,6)
(2,3,4)(2,3,5)(2,3,6)(2,4,5)(2,4,6)(2,5,6)(3,4,5)(3,4,6)(3,5,6)(4,5,6)
so 20 triples is the maximum that can be fit in any sixtuple.

thats what I wanted to say there.
Yeah, my question is given a long list of triples, is there some smart way to put them together in a list of sixtuples with as little sixtuples needed as possible?

 

[Mark44]

What I meant:
in the sixtuple (1,2,3,4,5,6) the triples
(1,2,3)(1,2,4)(1,2,5)(1,2,6)(1,3,4)(1,3,5)(1,3,6)(1,4,5)(1,4,6)(1,5,6)
(2,3,4)(2,3,5)(2,3,6)(2,4,5)(2,4,6)(2,5,6)(3,4,5)(3,4,6)(3,5,6)(4,5,6)
so 20 triples is the maximum that can be fit in any sixtuple.

So your question is really "How many triples can be formed from a list of six numbers?"
The answer, which you already stated, is 20 -- $\binom {6}{3} = 20$, the number of combinations of six things taken 3 at a time. The notation $\binom {6}{3}$ is usually read as "6 choose 3."
However, you still can't fit 20 triples into a 6-tuple.

Yeah, my question is given a long list of triples, is there some smart way to put them together in a list of sixtuples with as little sixtuples needed as possible?

This is a completely different question, and one that I don't understand. Can you provide a concrete example of what you mean?

 

[Maarten Havinga]

Perhaps I got the gist of the question: given a set of triples, find the smallest set of sixtuples such that each triple is contained in at least 1 sixtuple.

Is that what you mean, Bernt?

 

[bernd]

exactly that! sorry if my explanations are just.. too bad to understand.
I cant even imagine any smart or systematic way to do this, except since brute forcing.
Anyone got any good idea?

 

[Maarten Havinga]

Do you know anything about the set of triples?

I regard your question as a graph theory question: you have a graph G that is a union of complete K3 graphs and you want to cover it with the smallest set of complete K6 graphs.

What I would like to know is for instance if we can assume that G is a planar graph, or has some other structure. Because in general, a bound or best solution to the general problem will not be satisfactory. Consider for instance the triples $\{x,x+1,x+y\}$ (mod $y^2 - y + 1$). You will for certain fixed $y$ have the same amount of triples as you have vertices, that's a small amount. Yet for $y > 4$ each sixtuple can contain at most 2 triples, giving a lower bound that the number of sixtuples is at least $y(y-1)/2 + 1$ which is more than half the number of vertices and also more than half the number of triples.

 

[bernd]

I should probably elaborate where the whole problem is even coming from:In Germany there is a lottery "6 of 49" where, as you might guess, 6 numbers are drawn from a pool of 49 numbers, building the lotto number of that session.
people can fill out forms and bet on 6 numbers.
and depending on how many of those numbers are equal with the numbers drawn on that lotto session, you win different prices.
there are prices for having gotten 3 numbers the same as the winning numbers, 4 right numbers,etc.

Now there are "systems" out there, aka long lists of of 6-number-tuples (sixtuples).
if you place a ton of bets on all those 6 number tuples lsited there, you are guaranteed that at least one of them will have 3 or more numbers right with the lottery numbers, therefor guaranteeing you to have a price of category "3 rights".

basically, I want to built such a list.
obviously , the less sixtuples that need to be bet on at once, the better.
since each one costs money.

So, for a start I built a list of all possible 6-number-tuples.
and a second lsit consisting of all possible 3-number-tuples.
now, as we had briefly mentioned, one such 6-number-tuple is initially containing 20 3-number-tuples.

with some database java magicery (which i am still fumbling with) I will try to cut down that list of 3-number-tuples as far as possible but in a way that still for each sixtuple in existence, at least one of the remaining 3-number-tuples is contained in it.
so anyways, this way I should effectively get a list of 3-number-tuples that, if all somehow bet at once; will guarantee a "3+ right numbers" win, no matter what the lottery actually happens to draw.

so yeah, here we get to the question here.
I now know (theoretically, cause I havent found the ultimate smallest list)
a list of all 3-number-tuples that I have to bet on at once in order to achieve the goal.

obviously though, bets consist of betting on 6-number-tuples.
so I need to take that lsit of tripels and condense them all into a list of sixtuples that is as small as possible.
So yeah, dont really have the list yet, but also highly doubt that it will satisfy any meaning condition that could be useful :-/