1.) For this question, we have 46 numbers (balls, cards, whatever): {1,2,3,4 .... 45,46}
=======================
2.) Each length-6-set of 46 numbers ( e.g. {1,2,3,4,5,6} or {1,13,16,17,32,46 } 'covers' 5+4+3+2+1 = 15 pairs:
E.g. {1,2,3,4,5,6} ==>
(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)
===============
3.) There are 1035 combinations with length 2 out of 46. ( 46 choose 2 = 1035).
4.) There must be one (or more?) combinations of 69 length-6-sets, that contain all possible 1035 pair combinations. Why 69 ? Well, if a length-6-set "covers" 15 pairs, then the number of length-6-sets that we need can be calculated by 1035 / 15 = 69.
Questions:
- Is this set of 69 length-6-sets known? (where?)
- Have people tried to solve this before? (what is this problem (or a similar problem) called? How do I find algorithms to solve this?)
- I know a brute force program can solve this, but it would run for a prohibitively long time -- is there an algorithm with a n / n*log n / n^2 ?
- Any other comments welcome :)
My hunch is that this is actually a pretty hard question and that this combination has not been found yet :) (Would also love to be shown a solution)
========================
(This is a lotto-related question. A relative of mine asked me this question and I'd like to give him an answer. I've thought about this for a while now but can't wrap my head around it.
It turns out the answer is no. For such a situation to exist, every pair of integers in $\{1,\dots,46\}$ would have to be a subset of exactly one of the $69$ $6$-subsets. But if any two of the $6$-subsets were disjoint, then an easy counting argument shows that there would exist two other subsets which intersect in at least two elements. Therefore each pair of $6$-subsets would have to intersect in exactly one element. This is the same as saying that the $69$ subsets form a $(46,6,1)$ block design, which is known not to exist.