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!

Improve this question
$\endgroup$
2
  • 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, 2016 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, 2016 at 2:42

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.