Parity 2

This is a continuation of Parity. We further explore the idea of parity and its various uses. Apart from simply determining if a number is odd or even, parity can also be used as a counting argument.

Worked Examples

1. The opposite corners are removed from a $20 \times 20$ chessboard. Can the resulting shape be covered by 199 rectangles of size $2 \times 1$? Each rectangle must be placed so as to cover two adjacent squares of the board.

Solution: We can colour the squares of the chessboard black and white in an alternating pattern. This will give 200 squares of each colour. The two opposite corners will have the same colour, so when they are removed, there will be 198 squares of one colour remaining and 200 squares of the other. Each rectangle covers exactly one black square and one white square, so 199 rectangles cannot cover all 200 squares of the same colour.

2. In an $8 \times 8$ table, half of the entries are $1$ and the remaining entries are $-1$. You are allowed to multiply any number of rows and columns by $-1$. Is it possible to get 63 of the entries to be $1$ and the other entry $-1$ by this process?

Solution: Consider what happens when we multiply a row by $-1$. Suppose that $k$ of the entries in the row were $1$ and the other $8-k$ entries were $-1$. After we perform the multiplication, $8-k$ of the entries will be $1$ and $k$ of the entries will be $-1$. This represents a change of $(8-k) - k = 8-2k$ to the total number of entries which are $1$. Since $8 - 2k$ is always even when $k$ is an integer, the number of entries which are $1$ will always have the same parity. Since the parity was even to begin with, it can never become odd by a sequence of these multiplications. Therefore, it is not possible to do get 63 of the entries to be 1 by this process.

3. A move for a knight on a chessboard consists of the knight going 2 squares in one direction and 1 square in a perpendicular direction. Show that if a knight is on a square in a $5 \times 5$ chessboard, it cannot visit every other square exactly once before returning to its starting square.

Solution: Proof by contradiction. Once again, we can colour the squares of the chessboard black and white in an alternating pattern. Without loss of generality, the corner squares are all black. We can count that there are 13 black squares and 12 white squares.

Suppose that such a loop exists for the knight. Note that the sequence of squares in the knight's moves must alternate in color, e.g., $B-W-B-W-B-W- \cdots$. This implies that there must be an equal number of Black and White squares, since the knight returned to the starting square. This gives a contradiction.

4. Show that $\sqrt{2}$ is irrational by assuming that $\sqrt{2} = \frac{a}{b}$ and arriving at a contradiction involving parity.

Solution: Proof by contradiction. Suppose that $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac {a}{b}$, where $a$ and $b$ are coprime positive integers. Clearing denominators and squaring, we get $2 b^2 = a^2$. Since the LHS is even, so is the RHS, thus $a$ is even. Let $a = 2 a_1$. Then, we obtain

$2b^2 = (2a_1)^2 \Rightarrow 2b^2 = 4a_1 ^2 \Rightarrow b^2 = 2a_1 ^2.$

Now, since the RHS is even, so it the LHS, thus $b$ is even. As such, $a$ and $b$ are both even, contradicting the assumption that they are coprime.