Let $P_{3}(r)$ be the number of 3 x 3 magic squares that are symmetric to their main diagonal. Prove that $P_{3}(r) \leq (r+1)^3$.
$r$ in this problem seems to be the sum of each row and column
This is the first time I've dealt with magic squares, didn't even know of their existence before today. But from what I gathered off the internet they're square matrices containing non-negative integers where all row sums and column sums are equal to each other.
This question is from the chapter on permutations, strings over finite alphabets, and problems of choice. But I don't know how to prove this. Any ideas?
Suppose that $a$ and $b$ have been selected:
$$\begin{pmatrix} a & ? & ?\\ ? & b & ? \\ ? & ? & ?\\ \end{pmatrix}$$
We can immediately deduce the following value:
$$\begin{pmatrix} a & ? & ?\\ ? & b & ? \\ ? & ? & (r-a-b)\\ \end{pmatrix}$$
Using symmetry we obtain these two values:
$$\begin{pmatrix} a & ? & \frac{r-b}{2}\\ ? & b & ? \\ \frac{r-b}{2} & ? & r-a-b\\ \end{pmatrix}$$
Using the sum of the first and last row we deduce:
$$\begin{pmatrix} a & \frac{r-b-2a}{2} & \frac{r-b}{2}\\ ? & b & ? \\ \frac{r-b}{2} & \frac{2a+b-r}{2} & r-a-b\\ \end{pmatrix}$$
Using the sum of the first and last column we deduce:
$$\begin{pmatrix} a & \frac{r+b-2a}{2} & \frac{r-b}{2}\\ \frac{r+b-2a}{2} & b & \frac{3b+2a-r}{2} \\ \frac{r-b}{2} & \frac{2a+3b-r}{2} & r-a-b\\ \end{pmatrix}$$
It is not hard to see that the sum of the middle column is $3b$ so in fact $b=\frac{r}{3}$
Now notice $a=\frac{2a+3b-r}{2}$, so $P_3(r)=0$ for all $r$.