Problem

Source: IX International Festival of Young Mathematicians Sozopol, Theme for 10-12 grade

Tags: table, numbers in a table, combinatorics



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