Parity 2

This is a continuation of Parity. We further explore the idea of parity and its various uses. Apart from simply determining if a number is odd or even, parity can also be used as a counting argument.

Worked Examples

1. The opposite corners are removed from a 20×20 20 \times 20 chessboard. Can the resulting shape be covered by 199 rectangles of size 2×1 2 \times 1 ? Each rectangle must be placed so as to cover two adjacent squares of the board.

Solution: We can colour the squares of the chessboard black and white in an alternating pattern. This will give 200 squares of each colour. The two opposite corners will have the same colour, so when they are removed, there will be 198 squares of one colour remaining and 200 squares of the other. Each rectangle covers exactly one black square and one white square, so 199 rectangles cannot cover all 200 squares of the same colour.


2. In an 8×8 8 \times 8 table, half of the entries are 1 1 and the remaining entries are 1 -1 . You are allowed to multiply any number of rows and columns by 1 -1 . Is it possible to get 63 of the entries to be 1 1 and the other entry 1 -1 by this process?

Solution: Consider what happens when we multiply a row by 1 -1 . Suppose that k k of the entries in the row were 1 1 and the other 8k 8-k entries were 1 -1 . After we perform the multiplication, 8k 8-k of the entries will be 1 1 and k k of the entries will be 1 -1 . This represents a change of (8k)k=82k (8-k) - k = 8-2k to the total number of entries which are 1 1 . Since 82k 8 - 2k is always even when k k is an integer, the number of entries which are 1 1 will always have the same parity. Since the parity was even to begin with, it can never become odd by a sequence of these multiplications. Therefore, it is not possible to do get 63 of the entries to be 1 by this process.


3. A move for a knight on a chessboard consists of the knight going 2 squares in one direction and 1 square in a perpendicular direction. Show that if a knight is on a square in a 5×5 5 \times 5 chessboard, it cannot visit every other square exactly once before returning to its starting square.

Solution: Proof by contradiction. Once again, we can colour the squares of the chessboard black and white in an alternating pattern. Without loss of generality, the corner squares are all black. We can count that there are 13 black squares and 12 white squares.

Suppose that such a loop exists for the knight. Note that the sequence of squares in the knight's moves must alternate in color, e.g., BWBWBW B-W-B-W-B-W- \cdots . This implies that there must be an equal number of Black and White squares, since the knight returned to the starting square. This gives a contradiction.


4. Show that 2 \sqrt{2} is irrational by assuming that 2=ab \sqrt{2} = \frac{a}{b} and arriving at a contradiction involving parity.

Solution: Proof by contradiction. Suppose that 2 \sqrt{2} is rational. Then 2=ab \sqrt{2} = \frac {a}{b} , where a a and b b are coprime positive integers. Clearing denominators and squaring, we get 2b2=a2 2 b^2 = a^2 . Since the LHS is even, so is the RHS, thus a a is even. Let a=2a1 a = 2 a_1 . Then, we obtain

2b2=(2a1)22b2=4a12b2=2a12. 2b^2 = (2a_1)^2 \Rightarrow 2b^2 = 4a_1 ^2 \Rightarrow b^2 = 2a_1 ^2.

Now, since the RHS is even, so it the LHS, thus b b is even. As such, a a and b b are both even, contradicting the assumption that they are coprime.

Note by Calvin Lin
7 years, 3 months ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 2

paragraph 1

paragraph 2

[example link]( 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

In #4 why can you assume a and b are coprime?

Nathan Ramesh - 7 years, 1 month ago

Log in to reply

If they are not, you can divide both by their GCD.

Calvin Lin Staff - 7 years, 1 month ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...