Pintar triángulos en array

Question

En un $a\times b$ cada celda está dividida en cuatro triángulos por las dos diagonales. Algunas de las $4ab$ triángulos están pintados, de modo que cada triángulo no pintado comparte un lado con al menos un triángulo pintado. ¿Cuál es el número mínimo número de triángulos pintados?

Supongamos wlog que $a\leq b$ . Supongamos que pintamos el triángulo izquierdo de cada celda. Esto se encarga de todos los triángulos excepto los triángulos de la derecha de la columna más a la derecha. Al pintar esos triángulos se obtiene $ab+a$ triángulos en total. Creo que esto debería ser el mínimo, pero ¿cómo se puede demostrar?

Answer 1

Su límite es probablemente correcto.

No tengo pruebas, pero he comprobado la MiniZinc solucionador de restricciones en el problema y encontró la siguiente solución para $a=6, b=6$ como confirmación:

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 |
+---+---+---+---+---+---+

Mi modelo:

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"];

Un ejemplo más grande con $a=10, b=42$ tiene $430$ triángulos pintados como se predijo: