\documentclass{article}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{color}
%\textheight 10.2in
%\hoffset -0.7in
%\textwidth 7.6in
%\marginparwidth 0in
%\footskip 20pt
\usepackage{amsmath}
\usepackage{amsfonts}   % if you want the fonts
\usepackage{amssymb}    % if you want extra symbols

\newtheorem{problem}{Problem}

\author{Jiri Lebl}

\begin{document}
\textbf{Problem 11002, year 2003, page 240}

\vspace{0.1in}
Solution by Jiri Lebl, 9635
Genesee Ave Apt E1, San Diego, CA 92121.  

\vspace{0.1in}
{\em Problem: Pooh Bear has $2N+1$ honey pots.  No matter which one of them he
sets aside, he can split the remaining $2N$ pots into two sets of the same
total weight each consisting of $N$ pots.  Must all $2N+1$ pots weight the
same?}

\vspace{0.1in}
We answer the question in the positive.  To prove this we must show
that for some $N$, if we take any one of the honey pots away, the remaining
cannot be split into two groups of the same weight and same number of pots
unless all the pots weight the same.  A solution would then have to satisfy
$2N+1$ equations (one for each pot taken away).  Each of these equations
be written in the form
\begin{equation*}
\alpha_1 x_1 + \alpha_2 x_2 + \cdots + \alpha_{2N+1} x_{2N+1} = 0,
\end{equation*}
where
$\alpha$'s are either $1$, $-1$ or $0$.  There is only one $\alpha$ which
is $0$ and the number of $1$'s and $-1$'s is equal.  So what we are looking
for is really the nullspace of a matrix which has zeros on the diagonal
and $1$'s and $-1$'s elsewhere, provided that the number of $1$'s and
$-1$'s in each row is equal.  For example when $2N+1 = 5$ then we may have
\begin{equation*}
\left[ \begin{array}{rrrrr}
0 & 1 & -1 & 1 & -1 \\
1 & 0 & 1 & -1 & -1 \\
1 & -1 & 0 & 1 & -1 \\
1 & -1 & -1 & 0 & 1 \\
1 & 1 & -1 & -1 & 0 \\
\end{array} \right] .
\end{equation*}
This matrix has nullity $1$.  What we would need to show is that every such
$5\times5$ matrix has nullity $1$ and that would mean that there is only one
solution (all pots of equal weight) no matter how Pooh divides the remaining
$2N$ pots.  We note that we could always just make the first column all ones
(except for the zero), since that would not change the solutions.  So we really
have matrices of the form
\begin{equation*}
\left[ \begin{array}{rr}
0 & \beta \\
1 & A \\
\end{array} \right],
\end{equation*}
where $A$ is a $2N\times2N$ matrix and $\beta$ is just a vector
of $1$'s and $-1$'s.  If we can show that every $2N\times2N$
matrix with zeros on the diagonal and $1$'s and $-1$'s elsewhere is invertible
then we are done.

So we now focus on computing the determinant of this matrix $A$.  We look
at the algebraic approach for computing determinants, that is
\begin{equation*}
det(A) = \sum_{\sigma \in S_{2N}} \epsilon(\sigma) \prod_{i=1}^{2N} a_{i\sigma(i)} ,
\end{equation*}
where $S_{2N}$ is the group of permutations of $2N$ elements and
$\epsilon(\sigma) = 1$ if $\sigma$ is an even permutation and
$\epsilon(\sigma) = -1$
if $\sigma$ is odd.  Now each of the products above is going to be either $1$,
$-1$ or $0$.  If we can show that the number of products that is $1$ or $-1$ is
odd, then this would mean the determinant will be odd, and thus the matrix
will be invertible, as then the determinant can't be zero.  So we want to
find all the products that do not involve any element of the diagonal (which
are zero) and count these.  So in the first row we can pick $2N-1$ elements to
start with,
since we can't pick the diagonal element.  So suppose we pick the element
$a_{1\,i}$, where $i \not= 1$.  Now we look at the row $i$, since that row
has a zero in the $i$'th column.  So from row $i$ we are still free to pick
$2N-1$ elements.  We repeat the argument with a row we have not yet picked
from (likely row 2, unless $i$ was 2).  From this row we can pick $2N-3$
elements, and then
using the same argument we can pick $2N-3$ from yet another row.  We continue
until we get the entire product which is either $1$ or $-1$.  So this means
that the number of different products which are $1$ or $-1$ is
\begin{equation*}
(2N-1)(2N-1)(2N-3)(2N-3)\cdots(3)(3)(1)(1),
\end{equation*}
and this is just an
odd number.  This means that the determinant of $A$ is odd, and thus not
$0$, and this means that
\begin{equation*}
nullity \,
\left[ \begin{array}{rr}
0 & \beta \\
1 & A \\
\end{array} \right] = 1,
\end{equation*}
which means that Pooh's honey pots better all be of the same weight.

\end{document}