# Red cells in a 4x4 table

We say that two cells in a $4\times4$ table are interconnected, if they are in the same row or in the same column. No cell is interconnected with itself. There are $r$ cells in the table that are colored red, and each of the $16$ cells in the table is interconnected with at least two red cells.

Determine the smallest possible value for the number $r$ of cells in the table.

I think $r = 6$

If X is a red cell and 0 a white cell

\begin{array}{l} X&0&0&0\\X&0&0&0 \\ X&0&0&0 \\ 0&X&X&X \\ \end{array}
Number of interconnections for each cell :
\begin{array}{l} 2&2&2&2\\2&2&2&2 \\ 2&2&2&2 \\ 6&2&2&2 \\ \end{array}

This is the minimum because

We need 32 interconnections (2 per cell for 16 cells)
1 red cell create 6 interconnections (3 in the line and 3 in the column)
The first multiple of 6 bigger than 32 is 36=6*6 so we need at least 6 red cells

• +1 Nice logic, though the solution itself is rather obvious. Apr 14 '16 at 10:44