How to Distribute Least Number of D Card Decks Amongst n People – Combinatorial Optimization

co.combinatoricscombinatorial-optimization

Decks are composed of 1 copy of each of $D$ unique cards. The set of cards is $C$ ($|C|=D$), the set of people is $P$ ($|P|=n\geq k$).

Starting with a simpler case (dropping the $k-1$ restriction)

One answer is to give $n-k+1$ full decks to $n-k+1$ people. Then applying pigeonhole principle, any $k$ people will definitely have a full deck. This takes $n-k+1$ decks and $D\times (n-k+1)$ cards. $\blacksquare$

We can show this is minimum. Suppose there are $\leq n-k$ of some card $c\in C$ and hence $\geq n-(n-k)=k$ people who don't have $c$. So, those $k$ people cannot assemble a full deck. Hence, at least $n-k+1$ of each card is required and hence $n-k+1$ full decks. $\blacksquare$

Main Problem

Even adding in the restriction that any $k-1$ people cannot together have a full deck, the previous minimum still holds. i.e. we still need $\geq n-k+1$ full decks.

Possible general solution.

There are $\left(\frac{n}{k-1}\right)$ groups of $k-1$ people. This strategy cannot work with $D<\left(\frac{n}{k-1}\right)$.

Partition the set of cards $C$ into $\left(\frac{n}{k-1}\right)$ sets. For extra "niceness" we can easily ensure these parts will have size $\in \left \{ \left \lceil\dfrac{D}{\left(\frac{n}{k-1}\right)}\right \rceil, \left \lfloor\dfrac{D}{\left(\frac{n}{k-1}\right)}\right \rfloor \right \}$

For every group $G_i$ of $k-1$ people, assign a unique part $C_i$ to this group, and take away the cards from $C_i$ from each member of $G_i$.

For groups $G_i$ and $G_j$, $i\neq j$:

By construction $G_i \setminus G_j \neq \emptyset \implies \exists g\in G_i, g\notin G_j$. So $g$ has all the cards of $C_j$.

So members of $G_i$ are together only missing the cards of $C_i$.

By construction $\forall g\notin G_i\implies g$ has cards of $C_i$. $\blacksquare$

Number of cards used

Number of cards is optimal if $D>\left(\frac{n}{k-1}\right)$ as it achieves the previously computed lower bound. $\blacksquare$

Questions

Im assuming (perhaps prematurely) that my solution is correct.

Can we prove that there is no solution for the case $D<\left(\frac{n}{k-1}\right)$?

Best Answer

For each $G\subseteq P$ define $C_G\equiv\{$Cards not held by any member of G$\}$.

Notice $\forall G,H\subseteq P, C_{G\cup H}=C_G\cap C_H$

Let $K\equiv\{G\subseteq P : |G|=k-1\}$. Notice $|K|=\left (\frac{n}{k-1}\right )$ [By definition of $\left (\frac{n}{r}\right )$]

Claim

$\forall G\in K, C_G\neq \emptyset$

Proof

$|G|=k-1$. But $C_G=\emptyset\implies G$ has a full deck. $\blacksquare$

Claim

$\forall G,H\in K, G\neq H \implies C_G \cap C_H = \emptyset$.

Proof

Let $\exists G,H\in K, G\neq H, C_G \cap C_H \neq \emptyset$

Consider $h\in H$.

By construction, $C_{\{h\}}\supseteq C_H \supseteq C_G \cap C_H \neq \emptyset$.

$\therefore C_{G\cup\{h\}}=C_G\cap C_{\{h\}} \supseteq C_G \cap C_G \cap C_{\{h\}}\neq \emptyset$.

$\implies C_{G\cup\{h\}} \supset \emptyset \implies C_{G\cup\{h\}} \neq \emptyset$

$|G\cup\{h\}|=k$. $G\cup\{h\}$ does not have a full deck.$\blacksquare$

Putting it together

Maximum size partition of $C$ is $|C|=D$.

Notice the set $R\equiv\{C_G : G\in K\}$ forms a partition of $D$. [See 2 above claims]

$|R|=|K| \implies |K|=\left (\frac{n}{k-1}\right )\leq D$ [Pigeonhole principle rears its head once more!] $\blacksquare$

Related Question