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

  • $\begingroup$ +1 Nice logic, though the solution itself is rather obvious. $\endgroup$ – ghosts_in_the_code Apr 14 '16 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.