Curriculum

Method of Colouring

In brief

A colouring proof is a sort of invariant proof which can mainly be used to prove that something isn’t possible. The essence of invariant proofs is to strip the problem of any unnecessary details and only keep the information that best describes why something isn’t possible, making it very easy to follow invariant proofs.

Problem set (reference)

Class problems as we used them on this topic. For interactive practice with solutions and progress tracking, use Problems.cc when available.

0. Is it possible to cut a 8 × 8 square without two corner cells into 1 × 2 rectangles?
i) cells are on one side;
ii) cells are diagonally opposed.

‍
1. Is it possible to cut a 10 × 10 square into four-cell T-shaped figures?
2. Is it possible to make a 4 × 5 rectangle out of the five figures shown in the picture?

3. Can 8 × 8 board be tiled with 15 horizontal and 17 vertical rectangles of 1 × 2?
4. Can 8 × 8 board without a corner be tiled with 1 × 3 rectangles?