Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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.

share|improve this answer
    
Oops! You must have posted this just as I was starting to write up my answer, since I got no notification. –  Brian M. Scott Aug 15 '12 at 2:19
    
@Gerry How does the proof for the symmetric difference finish our proof? –  Xuan Huang Aug 15 '12 at 15:07
    
The number of times any symbol appears in the symmetric difference is the number $n_1$ of times it appears in $T_1$, plus the number $n_2$ of times it appears in $T_2$, minus twice the number of times it appears in $T_1\cap T_2$, right? And, modulo 2, that's just $n_1+n_2$, right? And by construction of $T_1,T_2$ we know $n_1,n_2$ have the same parity, right? So $n_1+n_2$ is even, and we're done. –  Gerry Myerson Aug 16 '12 at 6:38

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.

share|improve this answer

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!)

share|improve this answer
    
the tongue out smiley just does not look as adorable as it ought to in this font.... :/ –  uncookedfalcon Aug 15 '12 at 1:04
    
Hi I cannot understand how the map works. How from $\begin{pmatrix} v_1 & v_2 & \ldots & v_6 & v_7 \end{pmatrix}$ you get an element in $\mathbb{F}_2^{\oplus 7} $ and where it is sent? thank you –  clark Aug 15 '12 at 1:11
    
er all i'm saying is that a 6 x 7 box of numbers $(v_1 v_2 \ldots )$ can be interpreted as a linear transformation from $k^7 \rightarrow k^6$ (this is just the usual thing where a matrix represents a linear transformation). does that make sense? –  uncookedfalcon Aug 15 '12 at 1:36
    
(+1)Ok I got all wrong, I see now. Thanks –  clark Aug 15 '12 at 1:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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