Consider a card game-parity

Question

Consider a card game where the deck consists of 63 distinct cards. The deck is created in the following manner: each card consists of some number of symbols, where no two symbols are the same. There are six different symbols. We have $\binom{6}{1}=6$ cards with 1 symbol each on them, we have $\binom{6}{2}=15$ cards with 2 symbols each on them, and so on until we reach the single $\binom{6}{6}=1$ card that has all six symbols.

A set consists of some number of card such that within the set, the number of times each symbol appears is even.

How can we prove that given any 7 cards within this deck, we can find at least one set?

Answer 1

Kk I think the following works. Let's call our 7 cards $c_1, \ldots c_7$. View the "symbols on the card $c_j$" as an element $v_j$ of $\mathbb{F}_2^{\oplus 6}$: namely, if our 6 possible symbols are $s_1, \ldots s_6$, let the $i^{th}$ coordinate $v_j$ be the number of times $s_i$ appears on the card.

For example, if $c_1$ reads: $s_1 s_3 s_5$, $v_1 = (1, 0, 1, 0, 1, 0)$.

Now take your 7 cards, and look at their corresponding vectors side by side, i.e. form the matrix $$\begin{pmatrix} v_1 & v_2 & \ldots & v_6 & v_7 \end{pmatrix}$$This gives us a map from $\mathbb{F}_2^{\oplus 7} \rightarrow \mathbb{F}_2^{\oplus 6}$: it must have a nonzero kernel.

Suppose $w \neq 0$ is in the kernel-by construction the subset of the 7 cards corresponding to in which coordinates $w$ has a 1 is your desired subset (i.e. each symbol occurs an even number of times).

Lemme know if you have qs :p (cool question btw, thanks for sharing!)

Answer 2

Suppose you have a subset $T$ of the set of 7 cards. Some symbols may appear an odd number of times in $T$, and some symbols an even number of times. Let $E(T)$ be the set of symbols appearing an even number of times in $T$. So $E(T)$ is a subset of your set of 6 symbols. There are $2^6=64$ different subsets of the set of 6 symbols, so 64 different possibilities for $E(T)$. But there are $2^7-1=127$ different (non-empty) subsets $T$ of the set of 7 cards. Since $127\gt64$, there must be two subsets of the set of 7 cards, call them $T_1$ and $T_2$, such that $E(T_1)=E(T_2)$. Now I claim that the symmetric difference of $T_1$ and $T_2$ is the set you want, with every symbol appearing an even number of times (the symmetric difference is the cards that are in $T_1$ or $T_2$ but not both). See if you can prove the claim - I'll be back later to see how things are going.

Answer 3

Represent each of the seven cards by a binary vector: the vector for card $i$ is $v_i=\langle b_{i1},\dots,b_{i6}\rangle$, where $b_{ij}=1$ if the $j$-th symbol appears on card $i$, and $b_{ij}=0$ otherwise. For $j=1,\dots,6$ and $\varnothing\ne S\subseteq\{1,\dots,7\}$ let $b^S_j=\left(\sum_{i\in S}b_{ij}\right)\bmod 2$, and let $v_S=\left\langle b^S_1,\dots,b^S_6\right\rangle$; the problem is to show that $v_S=\vec0$ for some non-empty $S\subseteq\{1,\dots,7\}$.

For each non-empty $S\subseteq\{1,\dots,7\}$ let $C(S)=\big\{j\in\{1,\dots,6\}:b^S_j=1\big\}$. There are $2^6=64$ possible values for $C(S)$. On the other hand, there are $2^7-1=127>64$ non-empty subsets of $\{1,\dots,7\}$. Thus, there are distinct non-empty $S,T\subseteq\{1,\dots,7\}$ such that $C(S)=C(T)$. It should be clear that if $S\cap T=\varnothing$, then $C(S\cup T)=\varnothing$, and therefore $v_{S\cup T}=\vec0$. What if $S\cap T\ne\varnothing$?

Fix $j\in\{1,\dots,6\}$. Then, with all arithmetic done mod $2$, we have

$$\begin{align*} 0&=1+1\\ &=\sum_{i\in S}b^S_i+\sum_{i\in T}b^S_i\\ &=\sum_{i\in S\setminus T}b^S_i+\sum_{i\in T\setminus S}b^T_i+\sum_{i\in S\cap T}\left(b^S_i+b^T_i\right)\\ &=\sum_{i\in S\setminus T}b^S_i+\sum_{i\in T\setminus S}b^T_i+\sum_{i\in S\cap T}\left(1+1\right)\\ &=\sum_{i\in S\setminus T}b^S_i+\sum_{i\in T\setminus S}b^T_i\\ &=\sum_{i\in S\Delta T}b^{S\Delta T}_i\;, \end{align*}$$

where $S\Delta T$ is the symmetric difference of $S$ and $T$. But then $C(S\Delta T)=\varnothing$, so $v_{S\Delta T}=\vec0$. (Note that $S\Delta T\ne\varnothing$, since $S\ne T$.) Of course $S\Delta T=S\cup T$ when $S\cap T=\varnothing$, so we didn’t really need the nice special case except as a pointer towards the more general result.

Note that a pigeonhole argument also underlies uncookedfalcon’s nice linear algebraic solution.