1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ what is $r$? Are the elements in $\{0,1,2,\dots,r\}$? $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 22:23
  • $\begingroup$ r is the sum of each row and column. I just edited it in. Sorry about that $\endgroup$ – user482578 Oct 4 '17 at 22:31
  • $\begingroup$ In fact you can bound it by $(r+1)^ 2$ $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 22:34
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ So since $P_{3}(r) = 0$ for all $r$ then it is $\leq (r+1)^{3}$? $\endgroup$ – user482578 Oct 5 '17 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy