Problem: At a certain mathematical conference,
every pair of mathematicians are either friends or strangers.
At mealtime, every participant eats in one of two large dining rooms.
Each mathematician insists upon eating in a room which
contains an even number of his or her friends.
Prove that the number of ways that the mathematicians
may be split between the two rooms is a power of two
(i.e.\ is of the form $2^k$ for some positive integer $k$).

\end{enumerate}

Solution: Take the obvious graph interpretation
where we are trying to $2$-color a graph.
Let $A$ be the adjacency matrix of the graph over $\FF_2$,
except the diagonal of $A$ has $\deg v \pmod 2$ instead of zero.
Then let $\vec d$ be the main diagonal.
Splittings then correspond to $A \vec v = \vec d$.
It's then immediate that the number of ways is either zero
or a power of two, since if it is nonempty it is a coset of $\ker A$.

Thus we only need to show that:
\begin{claim*}
  At least one coloring exists.
\end{claim*}
\begin{proof}
If not, consider a minimal counterexample $G$.
Clearly there is at least one odd vertex $v$.
Consider the graph with vertex set $G-v$,
where all pairs of neighbors of $v$ have their edges complemented.
By minimality, we have a good coloring here.
One can check that this extends to a good coloring on $G$
by simply coloring $v$ with the color matching an even number of its neighbors.
This breaks minimality of $G$, and hence all graphs $G$ have a coloring.
\end{proof}

It's also possible to use linear algebra.
We prove the following lemma:
\begin{lemma*}[grobber]
Let $V$ be a finite dimensional vector space,
$T \colon V \to V$ and $w \in V$.
Then $w$ is in the image of $T$ if and only if
there are no $\xi \in V^\vee$ for which $\xi(w) \neq 0$
and yet $\xi \circ T = 0$.
\end{lemma*}

\begin{proof}
Clearly if $T(v) = w$, then no $\xi$ exists.
Conversely, assume $w$ is not in the image of $T$.
Then the image of $T$ is linearly independent from $w$.
Take a basis $e_1$, \dots, $e_m$ for the image of $T$, add $w$,
and then extend it to a basis for all of $V$.
Then have $\xi$ kill all $e_i$ but not $w$.
\end{proof}

\begin{corollary*}
  In a symmetric matrix $A$ mod $2$,
  there exists a vector $v$ such that $Av$ is a copy of the diagonal of $A$.
\end{corollary*}
\begin{proof}
  Let $\xi$ be such that $\xi \circ T = 0$.
  Look at $\xi$ as a column vector $w^\top$, and let $d$ be the diagonal.
  Then \[ 0 = w^\top \cdot T \cdot w = \xi(d) \]
  because this extracts the sum of coefficients submatrix of $T$,
  and all the symmetric entries cancel off.
  Thus no $\xi$ as in the previous lemma exists.
\end{proof}
This corollary gives the desired proof.