Finding 35 sets of size 6 in $A=\{1,\ldots,70\}$ s.t. for each choice of 6 numbers in $A$ there's always a set with intersection of size at least 2

Question

Look at $A=\{1,\ldots,70\}$. I want to find 35 sets, $s_{1},\ldots,s_{35}\subseteq A$, where $\forall i,\;\left|s_{i}\right|=6$, and for each choice of six numbers $\left\{ a_{1},\ldots,a_{6}\right\} \subseteq A$, there are $a_{i}\neq a_{j}$ s.t. $\exists k\in[35]$ s.t. $a_{i},a_{j}\in s_{k}$ (or equivalently $\exists k\in\left[35\right]:\;\left|\left\{ a_{1},\ldots,a_{6}\right\} \cap s_{k}\right|\geq2$.

This is like saying that you can always buying 35 lottery tickets, and having at least one of them have two numbers in common with the winning ticket.

I tried different combinations of sets, for example trying to place the number $1$ in half of the sets, and in half of those place $2$ and etc., but no matter what method I tried, I couldn't find such sets $s_{1},\ldots,s_{35}$.

In wikipedia I found a similar topic, stating that " In the 5-from-90 lotto, the minimum number of tickets that can guarantee a ticket with at least 2 matches is 100." however, the original paper did not provide an example of such sets.

If it turns out that it is impossible to find such sets that guarantee a 2-match, I would like to find sets that give us a 2-match in extremely high probability (99.99999%)

Answer 1

Let $[n]$ denote $\{1,\dots,n\}$.

The answer is yes, there does exist a successful collection of $35$ sets. Let me clarify my terminology:

A $(v,k,t,m)$-Lotto design is a collection, $\mathcal B$, of subsets of $[v]$, each with size $k$, such that for any subset $M\subseteq [v]$ such that $|M|=m$, there exists a subset $B\in \mathcal B$ such that $|M\cap B|\ge t$.
We let $L(v,k,t,m)$ be the size of the smallest lotto design.

You are searching for a Lotto design with parameters $(70,6,2,6)$. Since you want $35$ tickets, your design would prove that $L(70,6,2,6)\le 35$.

First, we demonstrate an "addition" operation on Lotto designs, which allows us to combine smaller designs into larger ones.

Lemma: Let $v,k,m,t$ be the Lotto design parameters. Let $n$ be a positive integer. For any numbers $v_1,\dots,v_n$ for which $v_1+\dots+v_n=v$, and $m_1,\dots,m_n$ for which $(m_1-1)+\dots+(m_n-1)=m-1$, we have $$L(v,k,t,m)\le \sum_{i=1}^n L(v_i,k,t,m_i)$$

Proof: The idea is to partition $[v]$ into sets $V_1,\dots,V_n$, such that $|V_i|=v_i$. For each of these sets, we choose a Lotto design $\mathcal B_i$, with parameters $(v_i,k,t,m_i)$. The union of these Lotto designs on the smaller sets is the lotto design on all of $[v]$.

To see that this works, note that for any subset $M\subseteq [v]$, the fact that $(m_1-1)+\dots+(m_n-1)=m-1$ implies that there exists $i$ for which $|M_i\cap V_i|\ge m_i$. If this were not true, we would have $|M_i\cap V_i|\le m_i-1$ for all $i$, which would mean $|M|=\sum_{i=1}^n |M\cap V_i|\le \sum_{i=1}^n (m_i-1)=m-1$, contradicting $|M|=m$. Since $|M\cap V_i|\ge m_i$ for some $i$, there will exist $B\in \mathcal B_i$ for which $|M\cap B|\ge t$, as required. $\square$

To apply this to your problem, we will choose $n=5$, $v_1=v_2=v_3=v_4=v_5=14$, and $m_1=\dots=m_5=2$. That is, we will divide $[70]$ into five equal sets with size $14$. For each of these sets, we will choose a $(14,6,2,2)$-lotto design. This is equivalent to asking for a covering design on the set $\{1,\dots,14\}$, by which I mean a collection of subsets, $\mathcal B$, each with size $6$, such that for every subset $M$ of size $2$, there is some $B\in \mathcal B$ where $M\subseteq B$.

We then consult the La Jolla covering repository to find the required covering design. Indeed, these $7$ subsets of $\{1,\dots,14\}$ with size $6$ will cover all pairs:

1  2  3  8  9 10
1  4  5  8 11 12
1  6  7  8 13 14
2  4  6  9 11 13
2  5  7  9 12 14
3  4  7 10 11 14
3  5  6 10 12 13

Now you just need to translate these sets to get similar covering designs for $\{15,\dots,28\}$, then for $\{29,\dots,42\}$, and so on. The union of these $7\cdot 5=35$ sets is your Lotto design.