MATC44H3 Chap.5 Colouring Proofs and Tiling Arguments
Colouring Proofs and Tiling Arguments
The idea of a colouring proof
A colouring proof partitions the squares of a board, or the elements of any set, into a few classes by colour, and shows that every allowed tile covers a fixed pattern of colours. If the board's colour counts cannot be produced by that pattern, no tiling exists.
The lecture's standard example removes two opposite corners of a chessboard: each domino covers one square of each colour, but the cut board has 30 of one colour and 32 of the other, so 31 dominoes cannot cover it.
Necessary but not sufficient
The same argument rules out tilings whenever both removed squares share a colour.
The reverse case, removing one square of each colour, always leaves a tileable board, a theorem of Gomory from 1973 that the lecture illustrates with a path through every square.
A balanced colour count never proves on its own that a tiling exists; a construction is needed for that.
Colourings for other tiles and mixed tilings
The practice set uses striped rows to show that the number of L-tetrominoes in a covering of a chessboard must be even, a recolouring with sparse dark squares for 2 by 2 and 1 by 4 tiles, and a five by five colouring for L-trominoes.
In each case the solution names a variable for each kind of tile, writes the total number of dark squares covered as an equation, and reads off a parity or sign contradiction. The first assignment asks for both a construction and a colouring proof for a tiling question.
What this chapter covers
- 01
Dominoes and the two-colour chessboard
- 02
Removing squares of the same and opposite colours
- 03
Fisher's count and Gomory's theorem
- 04
Colourings designed for longer tiles
- 05
Equations from colour counts
- 06
Constructions for the possible cases
Worked example · free
A 6 by 6 board with two corners removed
- 2Colour as a chessboard. Two corners on the same side of an even-length row have opposite colours.
- 1The cut board keeps 17 squares of each colour, so the colour count does not rule a tiling out.
- 2Construct one: tile the first row's four remaining squares with 2 dominoes and the other 5 rows with 15 horizontal dominoes.
Key terms
- Domino Tiling
- A domino tiling covers a board with non-overlapping 1 by 2 tiles so that every square is covered once.
- Mutilated Chessboard
- The mutilated chessboard is an 8 by 8 board with two opposite corners removed, which no domino tiling can cover.
- Tetromino
- A tetromino is a shape made of four equal squares joined edge to edge.
- Colour Count
- A colour count is the number of squares of each colour that a region or a tile covers.
- Parity Argument
- A parity argument shows an arrangement is impossible because it would make an odd quantity even or the reverse.
- Tromino
- A tromino is a shape made of three equal squares joined edge to edge.
Colouring Proofs and Tiling Arguments FAQ
Why does every domino cover one square of each colour?
A domino covers two squares that share an edge, and on a chessboard colouring two squares sharing an edge always have different colours. So whichever way a domino is placed, it covers exactly one dark square and one light square, and any domino tiling covers equal numbers of each colour.
If the colours balance, does a tiling exist?
Not necessarily. Balance is a necessary condition, not a sufficient one. For a standard chessboard with one square of each colour removed a tiling always exists, by Gomory's theorem, but for other shapes and tiles you must construct a tiling explicitly before claiming one exists.
How do I choose a colouring for tiles longer than a domino?
Look for a property shared by every placement of the tile. For a straight tile of length four, colouring by the remainder of row plus column modulo four makes each placement cover one square of each colour. For L-shaped tiles, striped rows make some tiles cover an odd number of dark squares, which leads to a parity equation.
What should a full answer to a tiling question contain?
Every location or number that works needs a construction, an explicit tiling a reader can check, and every one that fails needs an impossibility argument, usually a colouring with the colour counts stated. Questions on the first assignment and in the practice set expect both parts, so give each one separately.
Exam move
Redraw the mutilated chessboard argument from memory, then invent a board with two squares removed that is tileable and give the tiling. Next, for straight tiles of length three, design a colouring modulo three and test it on a 6 by 6 board. Write every argument with the colour counts stated explicitly.
Working through Colouring Proofs and Tiling Arguments in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Colouring Proofs and Tiling Arguments question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
