Professor Halfbrain and the 99x99 chessboard (Part 1)
Professor Halfbrain has spent the last weekend with filling the squares of a $99\times99$ chessboard with real numbers from the interval $[-1,+1]$. Whenever four squares form the corners of a rectangle (with sides parallel to the sides of the chessboard), then the four numbers in these squares had to add up to zero.
Professor Halfbrain has proved two extremely deep theorems on this.
Professor Halfbrain's first theorem: It is possible to fill the chessboard subject to the above rules, so that the sum of all numbers in all the squares is $0$.
Professor Halfbrain's second theorem: If we fill the chessboard subject to the above rules, then the sum of all numbers in all the squares is at most $9801$.
This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $x$, so that "the sum in all the squares is $0$" in the first theorem may be replaced by "the sum in all the squares is $x$", and so that "the sum is at most $9801$" in the second theorem may be replaced by "the sum is at most $x$" (again yielding true statements, of course).
mathematics combinatorics checkerboard
$\begingroup$ I have a feeling that a board filled with zeroes is the only possible solution but not sure how to prove it (yet) $\endgroup$
– Ivo Beckers
$\begingroup$ I think this problem is more interesting for corners of squares rather than rectangles, where the same result holds. $\endgroup$
– xnor
This is a sketchy proof of what Ivo suspected in the comments.
Take an arbitrary selection as below.
$A+B+E+F = 0$
$A+B+I+K = 0$
$=> E+F=I+K$
$E+F+I+K = 0$
$=>E +F = -I-K$
$E = -F$
$I = -K$
Similarily, we can obtain
$F+K+E+I = 0$
$G+L+F+K = G+L + E+ I = 0 => F+K-E-I = 0$
$F = -K$
$E = -I$
$F = I$
$E = K$
So, for an arbitrary selection, we know that the diagonal elements are equal. Taking an arbitrary selection with odd sides (e.g. $A+C+I+L = 0$), we know that $A,C,I,L$ must be equal and hence 0. Since this can be done for all squares, they must all be 0.
Carl LöndahlCarl Löndahl
$\begingroup$ I was about to show that you can take some values which arent 0, but then i followed the last short paragraph and came to your conclusion, the values are 0. It's a nice proof, i think it's enough to prove all values have to be 0. $\endgroup$
– Piotr Pytlik
A clarification on Carl Löndahl's proof: He has shown that for any two adjacent squares, the numbers must add up to $0$. Hence, it must form an alternating pattern for some value $a$: $$\begin{matrix} +a & -a & +a & -a & \ldots\\ -a & +a & -a & +a & \ldots\\ +a & -a & +a & -a & \ldots\\ -a & +a & -a & +a & \ldots\\\vdots & \vdots & \vdots & \vdots & \ddots\end{matrix}$$
But now, consider a 3x3 square with $+a$ in one (and therefore all) corners. This gives $4a = 0$, so $a = 0$. Every square on the board must be $0$.
Paul SinclairPaul Sinclair
Pick any four points that form a rectangle:
$$\begin{matrix} a_1 & \ldots & a_2\\ \vdots & \ldots & \vdots\\ a_3 & \ldots & a_4 \end{matrix}$$
We know that the sum of these four points is zero.
$$a_1+a_2+a_3+a_4=0$$
Consider the two additional points $b_1$ and $b_2$.
$$\begin{matrix} a_1 & \ldots & a_2 & \ldots & b_1\\ \vdots & \ldots & \vdots\\ a_3 & \ldots & a_4 & \ldots & b_2 \end{matrix}$$
These points form two additional rectangles (one large, and one smaller on the the right), so we get two more equations;
$$a_1+a_3+b_1+b_2=0$$ $$a_2+a_4+b_1+b_2=0$$
Taking the difference of these equations shows us that:
$$a_1+a_3=a_2+a_4$$
Substituting in our first equation, we get
$$a_1+a_3+a_1+a_3=0 \implies a_1=-a_3$$
Since our choice of points was arbitrary, we know that any two points that share a side of a rectangle must be the opposite sign.
Thus we have:
$$a_1=-a_2, a_1=-b_1, a_2=-b_1 \implies a_1=-a_1$$
The only way to satisfy these equations is if they are all zero.
Thus (again since our choice of points was arbitrary) all the points must be zero.
TreninTrenin
Not the answer you're looking for? Browse other questions tagged mathematics combinatorics checkerboard or ask your own question.
Polyominoes on a checkerboard
Points on a cube
Musings at a chess tournament
"Legally" filling a 10x10 table with 10 of each digit
Professor Halfbrain's chessboard theorems
Professor Halfbrain's chessboard dissection theorem
Professor Halfbrain and the 52 cards