11
$\begingroup$

This question is closely related to Green Hexagons Puzzle.

Start by choosing some triangles to be green. If a triangle is sharing an edge with at least 2 green triangles, it becomes green. This repeats for as long as possible. What's the minimal number of initial green triangles to make all triangles green? I have a solution I suspect is minimal, but no proof.

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ I assume touching means touching at the sides and not at the corners? $\endgroup$
    – Helena
    May 15, 2023 at 7:18
  • $\begingroup$ @Helena Yes, my mistake. $\endgroup$
    – PuzzleAndy
    May 15, 2023 at 8:30
  • $\begingroup$ I suppose you could do squares next for the sake of completeness? It's probably a good bit easier though... $\endgroup$ May 15, 2023 at 18:40
  • $\begingroup$ @DarrelHoffman Feel free to post it. Yes, maybe others haven't seen the solution and would be interested in solving it. $\endgroup$
    – PuzzleAndy
    May 15, 2023 at 18:43
  • $\begingroup$ I suppose it depends on how big a square you want to use. I'd have to think about it some (probably not while at work though...) $\endgroup$ May 15, 2023 at 18:45

5 Answers 5

8
$\begingroup$

This time we need a lot more than for the Green Hexagons Puzzle. The best I can do is

18:

grid with 18 cells filled

We definitely need at least

12 of the outermost cells

to be green, because:

  • at each corner of the whole hexagon there's 2 cells that can only be filled by each other being filled, so one of them must be filled from the beginning, giving 6 cells that must be initially green, and

  • we can't do anything with this unless we have one more green cell in each of the six little intervals, so that's another 6 cells that must be initially green.

Also, we definitely need at least

1 of the innermost (central 6) cells to be green, because we can't do anything with this.

That gives an absolute theoretical minimum of

13, and obviously we need more than that to fill the middle cells properly. I'm not 100% sure if 18 is optimal, but it's the best I could manage and it makes sense from a symmetry viewpoint as a multiple of 6.

$\endgroup$
7
  • $\begingroup$ I have a solution that uses fewer than 19. Would you like to know how many triangles I used, or would you rather hunt for yourself? $\endgroup$
    – PuzzleAndy
    May 14, 2023 at 18:45
  • 1
    $\begingroup$ @PuzzleAndy Improved to 18 :-) $\endgroup$ May 14, 2023 at 19:04
  • 2
    $\begingroup$ Your first linked "this" has some white cells with two green neighbors. $\endgroup$
    – RobPratt
    May 14, 2023 at 20:26
  • 1
    $\begingroup$ I agree. I'm only disputing the "we can't do anything" part. I think the claim can be salvaged by coloring these green, thereby making each of the six little intervals one cell littler. $\endgroup$
    – RobPratt
    May 14, 2023 at 20:53
  • 1
    $\begingroup$ But that correction yields a lower bound of 10. The little intervals overlap the 2-cell corners, so $6+6+1$ overcounts. $\endgroup$
    – RobPratt
    May 14, 2023 at 21:06
25
$\begingroup$

For a proof of minimality, consider

the quantity (perimeter + number of green triangles). This is nonincreasing; each time we add a triangle using the rule, the perimeter goes down by at least one, but the number of green triangles goes up by one.

In the goal state, this quantity is 72: we have all 54 triangles turned green, plus a perimeter of length 18.

Therefore we need at least 72/4, or 18, green triangles in the starting position.

$\endgroup$
7
  • $\begingroup$ +1 Elegant choice of potential function! And this additionally shows that all optimal solutions must have the $18$ initial triangles isolated from each other. $\endgroup$
    – RobPratt
    May 15, 2023 at 1:56
  • $\begingroup$ What perimeter is being calculated here? $\endgroup$
    – justhalf
    May 15, 2023 at 2:23
  • 2
    $\begingroup$ @justhalf Of the entire (possibly disconnected) green region $\endgroup$ May 15, 2023 at 3:09
  • 1
    $\begingroup$ @justhalf If two green triangles share an edge, that edge doesn't count towards the perimeter of the entire region. $\endgroup$ May 15, 2023 at 4:04
  • 3
    $\begingroup$ Ahh, so this is not about placing down green triangles from the initial position, but what happen after you're done placing down green triangles. All makes sense now. $\endgroup$
    – justhalf
    May 15, 2023 at 5:01
5
$\begingroup$

The minimum number of initial green triangles is...

...indeed $18$.

Define a graph with one node per triangle and an edge for each pair of adjacent triangles. This graph has $54$ nodes and $72$ edges. The problem is to minimize the number of initial green nodes so that all nodes are eventually green.

To derive the lower bound, I used integer linear programming to systematically search for small sets $C_k$ (in ascending order of cardinality) of nodes, at least one of which must initially be green. Let $N_i$ be the set of neighbors of node $i$. Let binary decision variable $g_i$ indicate whether node $i$ is ever green. The (cut-generating) problem is to maximize $\sum_i g_i$ subject to \begin{align} \sum_i (1 - g_i) &\ge 1 \tag1\label1 \\ \sum_{j\in N_i} g_j - 1 &\le (|N_i|-1) g_i &&\text{for all $i$} \tag2\label2 \\ \sum_{i\in C_k} g_i &\ge 1 &&\text{for all $k$} \tag3\label3 \end{align} Constraint \eqref{1} enforces that at least one node is never green. Constraint \eqref{2} enforces that a node that is never green has at most one green neighbor. That is, $g_i = 0 \implies \sum_{j\in N_i} g_j \le 1$. Constraint \eqref{3}, which is dynamically generated, forces $g_i=1$ for at least one node in $C_k$. Each time this subproblem is solved, a new constraint \eqref{3} is generated by incrementing $k$ and taking $C_k=\{i:g_i = 0\}$. Because we are maximizing, the cardinalities $|C_k|$ are automatically ascending. In particular, the first six $C_k$ have cardinality $2$ and correspond to the corners identified by @Rand al'Thor.

Given a set of valid inequalities defined by $C_k$, we can obtain a lower bound for the original problem by solving a different integer linear programming problem as follows. Let binary decision variable $x_i$ indicate whether node $i$ is initially green. The (set covering) problem is to minimize $\sum_i x_i$ subject to $$\sum_{i\in C_k} x_i \ge 1 \quad \text{for all $k$} \tag4\label4$$

Each time we solve the set covering problem, we obtain a valid lower bound on the original problem, and this bound is monotonic throughout the process because we are always introducing additional constraints. I alternated between solving the set covering master problem and solving the cut-generating subproblem until the lower bound returned by the master problem was...

...$18$. Because we know a solution that achieves $18$, this lower bound certifies the optimality.

I ended up generating $1277$ node sets $C_k$, and the frequencies of the cardinalities were as follows: \begin{matrix} \text{Cardinality} & \text{Frequency} \\ 2 &6 \\ 3 &12 \\ 6 &28 \\ 7 &6 \\ 8 &48 \\ 9 &24 \\ 10 &72 \\ 11 &160 \\ 12 &172 \\ 13 &207 \\ 14 &259 \\ 15 &197 \\ 16 &86 \end{matrix}

$\endgroup$
4
$\begingroup$

I thought it worth mentioning the generalization to filling an $n$-layer triangular grid with the minimal number of green triangles. Using Desouvi's beautiful invariant, we can prove that the number of triangles required is at least

$$\frac{\text{outer perimeter}+\text{total # of triangles}}4=\frac{6n+6n^2}{4}=\frac{3n(n+1)}{2}$$

This is attainable. I will do my best to describe the general method in words.

The lines of the grid form several concentric hexagons. One of these is the perimeter of the whole grid, which is a hexagon with side length $n$, and there are hexagons of every side length between $1$ and $n$, all of whose centers are at the center of the grid. For each of these $n$ hexagons, we will color exactly half of their line segments green. Namely, for each $k$ between $1$ and $n$, the hexagon with side length $k$ is made of $6k$ line segments, and we will alternate coloring every other of those green. There are two ways to do this, for each of the hexagons, and the choice of "phase" does not matter.

This means that we have colored

$$\frac{6\cdot 1}{2}+\frac{6\cdot 2}{2}+\dots+\frac{6\cdot n}2=\frac62\cdot\frac{n(n+1)}{2}=\frac{3n(n+1)}{2}$$

green segments. Therefore, the number green segments is equal to the target number of triangles. Finally, on each of those green segments, there are two neighboring triangles, one pointing inward, and the other pointing outward. The initial green triangles are the inward pointing triangles of each green segment. You can check that this will fill the entire grid. For example, here is the result when $n=5$.

enter image description here

$\endgroup$
2
$\begingroup$

Here's my solution. I went for symmetry:

18:
enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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