how many cards must be drawn to guarantee one of n combinations is found

Question

I was working on creating a card game with a friend, and we wanted to understand how card draws would play out.

We have a set of 18 distinct cards. Each card participates four times in some pre-defined combination of three cards (order doesn't matter) for a total of 24 combinations. How many cards do we need to draw in our opening hand, to ensure that one of the combinations exists in our opening hand?

We thought this had to do with combinatorics, maybe related to this question, but we get stuck thinking about it, because each of our cards is distinct, so we don't actually have 24 identical cards to choose from, but rather 24 different sets of 3 cards out of 18 unique cards.

Answer 1

Presumably any possible two 3-card combinations of cards share at most $1$ card. So if you take an initial card, all the combinations involving that card would be another $4\cdot 2 = 8$ cards. So adding the initial card, that's half the pack - is there an "anti-card" to our initial choice for which all of its combinations complete the pack? In which case you could certainly hold $1+4+1+4=10$ cards without a combination & need at least $11$ cards to have a combination.

Coming from the other side, each card can only break $4$ combinations, so you'd need to omit $6$ cards to have any chance of breaking all combinations. That would imply that $13$ cards would always be enough, depending on how the combinations are organized. The requirement for $13$ cards can be firm if a lot of combinations have some common cards, for example with combinations:
$\{abm, abn, abo, abp, $ $cdq, cdr, cdm, cdn, $ $efo, efp, efq, efr, $ $ghm, ghn, gho, ghp, $ $ijq, ijr, ijm, ijn, $ $klo, klp, klq, klr \}$
you could have zero combinations unless at least one of $m,n,o,p,q,r$ are held.

Answer 2

The answer depends on what the particular $24$ combinations are. Here are two examples where the required number of cards in the deck are different. In order to answer your question, you would have to enumerate all possible ways to choose $24$ combinations, find the minimum number of cards which contains at least one combination for each, and take the maximum of these minima. I do not know how to do this.

• Suppose the cards are labeled $A_1,A_2,\dots,A_6$, $B_1,B_2,\dots,B_6$, and $C_1,C_2,\dots,C_6$. The following $8$ subsets contain each of the $A$ cards exactly four times: $$ \{A_1,A_2,A_3\},\{A_4,A_5,A_6\}\\\{A_1,A_2,A_4\},\{A_3,A_5,A_6\}\\\{A_1,A_2,A_5\},\{A_3,A_4,A_6\}\\\{A_1,A_2,A_6\},\{A_3,A_4,A_5\}\\\ $$ If you repeat that construction with $A$ replaced with $B$ and $C$, you get $24$ subsets total which contain all cards exactly four times. For this choice of subsets, you need $\boxed{10}$ cards to guarantee having one of the $24$ combinations. Indeed, if you have $10$ cards, then there must exist four cards which have the same letter (either all $A$, all $B$, or all $C$), and you can directly check that four of $A_1,A_2,\dots,A_6$ will contain one of the above subsets, while any three will not suffice (e.g. $\{A_1,A_3,A_4\}$).

• For the other example, we first construct $9$ cards and $12$ subsets of size $3$ which contain these cards four times each. The nine cards are the squares of a tic-tac-toe board, while the $12$ subsets consist of

  • The three rows.
  • The three columns.
  • The three downward sloping broken diagonals.
  • The three upward sloping broken diagonals.

  You can check that any five cards will contain one of these 12 subsets, but there exist subsets of size $4$ which do not, like the set of $4$ corners.

  Now, if you use two copies of this deck, you get a deck of $18$ cards and $24$ combinations of these cards containing each card four times. In order to guarantee getting one of these subsets in a set of cards, you need at least $\boxed 9$ cards in that set, while $8$ does not suffice.

As you see, the answer can be either $9$ or $10$. It is possible there are other answers.