4
$\begingroup$

We play the following card game:

We are given a deck with $M$ cards in different colors $c\in\left\{ 1,\dots,C\right\}$. There are $D$ cards from each color, so $M=CD$.

We wish to place a subset of $N$ cards from the deck on a board with “card locations” $n\in\left\{ 1,\dots,N\right\}$. Each location is painted with a set of colors $P_n \subset \{1,\dots,C\}$. Assume that any color can be painted on at most $D-1$ locations.

In each location we must place:

1) A card with a color $c$, for each the color $c \in P_n$.

2) An additional card with a color $c \notin P_n $.

The question is: When does a solution exist?

It is easy to show the following necessary conditions for the existence of a solution:

(1) $\forall n:\,|P_{n}|<C$

(2) $M \geq\sum_{n=1}^{N}|P_{n}|+N$.

Find sufficient and necessary conditions, or as strong a possible sufficient conditions.

Any help would be appreciated, thanks in advance!

$\endgroup$
  • 7
    $\begingroup$ Not sure what other conditions are sufficient, but these two aren't. Consider a board with three spaces: one where azure is prohibited, one where burgundy is prohibited, and one where chartreuse is prohibited. According to (1) and (2) we only need a six card deck: {A1, A2, B1, B2, C1, C2}. You'll have to put two cards of the same number on the board, and there's only one space where you can put either of those cards. $\endgroup$ – Jonah Ostroff Jun 22 '16 at 4:53
  • 1
    $\begingroup$ Thank you for this nice counter example. From this example, I understand now that the original question might be too hard. I'll now edit it, in an attempt to make it easier. $\endgroup$ – Daniel Soudry Jun 23 '16 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.