Deje $G$ ser el grafo con vértices $v_1,\ldots,v_k$, representando a la gente
y con bordes cuando dos personas se conocen.
Deje $F$ a ser el campo con 2 elementos.
Deje $V$ $k$- dimensiones vectorspace $F$.
Consideramos que los elementos de $V$ que representan los posibles subconjuntos de personas,
es decir, $(x_1,\ldots,x_n)$ representa el subconjunto $A$ donde $v_i\in A$ si y sólo si $x_i=1$.
Deje $W$ otro $k$-dimensiones vectorspace $F$.
Sus elementos son los que van a ser interpretadas como las paridades de los grados de los vértices en su propia habitación (es decir, la partición).
Ejemplo: para $k=3$ el elemento $(0,1,0)$ $W$ se interpreta como:
$v_1$ $v_3$ tiene un número par de conocidos en la misma habitación,
$v_2$ tiene un número impar de los conocidos en la misma habitación.
Se nota que no es en absoluto garantía de que cada elemento de a $W$ corresponde a una configuración existente.
Para cada una de las $i=1,\ldots,k$, podemos definir un mapeo $s_i:W\to W$ como sigue:
$s_i(a_1,\ldots,a_k)=(b_1,\ldots,b_k)$ donde
- $b_j=1-a_j$ si $v_i$ $v_j$ son vecinos,
- $b_i=1-a_i$ si el grado (número total de los conocidos) de $v_i$ es impar,
- $b_i=a_i$ si el grado de $v_i$ es aún, y
- $b_j=a_j$ lo contrario.
Esta asignación corresponde exactamente a la paridad de los cambios que se producen al mover $v_i$ a la otra habitación (verificar!).
La composición de la $s_i$ es conmutativa (verificar!), así es fácil ver que la colección
de todas las $F$-combinaciones lineales de las $s_i$ es un espacio vectorial sobre $F$, donde la composición
tiene la función de espacio vectorial (verificar!). Llamar a este espacio vectorial $T$.
Definir la asignación $g:V\to T$ asignando a $(x_1,\ldots,x_k)$ la composición de los
$s_i$ que $x_i$ es distinto de cero.
Ejemplo: para $k=3$ el elemento $(0,1,1)$ mapa a $s_2\circ s_3$.
A continuación, $g$ es lineal (verifique!) y su núcleo representa subconjuntos de a $\{v_1,\ldots,v_k\}$
que no causan cambios de paridad cuando se trasladó a la otra sala al mismo tiempo.
Dado que el núcleo de un lineal mapa es un espacio vectorial en sí mismo, su cardinalidad es una potencia de 2, decir $2^n$.
Ahora hemos demostrado que para cada posible(!) la paridad de la distribución, hay exactamente $2^n$
las configuraciones de la realización de esta distribución.
Esto reduce el problema a mostrar que hay al menos una configuración donde todas las correlaciones son 0 y este problema se resuelve aquí (gracias Alex).
