# Covering combinations

This feels like it ought to be a basic combinatorial question, but I just can't wrap my head around it tonight:

Let C(n,k) be the set of all k-element combinations from a set of n elements.

S \subset C(n,l) is a "covering" set if for every c in C(n,k), there exists some s from S such that s \subset c. That is, every combination in C(n,k) is an extension of the elements in S.

What is the minimum size of S in terms of n, k, and l?

In particular I'm interested in n=52, k=17 or k=13. Given a 13- or 17-card hand, what is the minimum number of small hands such that any larger hand can be discarded down to a small hand? ETA: for each specific small hand size, say l=5 or l=3.

For l=1 the answer is |S| = n-k+1. There are only k-1 missing elements, so every k-combination must pick at least one element of S.

For l>=2, I'm not sure what the general answer is.

Suppose we marked 15 cards from the 52-card deck. Then any 17-card hand must include at least two unmarked cards. This suggests that we could get by with (52-15)C2 = 666 elements of S to cover C(52,17); that is, all the pairs of unmarked cards. But is this the best we can do?
Tags:
• Post a new comment

#### Error

default userpic