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?

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?

Share a problem which requires understanding of Parity.

#NumberTheory #KeyTechniques #Math

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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$ .

Patrick Corn - 7 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.)

Anqi Li - 7 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. □

Zhang Lulu - 7 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.

敬全钟 - 7 years, 6 months ago

I used the same method :)

A Former Brilliant Member - 7 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.

Marek Bernat - 7 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?

Arkan Megraoui - 7 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.

Michael Tong - 7 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.

Sharky Kesa - 7 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.

A Former Brilliant Member - 7 years, 6 months ago

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

Sharky Kesa - 7 years, 6 months ago

@Sharky Kesa – Yeah we had to do this in our math class last year.

William Cui - 7 years, 6 months ago

Math	Appears 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}$