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.

## 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 \). – 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 agoLog in to reply

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. □ – Zhang Lulu · 3 years, 8 months agoLog 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

– Marek Bernat · 3 years, 8 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.Log in to reply

– Yash Talekar · 3 years, 8 months ago

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:

– Sharky Kesa · 3 years, 8 months agoLog in to reply

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. – Yash Talekar · 3 years, 8 months agoLog in to reply

– Sharky Kesa · 3 years, 8 months ago

You got the answer. My reason was the same as yours.Log in to reply

– William Cui · 3 years, 8 months ago

Yeah we had to do this in our math class last year.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

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