[Brilliant Blog] Parity II

The above image refers to the problem described in Test Yourself question number 6

[This post is targeted at a Level 4 student. You should be familiar with Parity.]

We will further explore the idea of parity, and its various uses. Apart from simply determining if a number is odd or even, parity can be used as a simple counting argument in many cases. In Parity Test Yourself 1, we gave a question where Mary had an even number of sheep at the start, and an odd number of sheep at the end of the day. This implies that she had a different amount of sheep, and hence didn't do her job properly. 

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 will cover a black square and a white square, so 199 rectangles cannot cover all 200 squares of the same colour.
2. An $8 \times 8$ table has half of its entries $1$ and the other half $-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: It is not possible to do this. 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 do 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.
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 each 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. We see that it must jump from a black square to a white square, so the squares that it lands on must alternate $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. Hence, we have 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 get that $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.

Test Yourself

1. 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. Consider the $5 \times 5$ chessboard. Is it possible for the knight to visit each square exactly once (without returning to its starting square)? If so, which squares can the knight start on to make this possible?

2. 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. For what values of $n$ can a knight visit each square of a $4 \times n$ chessboard without going over the same square twice? It does not need to return to its starting square.

3. 2013 integers are arranged around a circle. Show that some consecutive pair has an even sum.

4. Show that $ax^2 + bx + c = 0$ has no solutions in rational numbers when $a,b,c$ are all odd.

5. The numbers $1,1,2,3,5,8,13,21,34,55$ are equally spaced clockwise around a circle. You are allowed to pick a pair of adjacent numbers and add 1 to each number. Is it possible that after a sequence of these additions that all of the numbers are the same?

6. (2007 CMO) What is the maximum number of non-overlapping $2 \times 1$ dominoes that can be placed on a $8 \times 9$ checkerboard if six of them are placed as shown? Each domino must be placed horizontally or vertically so as to cover two adjacent squares of the board.

7. (*) On a 8 by 8 chessboard, we write the numbers 1 on black squares and -1 on white squares. In each step, we choose three consecutive squares in the same row of column, and multiply each of their entries by -1. Is it possible to eventually get all 1's on the board?