Problem
COM-B2-M04-P014 Two Colours and a Maximal Chain
In a row of \(n\) cells, each cell is coloured red or blue. One may choose several disjoint neighbouring pairs of different colours. The chosen set of pairs is maximal by inclusion. Prove that among the unchosen cells there are no two neighbouring cells of different colours.
If two neighbouring unchosen cells have different colours, their pair is still available.
Suppose two neighbouring unchosen cells \(i\) and \(i+1\) have different colours. Then the pair \((i,i+1)\) satisfies the condition and is disjoint from all chosen pairs, because both cells are unchosen.
It can be added to the current set of pairs while preserving all conditions. This contradicts maximality by inclusion. Therefore no such neighbouring unchosen cells exist.
A useful non-graph version of the maximal matching argument.