In the card game "Projective Set": Compute the probability that $n$ cards contain a set

Question

In the game of Projective Set, it turns out that any seven cards contain a projective set. For fewer than 7 cards, how can we determine the probability that one or more sets exist (in terms of the number of cards)?

For those not familiar with Projective Set, here's a description from the wikipedia page linked above:

A Projective Set card has six binary attributes, or bits, generally represented by colored dots. For each color of dot, each card either has that dot or does not. There is one card for each possible combination of dots except the combination of no dots at all, making $2^6 - 1 = 63$ cards total.

Three cards are said to form a "set" if the total number of dots of each color is either 0 or 2. Similarly, four or more cards form a "set" if the number of dots of each color is an even number.

A card and itself could be said to form a two-card set, but as the cards in the deck are all distinct, this does not arise in actual gameplay.

Answer 1

The cards correspond to (nonzero) vectors in the $6$-dimensional vector space $V$ over the $2$-element field ${\Bbb F}_2$. Under this correspondence, a "set" is a collection of vectors whose sum is the zero vector. Since the dimension of the vector space is $6$, any set of $7$ vectors $v_1,\ldots, v_7$ must be linearly dependent, i.e. there exist constants $c_i\in{\Bbb F}_2$, not all zero, such that $$\sum_{i=1}^7 c_i v_i = 0 \textrm{ in }V.$$ But the $c_i$'s all either $0$ or $1$, so this means that some subset of the $v_i$'s must sum to the zero vector. Therefore, any $7$ cards contain a set.

To find the probability that $k$ vectors contain a set, we are asking for the probability that $k$ distinct nonzero vectors $v_1,\ldots,v_k$ are linearly dependent. It's easier to compute the number of ways they can be chosen to be linearly independent. There are $2^6-1$ possibilities for $v_1$; $v_2$ must not be in the subspace spanned by $v_1$, so there are $2^6-2$ possibilities for $v_2$. Similarly there are $2^6-4$ possibilities for $v_3$, and so on, with $2^6-2^{k-1}$ possibilities for $v_k$. Thus the probability that $\{v_1,\ldots, v_k\}$ are linearly independent (i.e. do not contain a set) is $$\frac{\prod_{i=0}^{k-1}(2^6-2^i)}{\prod_{i=1}^k(2^6-i)}.$$ Note that this probability becomes $0$ as soon as $k=7$, confirming that every $7$-tuple contains a set.

(The product in the denominator starts with $1$, rather than $0$, since this is Projective Set (rather than Affine Set), and we threw away the all-zero vector.)

Answer 2

As explained in this answer: The $63$ cards can be identified with the vectors in $\mathbb F_2^6 \setminus\{\mathbf 0\}$, and any collection $S$ of cards contains a set (in the sense of the game) if and only if it is linearly dependend in the $\mathbb F_2$-vector space $\mathbb F_2^6$.

So the question is: What is the probability that a random subset of $\mathbb F_2^6 \setminus\{\mathbf 0\}$ of size $n$ is linearly dependent? According to the (+1) answer of Tad, this probability is given by $$p(n) = 1 - \prod_{i=0}^{n-1}\frac{2^6 - 2^i}{2^6 - i - 1}\text{.}$$ Evaluating the expression for concrete values of $n$, we get the result $$ \begin{array}{ccc} n & \text{exact } p(n) & \text{approx. } p(n) \\ \hline \leq 2 & 0 & 0\% \\ 3 & \frac{1}{61} & 1.64\% \\ 4 & \frac{5}{61} & 8.20\% \\ 5 & \frac{911}{3599} & 25.31\% \\ 6 & \frac{61363}{104371} & 58.79\% \\ \geq 7 & 1 & 100\% \end{array} $$