16
$\begingroup$

This puzzle continues "Red cells in a 4x4 table".


Two cells in a $2016\times2016$ table are said to be interconnected, if they are in the same row or in the same column of the table. No cell is interconnected with itself. There are $r$ cells in the table that are colored red, and each of the $2016^2$ cells in the table is interconnected with at least two red cells.

Question: What is the smallest possible value for the number $r$ of cells in this table.

$\endgroup$
  • 1
    $\begingroup$ Maybe interesting for people to know is that if you consider the cells as vertices in a graph and each interconnection is an edge then the red cells form a Dominating set. The other way around is not true I think: not every Dominating set is a solution to this problem. $\endgroup$ – Ivo Beckers Apr 14 '16 at 13:16
  • $\begingroup$ is there a puzzle where diagonals are also considered interconnected? $\endgroup$ – JonMark Perry Apr 15 '16 at 8:50
11
$\begingroup$

This is a proof that Paul Evans solution is optimal. I write the solution in a different way but is the same

Solution :

I consider the $2016☓2016$ grid by blocks of $4☓4$ so we can reuse the solution to the $4☓4$ grid :
enter image description here
We can put this block on the diagonal of the $2016☓2016$ grid ( A and 0 are $4☓4$ blocks) :
\begin{array}{l} A&0&0&0&...\\0&A&0&0&... \\ 0&0&A&0&... \\ 0&0&0&A&...\\ \vdots & \vdots & \vdots & & \dots \end{array}

enter image description here

This solution is generic for $N☓N$ grid where N is multiple of 4 and there are $R=\frac{3}{2}*N$ red cells

Proof that it is an optimal solution for N when N is multiple of 4 (by recursion)

We want to prove that $R≥\frac{3}{2}*N$ in a valid grid.
You can easily find that :
- There cannot be empty rows or empty columns in an optimal grid.
- By moving some cells, we can change an optimal solution to an other optimal solution where every rows and columns has 3 or less red cells. I call it a reduced grid
- If you swap 2 lines or 2 rows of a valid grid, you still have a valid grid. If the grid was reduced, it still is.

Let's take a reduced valid grid which is optimal
There is at least one column with only 1 red cell (or we have more than 2*N red cells). This red cell need to be on a row with 3 red cells to have 2 interconnections.
=> we can find one row and one column with 3 red cells. Then we swap them to put them in the top left corner :
enter image description here

N-4 is a multiple of 4 so the $(N-4)☓(N-4)$ grid has more than $\frac{3}{2}*(N-4)$ red cells so the $N☓N$ grid has more than $\frac{3}{2}*(N-4) + 6 = \frac{3}{2}*N$ cells.

$\endgroup$
  • 2
    $\begingroup$ Nice :) Funny how the core argument is the same as for linear programming, that is, any single cell in a column must have 2 others in its row. Similar arguments for completely different proofs.... $\endgroup$ – tarulen Apr 15 '16 at 7:09
12
$\begingroup$

Is it

$2\cdot\frac34\cdot2016 = 3024$

Because

\begin{array}{l} r & - & \dots &- &-&-&-&-&-\\ r & - & \dots &- &-&-&-&-&-\\ r & - & \dots &- &-&-&-&-&-\\ - & r & \dots &- &-&-&-&-&-\\ - & r & \dots &- &-&-&-&-&-\\ - & r & \dots &- &-&-&-&-&-\\ \vdots & & & & & & & & \vdots\\ - & - &\dots & r & r & r & - & - & - \\ - & - &\dots & - & - & -& r & r & r \\ \end{array}

Is a solution.

It's 3 reds on top of each other shifting over one column and down three rows for the first $\frac34\cdot2016$ rows and first $\frac14\cdot2016$ columns and the mirror image through the main diagonal for the bottom rows and right columns.
This works as every cell is interconnected to at least 2 reds.
Let's call the formation of vertical red triplets spanning the first $\frac34\cdot2016$ rows and first $\frac14\cdot2016$ columns the vertical arm and likewise the formation of the horizontal red triplets in the bottom right the horizontal arm.
Consider a red triplet in the vertical arm.
If we remove a red then we will need a minimum of two reds on top of each other in the same rows as the remaining reds to maintain interconnectivity between all these reds.
We could now remove the corresponding red in the column of the two new reds from the horizontal arm.
But that's a net gain of one red so doesn't minimise the solution.
And if we add a red to this triplet we don't shorten the horizontal arm in fact if we add 3 or more we lengthen the horizontal arm so we're adding reds again.
So this solution (thanks to Trenin for pointing this out) is a local minimum.

$\endgroup$
  • $\begingroup$ I have the same solution and cant find better or prove that it is the best $\endgroup$ – Fabich Apr 14 '16 at 12:26
  • $\begingroup$ I think this probably is the generic solution for any $N \times N$ board. And if the problem statement didn't say "at least two red cells" but "at least $X$ red cells" then you always should make $X+1$ reds on top of each other I think. $\endgroup$ – Ivo Beckers Apr 14 '16 at 13:56
  • $\begingroup$ @IvoBeckers This can only be applied for $4N x 4N$ board. And "at least X red cells" is very different : if you make X+1 groups it does not work (take the top right cell for example, it still has 2 interconnections) $\endgroup$ – Fabich Apr 14 '16 at 14:40
  • $\begingroup$ @Lordofdark aah, of course you're absolutely right $\endgroup$ – Ivo Beckers Apr 14 '16 at 14:46
  • 4
    $\begingroup$ The argument for optimality is not rigorous. You are arguing that modifying this solution in some way either makes it worse or equivalent. This simply makes this solution a local minimum. It is still possible a completely different solution is possible that is not a few simple changes different from this one. $\endgroup$ – Trenin Apr 14 '16 at 14:59
11
$\begingroup$

The answer from @PaulEvans :

3024

Is optimal.

One way to prove it is via linear programming:

Write $r_1$ for the number of red cells in rows with a single red cell

Write $r_2$ for the number of red cells in rows with exactly 2 red cells

Write $r_3$ for the number of red cells in rows with at least 3 red cells

Write similarly $c_1,c_2,c_3$ for the same quantities column-wise, and $R$ for the total number of red squares.

Note that no row or column can be empty (if a row is empty, every column must contain at least 2 red cells, for a total of at least 2*2016. So this cannot occur in an optimal solution)

Now, we have some easy constraints:

$$R=r_1+r_2+r_3\\R=c_1+c_2+c_3\\2016 \leq r_1+\frac12 {r_2}+ \frac 13 r_3\\2016 \leq c_1+\frac12 {c_2}+ \frac 13 c_3$$

And 2 slightly more difficult constraints:

$$ r_1 \leq c_3 \quad c_1\leq r_3$$(indeed, any single element in a column must have at least 2 neighbors in the row, and vice versa)

We then need to

minimize $R$

which gives an optimal solution:

$R=3024$, $r_1=r_3=c_1=c_3=1512$. So 3024 is best!

To be perfectly convincing (i.e., make sure it's not a bug of my solver), we'd need a feasible solution fo the dual problem with the same value... if anyone is interested in giving one, please do :)

$\endgroup$
4
$\begingroup$

Partial answer

$2018 \le r \le 4030$

For a general case of an $N*N$ grid ($N\ge4$) the minimum is

$N+2$

Because each cell is interconnected with $2N-2$ cells and we need to cover $2*N^2$ cells, we need at least $\lceil \frac{2N^2}{2N-2}\rceil=N+2$

Alternative proof:

Imagine we could do it with less, that is $N+1$
We would then cover $(2N-2)(N+1)=2N^2-2$
Since we need to cover $2N^2$ connections, this is not enough. We will always need 2 more connections, independently of N.

The maximum is

$2N-2$

Because by filling an entire row and an entire column, while leaving out the cell where they overlap, we will satisfy the conditions

$\endgroup$
  • $\begingroup$ The N+2 solution needs a more rigorous proof, IMO. $\endgroup$ – CodeNewbie Apr 14 '16 at 13:17
  • $\begingroup$ Added a different proof $\endgroup$ – Kruga Apr 14 '16 at 13:33
1
$\begingroup$

It is

$2015*2 = 4030$

Reason

We need to ensure every cell is interconnected with at least two red cells. The easiest way to accomplish this is by filling the first column and row with red cells save for the one where they overlap. Any other orientation will be equivalent or produce additional unnecessary overlap.

$\endgroup$
  • 3
    $\begingroup$ Welcome to Puzzling! Other answers have done better so far. $\endgroup$ – Deusovi Apr 14 '16 at 13:29
  • $\begingroup$ So this is the easiest way, but can you show that it is the optimal way? $\endgroup$ – Alexander Apr 14 '16 at 13:31
0
$\begingroup$

Couldn't it be ...? Nvm, proven wrong

2016+2? If you color one diagonal and the other 2 corners...doesn't that give the expected result?

$\endgroup$
  • 1
    $\begingroup$ Don't all the reds not in a corner have no connected reds? $\endgroup$ – Paul Evans Apr 14 '16 at 12:52
  • $\begingroup$ I have colored all 4 corners, so that each corner has 2 connections too $\endgroup$ – Mario Garcia Apr 14 '16 at 12:53
  • $\begingroup$ I mean a red on the diagonal not in a corner, say one in the middle. What is it connected to? $\endgroup$ – Paul Evans Apr 14 '16 at 12:54
  • $\begingroup$ Ah yes, you're right there, it seemed like a too easy answer for me :( $\endgroup$ – Mario Garcia Apr 14 '16 at 12:55

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.