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.

No vote yet

29 votes

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestThe 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/Proofs

ofFermat%27stheoremonsumsoftwosquares#Zagier.27s.22one-sentenceproof.22The 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 \).

Log in to reply

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.)Log in to reply

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

noton 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. □Log in to reply

\(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.

Log in to reply

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.

Log in to reply

I used the same method :)

Log in to reply

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:

Log in to reply

No, a domino covers exactly

oneblack square andonewhite 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.Log in to reply

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

Log in to reply

Log in to reply

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?

Log in to reply

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.

Log in to reply