A square is divided into 169 identical small squares and in every small square is written 0 or 1. It isn’t allowed in one row or column to have the following arrangements of adjacent digits in this order: 101, 111 or 1001. What is the the biggest possible number of 1’s in the table?
For every 5 consecutive squares from one row or column there are no more than two 1’s in them in order to satisfy the conditions (10001 or the two 1’s are adjacent). The table can be cut into 32 rectangles 1 x 5 or 5 x 1 with one square 3 x 3 in which there are no more than five 1’s with no more than one 1 for each letter:
a b a
c e c
d b d
Hence the number of 1’s that we can have is no more than 32.2 + 5= 69. The following example shows that we can have 69 1’s in the table:
1 1 0 0 0 1 1 0 0 0 1 1 0
0 1 1 0 0 0 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 0 0 0 1
0 0 0 1 1 0 0 0 1 1 0 0 0
1 0 0 0 1 1 0 0 0 1 1 0 0
1 1 0 0 0 1 1 0 0 0 1 1 0
0 1 1 0 0 0 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 0 0 0 1
0 0 0 1 1 0 0 0 1 1 0 0 0
1 0 0 0 1 1 0 0 0 1 1 0 0
1 1 0 0 0 1 1 0 0 0 1 1 0
0 1 1 0 0 0 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 0 0 0 1