Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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: mathematics
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments