The question is from Roland Backhouse Algorithmic Problem Solving.
Suppose a rectangular board can be covered with T-tetrominoes. Show that the number of squares is a multiple of 8.
The almost-complete solution to this problem is presented in the book. However, the author is not explicit in calculating an invariant for
$$d, b, w := d+1, b+3, w+1$$
$$l, b, w := l+1, b+1, w+3$$
where:
- $d$ number of dark (3sq black 1 sq white) tetrominoes
- $l$ number of light (3sq white 1 sq black) tetrominoes
- $w$ number of white squares on the board that are covered
- $l$ number of black squares on the board that are covered
The invariant is presented as b-3*d-l. A note explains that it was obtained by assuming the invariant is a linear combination of the variables and the coefficients are calculated based on this premise.
My attempt, starting with
$$((A*d) + (B*b) + (C*w))[d, b, w := d+1, b+3, w+1]$$ yields
$$A*d + A + B*b + 3*B + C*w + C$$
And I'm stuck on how to transform this into the invariant $b-3*d-l$.
How is it done?
If the linear combination should be an invariant then it has to hold for all changes of adding/removing a dark as well as a light tetromino. This gives two linear equations as follows:
Adding a dark tetromino: $A*d+B*b+C*w+D*l = A*(d+1)+B*(b+3)+C*(w+1)+D*l$ Adding a white tetromino: $A*d+B*b+C*w+D*l = A*d+B*(b+1)+C*(w+3)+D*(l+1)$
Now simplifying those equations yields:
$A+3B+C+0$ and $B+3C+D=0$
So you have a system of two linear equations in 4 variables. Solve this and you will see that the given invariant is one solution, given by: $A=-3$, $B=1$, $C=0$ and $D=-1$.
But of course there are other solutions (the system is under-determined) which would give other invariants, e.g. multiplying all coefficients by an integer or adding different solutions of the system. (Can you find and describe them all?) It simply seems the given invariant is one of the "fundamental" ones, where one variable ($C=0$) is chosen to be zero.