I enjoy the card game Set, and have come up with a few variants based on the concept of assigning card "values" to stacks of cards (that is, each stack of cards is considered equivalent to a particular card) as follows:

  • A stack containing a single card is equivalent to that card
  • A stack containing multiple cards is equivalent to the third member of the set containing the top card and the card-equivalent of the rest of the stack (unless the rest of the stack is equivalent to the top card, in which case the whole stack is equivalent to the top card). This works because there is exactly one set containing any given pair of cards.

While there are a couple of variants, the basic idea is as follows: the top two cards of the deck are played into a stack, and players attempt to add cards to the stack so as to make the entire stack equivalent to the bottom card of the stack.

For example (I represent cards as $4$-tuples of $\{a,b,c\}$ signifying three options for four properties):

If the starting stack (from the bottom up) is $(a,b,c,c,),\;(a,a,a,a)$ (equivalent to card $(a,c,b,b)$) one possible winning play would be

  1. $(b,a,a,b)$ (making the stack equivalent to $(c,b,c,a)$)
  2. $(b,b,c,c)$ (making it equivalent to $(a,b,c,b)$)
  3. $(a,b,c,a)$ (making it equivalent to $(a,b,c,c)$)

My question is this: given a version of this game where cards have $n$ properties (for a standard Set deck $n=4$) and the deck contains exactly one copy of each possible card, how many cards do you have to draw to guarantee that your hand contains at least one solution for any starting stack of $2$ cards. It's at least $3^{n-1}+1$ since if your starting stack was $(a,\dots),\;(b,\dots)$, you could draw all $3^{n-1}$ cards with $(c,\dots)$ and still have no solution, but drawing any additional card is then guaranteed to produce a solution. This feels like the worst case to my intuition, but I'm not sure how to show that, or even if it's correct.

Note: I've asked related questions before here and here, though there I tried to be more abstract, treating the cards as elements of a magma.

  • $\begingroup$ Have you solved the problem for $n = 2, 3$? Think about fewer options too. $\endgroup$ – Ethan Bolker Nov 15 '16 at 21:42
  • $\begingroup$ @Ethan Bolker No. I haven't, or at least not rigorously. As I said, I suspect the answer is $3^{n-1}+1$, in which case for $2$ and $3$ it would be $4$ and $10$ respectively, but I haven't exhaustively shown that to be the case for all possible starting stacks and hands of those sizes. I could probably do it for $n=2$ (in fact, I'm about to attempt just that), but even with $n=3$ there are way too many possibilities ($84987760$ up to permutation of category values) to enumerate by hand. Even for $n=2$ there are $280$ possibilities, so I'm gonna have to be a bit clever even there. $\endgroup$ – Gabriel Burns Nov 15 '16 at 21:56
  • $\begingroup$ @EthanBolker Ok I guess I overcounted some there, but there are still a lot of possibilities. $\endgroup$ – Gabriel Burns Nov 15 '16 at 22:23

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.