Waste less time on Facebook — follow Brilliant.
×

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
3 years, 8 months ago

No vote yet
29 votes

Comments

Sort by:

Top Newest

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 · 3 years, 8 months ago

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.) Anqi Li · 3 years, 8 months ago

Log in to reply

@Anqi Li 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 · 3 years, 8 months ago

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. 敬全 钟 · 3 years, 8 months ago

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. Marek Bernat · 3 years, 8 months ago

Log in to reply

@敬全 钟 I used the same method :) Yash Talekar · 3 years, 8 months ago

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:

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

                     2. A chessboard has 64 squares.
Sharky Kesa · 3 years, 8 months ago

Log in to reply

@Sharky Kesa 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. Yash Talekar · 3 years, 8 months ago

Log in to reply

@Yash Talekar You got the answer. My reason was the same as yours. Sharky Kesa · 3 years, 8 months ago

Log in to reply

@Sharky Kesa Yeah we had to do this in our math class last year. William Cui · 3 years, 8 months ago

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? Arkan Megraoui · 3 years, 8 months ago

Log in to reply

@Arkan Megraoui 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 · 3 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...