0
$\begingroup$

It's my first question out here, so please don't judge me too strictly.
I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) painted on cards, while for every pair of cards there's one and only one common object. The game is for two players. At each step each player draws a card and puts it along the card of the other player. The player who is the first to pronounce the common object wins the step and takes both cards. The one who attains all cards first is the winner.

Specifically:
1. There're 50 cards
2. Each card contains 8 different objects
3. There's set of 36 possible different objects (from which 8 objects are chosen)
4. The set of cards has the following property: for each pair of cards there's one (and only one) common object

What I'm asking is how to build an algorithm that chooses the subset of objects to paint on cards.

To make it strict:
Input:{N, O, K},
N-number of cards
O-total number of objects
K-number of objects on a card

Output:
N lines of k numbers each: n_1, n_2, ..., n_N where
n_1= {k1_1, k1_2, ..., k1_K}
n_2= {k2_1, k2_2, ..., k2_K}
....
n_N= {kN_1, kN_2, ..., kN_K}
such that for any i,j<=N exists |n_i X n_j|=1, where X is intersection of sets

It's clear to me, that not for all triples {N,O,K} there's a solution.
No limitations on time/space complexity. All supporting data structures are allowed.
Thanks in advance

$\endgroup$
  • 4
    $\begingroup$ Welcome to CS.SE! What have you tried? What approaches have you considered? Also, I can't understand what "exists |n_i X n_j|=1" means. Can you edit the question to clarify? What variables are you saying there exist values for? $\endgroup$ – D.W. Jun 20 '16 at 21:13
1
$\begingroup$

The Ray-Chaudhuri–Wilson theorem states that the number of cards is at most the number of objects. See for example a paper of Noga Alon (in your case, $L = \{1\}$).

$\endgroup$
0
$\begingroup$

After a little digging I've found this twin question, which has a really great answer. Thanks for writing comments

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.