Let $X$ be a $5\times 5$ matrix with each entry be $0$ or $1$. Let $x_{i,j}$ be the $(i,j)$-th entry of $X$ ($i,j=1,2,\hdots,5$). Consider all the $24$ ordered sequence in the rows, columns and diagonals of $X$ in the following: \begin{align*} &(x_{i,1}, x_{i,2},\hdots,x_{i,5}),\ (x_{i,5},x_{i,4},\hdots,x_{i,1}),\ (i=1,2,\hdots,5) \\ &(x_{1,j}, x_{2,j},\hdots,x_{5,j}),\ (x_{5,j},x_{4,j},\hdots,x_{1,j}),\ (j=1,2,\hdots,5) \\ &(x_{1,1},x_{2,2},\hdots,x_{5,5}),\ (x_{5,5},x_{4,4},\hdots,x_{1,1}) \\ &(x_{1,5},x_{2,4},\hdots,x_{5,1}),\ (x_{5,1},x_{4,2},\hdots,x_{1,5}) \end{align*}Suppose that all of the sequences are different. Find all the possible values of the sum of all entries in $X$.
Problem
Source: 2019 CSMO Grade 11 P4
Tags: combinatorics, Bashing, matrix
30.07.2019 13:34
I think the answer is [12,13]
30.07.2019 13:54
This solution is wrong, while it has some helpful observations, it is not complete, maybe I'll complete another day, There are $2^5=32$ binary sequences of length $5$ and there are $2^3=8$ palindromes, so these sequences must be all non-palindromic ones (we're considering a sequence as a binary number). The sum of digits of all binary sequences of length $5$ is $5+4\cdot5+3\dbinom{5}{2}+2\dbinom{5}{3}+5=80$, and this sum at palindromes is $20$, therefore the sum of entries at the $24$ sequences is $80-20=60$. @below thanks
30.07.2019 15:24
XbenX wrote: There are $2^5=32$ binary sequences of length $5$ and there are $2^3=8$ palindromes, so these sequences must be all non-palindromic ones (we're considering a sequence as a binary number). The sum of digits of all binary sequences of length $5$ is $5+4\cdot5+3\dbinom{5}{2}+2\dbinom{5}{3}+5=80$, and this sum at palindromes is $3+2\dbinom{3}{2}+3=12$, therefore the sum of entries at the $24$ sequences is $80-12=68$. Note that the numbers on the diagonals are counted $5$times and the numbers not on diagonals are counted $4$ times, so let $k$ be the sum of numbers in diagonals, and $t$ be the sum of other numbers, so we have that $$5k+4t=68$$and since there are $10$ numbers on diagonals, we have that $k=4$ or $k=8$ since $4 \mid 68$. For $k=4$ we have that $t=12$, and for $k=8$ we have $t=6$, so the possible sums are $k+t=16$ or $14$. (I'm too lazy to check wich one of them works) But the numbers on the diagonals are counted 6 times,not 5times.
30.07.2019 18:14
The number in the center is counted 8 times,not 6times.
30.07.2019 23:41
The answer is $12,13$. Let $n$ (stands for not-on-diagonal) denote the sum of entries on cells that do not lie on two diagonals. Let $d$ (stands for diagonal) denote the sum of entries on cells that lie on two diagonals, except the center cell. Let $c$ (stands for center) denote the entry on the center cell. By double counting as in #3 we found that $4n+6d+8c=60\implies 2n+3d+4c=30$. So $2\mid d$. Let $d=2d'$. We get $n+3d'+2c=15$. The sum of all entries in $X$ is equal to $s:=n+2d'+c=15-d'-c$. Since all our variables are integer and $d'$ cannot equal to $4$ (in that case we easily found the palindrome on diagonals). We get that $$11=15-3-1\leqslant s=15-d'-c\leqslant 15-1-0=14.$$Since the problem is symmetric over switching $0$ to $1$ and vice versa in all entries, it's enough to show that $s=11$ is impossible and $s=12$ is possible. For the first part. By our bound, we get $c=1$ and $d=2d'=6$. This means the two $0$ entries on two diagonals must be on distinct ones. And note that the sequence produced from the two diagonals can't be the same, which reduces some cases. For the remaining cases may WLOG the entries to be the one in the table below. $$\begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & \\ \hline & & 1 & & \\ \hline & 1 & & 1 & \\ \hline 1 & & & & 0 \\ \hline \end{tabular}$$Consider the sequence $0,0,0,0,1$. From the table above, it must be one of the four borders. This gives us two cases: $$\begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & \\ \hline & & 1 & & \\ \hline & 1 & & 1 & \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{tabular} \quad \begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & 0 \\ \hline & & 1 & & 0 \\ \hline & 1 & & 1 & 0 \\ \hline 1 & & & & 0 \\ \hline \end{tabular}$$For the left table, we have the following sequence of logic: $a_{12}\neq a_{52}\implies a_{12}=1$. $a_{32}$ must be $0$ (else there's two $1,1,1,1,0$). Since $a_{41}\neq a_{45}$, we're forced to create two $1,1,1,1,0$ when $a_{43}=1$ and two $1,1,0,1,0$ when $a_{43}=0$. $$\begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & \\ \hline & & 1 & & \\ \hline & 1 & & 1 & \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{tabular} \implies \begin{tabular}{|l|l|l|l|l|} \hline 1 & 1 & & & 1 \\ \hline & 1 & & 0 & \\ \hline & & 1 & & \\ \hline & 1 & & 1 & \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{tabular} \implies \begin{tabular}{|l|l|l|l|l|} \hline 1 & 1 & & & 1 \\ \hline & 1 & & 0 & \\ \hline & 0 & 1 & & \\ \hline & 1 & & 1 & \\ \hline 1 & 0 & 0 & 0 & 0 \\ \hline \end{tabular}$$For the right table, we have the following sequence of logic: $a_{41}\neq a_{45}\implies a_{41}=1$. $a_{43}$ must be $0$ (else there's two $1,1,1,1,0$). Since $a_{12}\neq a_{15}$, we're forced to create two $1,1,1,1,0$ when $a_{13}=1$ and two $1,1,0,1,0$ when $a_{13}=0$. $$\begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & 0 \\ \hline & & 1 & & 0 \\ \hline & 1 & & 1 & 0 \\ \hline 1 & & & & 0 \\ \hline \end{tabular} \implies \begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & 0 \\ \hline & & 1 & & 0 \\ \hline 1 & 1 & & 1 & 0 \\ \hline 1 & & & & 0 \\ \hline \end{tabular} \implies \begin{tabular}{|l|l|l|l|l|} \hline 1 & & & & 1 \\ \hline & 1 & & 0 & 0 \\ \hline & & 1 & & 0 \\ \hline 1 & 1 & 0 & 1 & 0 \\ \hline 1 & & & & 0 \\ \hline \end{tabular}$$These two cases conclude $s\neq 11$. For construction, we have the following table $$\begin{tabular}{|l|l|l|l|l|} \hline 0 & 1 & 0 & 0 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 \\ \hline 0 & 0 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 1 \\ \hline \end{tabular}$$