# Parity

This week, we learn about Parity and Applications of Parity. Parity is a useful technique for determining whether two quantities can be equal by comparing their parity.

How would you use Parity to solve the following?

1. Consider an $$n\times n$$ checkboard with all 4 corners removed. For what values of $$n$$ can this board be completely covered by non-overlapping $$1 \times 2$$ dominos?

2. Share a problem which requires understanding of Parity.

Note by Calvin Lin
4 years, 6 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

The most beautiful example of this phenomenon is Zagier's famous proof of Fermat's two-squares theorem, which I cannot recommend highly enough.

http://en.wikipedia.org/wiki/ProofsofFermat%27stheoremonsumsoftwosquares#Zagier.27s.22one-sentenceproof.22

The well-known "100 lockers" problem can be viewed as an elementary application of this principle, since the number of factors of an integer $$n$$ has the same parity as the number of fixed points of the involution $$d \mapsto n/d$$.

- 4 years, 6 months ago

Problem: An $$n×n$$ matrix (square array) whose entries come from the set $$S = {1,2, . . . ,2n−1}$$, is called a golden matrix if, for each $$i = 1,2, . . . , n,$$ the $$i$$th row and $$i$$th column together contain all elements of $$S$$. Show that there is no golden matrix for $$n = 2013$$. (Adapted from IMO)

EDIT: For those ambitious, using your conjecture from above, show that there are infinitely many golden matrices. (Note: I have $$2$$ approaches, one of which uses the more obvious latin square construction by essentially "building" the golden matrices from smaller cases. A hint for the second approach would be to think of partitions.)

- 4 years, 6 months ago

Ok, I'll give this a try: Well, we will show that $$n$$ must be even. Because we need to denote some pretty weird things, let's start with the definitions. Let $$CR_i$$ denote the all the elements in the $$i$$th row and $$i$$th column, excluding the diagonal element. Also, because golden matrix is pretty long, denote a $$n \times n$$ golden matrix by $$G$$. So, we take an element that is not on the diagonal, and say it is $$n$$ and $$n = (j,k)$$. Clearly we can find such an $$n$$ since there is a total of $$2n-1$$ elements and only a max of $$n$$ elements on the diagonal. Then we have $$n \in CR_j, CR_k$$. Now it is clear that $$n$$ partitions $$G$$ into pairs $$\rightarrow$$ $$n$$ must be even. Since $$2013$$ is trivially odd, we are done. □

- 4 years, 6 months ago

$$n$$ must be an even number. It is told that the 4 corners were removed, so, from here, we can make the situation easier by removing the sides. Now we get a square. In order to place all the $$1 \times 2$$ dominoes into the new square, we need even number as the side. This implies that when we join back those rectangles that we removed just now, including removed corners, we get even number as a side.

- 4 years, 6 months ago

I don't quite get your solution. Here's mine: when $$n$$ is even there is an obvious tiling where all dominoes point into same direction. When $$n$$ is odd, the number of squares to be covered is $$n^2 - 4$$ which is also odd. But because every domino covers two squares, altogether they have to cover even number of squares, so $$n$$ odd can't work.

- 4 years, 6 months ago

I used the same method :)

- 4 years, 6 months ago

This is a relatively easy problem that I read.

There is a chessboard with two opposite corners removed. Is it possible to cover up the chessboard entirely with dominoes and why is/isn't it?

Notes:

                     1. The domino squares are the same size as the chessboard squares.

2. A chessboard has 64 squares.


- 4 years, 6 months ago

No, a domino covers exactly one black square and one white square. Two opposite corners are of the same colour. This means the dominoes must cover 64 squares of one colour and 62 squares of another colour which is impossible.

- 4 years, 6 months ago

You got the answer. My reason was the same as yours.

- 4 years, 6 months ago

Yeah we had to do this in our math class last year.

- 4 years, 6 months ago

Problem:

In the forest, there are chameleons of 3 colors: blue, red and green. When two chameleons of a different color meet, they will change into the third color. For example, if a red and blue chameleon meet each other, they will both turn green. If there are currently 12 blue chameleons, 34 red chameleons and 56 green chameleons, would it be possible for all the chameleons in the forest to turn green?

- 4 years, 6 months ago

No. We need to create an equal number of blue/red chameleons, and then have those chameleons meet each other and then they all turn green. The possible moves are

$$B + R \rightarrow 2G$$ -- which is unproductive until the end step

$$R + G \rightarrow 2B$$ or $$B + G \rightarrow 2R$$. In both cases, the difference in blue/red chameleons changes by three. Since the number of blue and red chameleons given initially does not differ by a multiple of three, this is an impossibility.

- 4 years, 6 months ago