Painting triangles in array

Question

In an $a\times b$ array, each cell is divided into four triangles by the two diagonals. Some of the $4ab$ triangles are painted, so that every unpainted triangle shares a side with at least one painted triangle. What is the minimum number of painted triangles?

Assume wlog that $a\leq b$. Suppose we paint the left triangle of every cell. This takes care of all triangles except the right triangles of the rightmost column. Painting those triangles gives $ab+a$ triangles in total. I think this should be the minimum, but how can it be proven?

Answer 1

Your limit is probably correct.

I have no proof, but I ran the MiniZinc constraint solver on the problem and found the following solution for $a=6, b=6$ as confirmation:

painted triangles = 42 = 6*6+6
+---+---+---+---+---+---+
| X | . | . | . | . | . |
|. .|. X|. X|. X|. X|. X|
| . | X | . | . | . | . |
+---+---+---+---+---+---+
| X | . | . | . | . | . |
|. .|. .|X .|X .|X .|X .|
| . | X | . | . | . | X |
+---+---+---+---+---+---+
| X | . | . | . | X | . |
|. .|. .|. X|. X|. .|. .|
| . | X | X | . | . | X |
+---+---+---+---+---+---+
| X | . | . | . | X | . |
|. .|. .|. .|. X|. .|. .|
| . | X | X | X | . | X |
+---+---+---+---+---+---+
| X | . | . | . | X | . |
|. X|. X|. X|. X|. .|. .|
| . | . | . | . | . | X |
+---+---+---+---+---+---+
| . | . | . | . | X | . |
|X .|X .|X .|X .|X .|. .|
| . | . | . | . | . | X |
+---+---+---+---+---+---+

My model:

int: a = 6; 
int: b = 6; 

int: Left = 1;
int: Top = 2;
int: Right = 3;
int: Bottom = 4;

set of int: Rows = 1..a;
set of int: Cols = 1..b;
set of int: Corners = 1..4;

%  Look-up tables for adjacent corners    Left    Top     Right   Bottom
array[Corners] of Corners: neighbour1 = [ Top ,   Left,   Top,    Left];
array[Corners] of Corners: neighbour2 = [ Bottom, Right,  Bottom, Right];
array[Corners] of Corners: neighbour3 = [ Right,  Bottom, Left,   Top];

%  Look-up tables to locate tile of neighbour3
array[Corners] of int: deltaRow =       [ 0,      -1,     0,      1];
array[Corners] of int: deltaCol =       [ -1,     0,     1,       0];

%  Decision variables: one bool per triangle
array[Rows, Cols, Corners] of var bool: painted;

% every unpainted triangle shares a side
% with at least one painted triangle

constraint
forall(row in Rows, col in Cols, c in Corners) (
  (not painted[row, col, c]) -> 
  (painted[row, col, neighbour1[c]] \/ 
   painted[row, col, neighbour2[c]] \/
   isPainted(row + deltaRow[c], col + deltaCol[c], neighbour3[c]))
);

function var bool: isPainted(int: row, int: col, int: c) =
  if (row in Rows) /\ (col in Cols) then painted[row, col, c] else false endif;

function string: it(bool: cond, string: y) =
  if cond then y else "" endif;

function string: ite(bool: cond, string: y, string: n) =
  if cond then y else n endif;

function string: itv(var bool: cond) =
  if fix(cond) then "X" else "." endif;

solve minimize sum([painted[row, col, c] | row in Rows, col in Cols, c in Corners]);

output
["sum = " ++ show(sum([painted[row, col, c] | row in Rows, col in Cols, c in Corners]))] ++
[it((col == 1) /\ (c == 1), "\n") ++
 it((r == 1) /\ (c == 1), "+") ++
 it((r != 1) /\ (c == 1), "|") ++
 it((r == 1) /\ (c != 1), "-") ++
 it((r == 2) /\ (c == 2), " ") ++
 it((r == 2) /\ (c == 3), itv(painted[row, col, Top])) ++
 it((r == 2) /\ (c == 4), " ") ++
 it((r == 3) /\ (c == 2), itv(painted[row, col, Left])) ++
 it((r == 3) /\ (c == 3), " ") ++
 it((r == 3) /\ (c == 4), itv(painted[row, col, Right])) ++
 it((r == 4) /\ (c == 2), " ") ++
 it((r == 4) /\ (c == 3), itv(painted[row, col, Bottom])) ++
 it((r == 4) /\ (c == 4), " ") ++
 it((col == b) /\ (c == 4), ite(r == 1, "+", "|"))
 | row in Rows, r in 1..4, col in Cols, c in 1..4 ] ++
 ["\n"] ++
 [ite(c == 1, "+", "-")|col in Cols, c in 1..4] ++ ["+\n"];

A biger example with $a=10, b=42$ has $430$ painted triangles as predicted: