Let $n > 4$ be an integer. A square is divided into $n^2$ smaller identical squares, in some of which were 1’s and in the other – 0's. It is not allowed in one row or column to have the following arrangements of adjacent digits in this order: $101$, $111$ or $1001$. What is the biggest number of 1’s in the table? (The answer depends on $n$.)
Problem
Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade
Tags: table, numbers in a table, combinatorics
NikoIsLife
22.09.2018 15:51
The conditions for each row/column can be restated as follows:
(i) You can only have at most two consecutive $1's$.
(ii) Each block of $0's$ must always have at least three consecutive $0's$.
Note that for every two $1's$, we must always have at least three $0's$.
If $n$ is divisible by $5$, then the answer would be $\frac{2n^2}5$.
You can do it as follows:
\begin{tabular}{llllllllll}
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1
\end{tabular}where for every row or column, the pattern $11000$ repeats.
Pinko
24.08.2019 22:52
Let $n=5k+r$, where $k\in \mathbb{N}$ and $r=0,1, 2, 3, 4$. We partition the given table into the following smaller tables: $5k\, x\, 5k, 5k\, x\, r, 5k\, x\, r,$ and $r\, x\, r$. Using what we have found in this Problem, we see that among every 5 consecutive numbers we can have two 1's at most. This means that we would have at most $2k(5k+2r)$ 1's in the first 3 tables, leaving us with calculating the number of 1's in the remaining $r\, x\, r$ table. For all the following cases we will fill the table as NikoIsLife has shown: Case 1: $r=0$. It is the easiest one, as we only have the $5k\, x\, 5k$ table, which leads to $\frac{2n^2}{5}$ 1's at most, as NikoIsLife had already found. Case 2: $r=1$. We start the table in the following way: \begin{tabular}{llllllllll} 1 & 1 & 0 & 0 & 0 & . & . & . \\ 1 & 0 & 0 & 0 & 1 & . & . & . \\ 0 & 0 & 0 & 1 & . & . & . & . \\ . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . \\ \end{tabular}which leads to the $1\, x\, 1$ table having 1 in it. Thus in this case the greatest number of 1's is $2k(5k+2)+1$. By similar reasoning we can cover the remaining three cases: For $r=2$, we see that we can have at most 3 1's in the $r\, x\, r$ table, leading to $2k(5k+4)+3$ 1's; $r=3$ gives at most 5 1's in the $r\, x\, r$ table (as we have seen in this Problem) so $2k(5k+6)+5$ at most, and $r=4$ leaves us with at most $2k(5k+8)+7$ 1's, with 7 being the max number of 1's in the $r\, x\, r$ table.
Attachments:
