Considere una juego de tarjeta-paridad

Question

Considere la posibilidad de un juego de cartas donde la cubierta se compone de 63 cartas distintas. La cubierta se crea de la siguiente manera: cada tarjeta consta de un cierto número de símbolos, donde no hay dos símbolos son los mismos. Hay seis diferentes símbolos. Tenemos $\binom{6}{1}=6$ tarjetas con 1 símbolo de cada uno de ellos, tenemos $\binom{6}{2}=15$ tarjetas con 2 símbolos de cada una de ellos, y así sucesivamente hasta llegar a la única $\binom{6}{6}=1$ tarjeta que cuenta con seis símbolos.

Un juego se compone de un cierto número de tarjeta de que dentro del conjunto, el número de veces que cada símbolo que aparece es incluso.

¿Cómo podemos demostrar que, dado cualquier 7 cartas en la baraja, podemos encontrar al menos un conjunto?

Answer 1

Supongamos que usted tiene un subconjunto $T$ del conjunto de 7 cartas. Algunos símbolos pueden aparecer un número impar de veces en $T$, y algunos símbolos de un número par de veces. Deje $E(T)$ el conjunto de símbolos que aparece un número par de veces en $T$. Por lo $E(T)$ es un subconjunto del conjunto de 6 símbolos. Hay $2^6=64$ diferentes subconjuntos del conjunto de los 6 símbolos, de modo 64 diferentes posibilidades para $E(T)$. Pero hay $2^7-1=127$ diferente (no vacío) de subconjuntos de a $T$ del conjunto de 7 cartas. Desde $127\gt64$, debe haber dos subconjuntos del conjunto de 7 cartas, llamar a$T_1$$T_2$, de tal manera que $E(T_1)=E(T_2)$. Ahora me reclaman que la diferencia simétrica de a $T_1$ $T_2$ es el conjunto que desea, con cada uno de los símbolos que aparecen un número par de veces (la diferencia simétrica es el de las tarjetas que están en $T_1$ o $T_2$, pero no tanto). Vea si usted puede probar que la afirmación - volveré más tarde para ver cómo van las cosas.

Answer 2

Kk creo que los siguientes trabajos. Vamos a llamar a nuestros 7 tarjetas de $c_1, \ldots c_7$. Ver los "símbolos de la tarjeta de $c_j$" como un elemento $v_j$$\mathbb{F}_2^{\oplus 6}$: es decir, si nuestro 6 posibles símbolos se $s_1, \ldots s_6$, vamos a la $i^{th}$ coordinar $v_j$ ser el número de veces que $s_i$ aparece en la tarjeta.

Por ejemplo, si $c_1$ lee: $s_1 s_3 s_5$, $v_1 = (1, 0, 1, 0, 1, 0)$.

Ahora toma tus 7 cartas, y mirar sus correspondientes vectores de lado a lado, es decir, forman la matriz $$\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}$: se debe tener un kernel distinto de cero.

Supongamos $w \neq 0$ está en el núcleo de la construcción el subconjunto de las 7 cartas correspondiente en el que coordina $w$ tiene un 1 es su subconjunto deseado (es decir, cada símbolo se produce un número par de veces).

Déjame saber si usted tiene qs :p (cool pregunta btw, gracias por compartir!)

Answer 3

Representan a cada una de las siete cartas por un binario de vectores: el vector de la tarjeta de $i$ $v_i=\langle b_{i1},\dots,b_{i6}\rangle$ donde $b_{ij}=1$ si $j$-ésimo símbolo aparece en la tarjeta)$i$, e $b_{ij}=0$ lo contrario. Para $j=1,\dots,6$ $\varnothing\ne S\subseteq\{1,\dots,7\}$ deje $b^S_j=\left(\sum_{i\in S}b_{ij}\right)\bmod 2$, y deje $v_S=\left\langle b^S_1,\dots,b^S_6\right\rangle$; el problema es demostrar que el $v_S=\vec0$ para algunos no vacía $S\subseteq\{1,\dots,7\}$.

Para cada no-vacía $S\subseteq\{1,\dots,7\}$ deje $C(S)=\big\{j\in\{1,\dots,6\}:b^S_j=1\big\}$. Hay $2^6=64$ posibles valores de $C(S)$. Por otro lado, hay $2^7-1=127>64$ no vacía de subconjuntos de a $\{1,\dots,7\}$. Por lo tanto, hay distintas que no se vacía $S,T\subseteq\{1,\dots,7\}$ tal que $C(S)=C(T)$. Debe quedar claro que si $S\cap T=\varnothing$,$C(S\cup T)=\varnothing$, y por lo tanto $v_{S\cup T}=\vec0$. Lo que si $S\cap T\ne\varnothing$?

Fix $j\in\{1,\dots,6\}$. Entonces, con toda la aritmética hecho de mod $2$, tenemos

$$\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*}$$

donde $S\Delta T$ es la diferencia simétrica de a$S$$T$. Pero, a continuación,$C(S\Delta T)=\varnothing$, lo $v_{S\Delta T}=\vec0$. (Tenga en cuenta que $S\Delta T\ne\varnothing$, ya que el $S\ne T$.) De curso $S\Delta T=S\cup T$ al $S\cap T=\varnothing$, por lo que no necesitan realmente la agradable caso especial, excepto como un puntero hacia el más general de resultados.

Tenga en cuenta que una caja argumento subyace también uncookedfalcon bueno algebraicas lineales solución.