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.
Answer
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
No comments:
Post a Comment