perfe

INTUITIVEPROOFS

Example 1: (Chessboard Problem) Suppose you have a

chessboard (8 × 8 grid of squares) and a bunch of
dominoes (2 × 1 block of squares), so each domino can
perfectly cover two squares of the chessboard.

-> 64 (32light, 32 dark squares)

squares
-> domino take up 2x1(12,1D)
-> 32 dominos can fit

sol'nA sol'n 2
Definition: A PERFECT COVER of an mxn board with 2x1 dominoes is an arrangement of
those dominoes on the chessboard with no squares left uncovered and no dominoes stacked or left
hanging off the ends.

Proposition: There exists a perfect cover of an 8x8 chessboard.

I
Ideas:"there exists"suggests is
there
that
Proof
an element
or an example of it

following
Proof:Observe thatthe is a
perfectcover:

We have shown an example that

a
perfectcover existe,
1 roof.
the Halmo's tombstone
completing >

QED

Example 2: What if I cross out the bottom-left and top-left

squares, can we still perfectly cover the 62 remaining
squares?

less domino
->

-
exist
->
perfect
cover
 E
Example 3: What if I cross out just one square? Can this
be perfectly covered? NOx
63
3)
->
1,32D
-
parity

Proposition: If one crosses out the top-ledt square of an 8x8 chessboard, the remaining squares
cannot be covered perfectly by dominoes.
Idea:each 2
squares:1, ID
Proof domino covers

8
1 domino -> 2
squares (12, D)
2" +

4sg (22,2B)
I -> G
59 (32,3D) ...

even

Proof: Since each domino covers 2

squares and the
dominoses are
non-overlapping, if one place, our
K dominoes on the board, they will cover 2K
squares,
w/ is always an even number.
So a perfectcover can only cover an even

number of squares. Since the board has 63 squares,

which is an odd number, then itcannotbe perfectly

covered.
 Example 4: What if I take an 8 × 8 chessboard and cross
out the top-left and the bottom-right squares? Can this be
perfectly covered by dominoes?

-
Less
->

21, unequal 14 D

32D, 50L

-> every domino covers a

pair of LID
-> dominoes are arrangedalternatively

Proposition: If one crosses out the top-left and bottom-right square of an 8x8 chessboard, the
remaining squares cannot be covered perfectly by dominoes.

the chessboard has

Proof:Observe that 62
squares, and
since every domino covers square, theto
perfectcover
62
would require -=3! dominoes
2

Also observe thatevery domino covers exactly one light

square and one dark square, for example:
Thus when I
I lacing
31 non-overlapping dominoes on a
31 light squares
chessboard, they will ultimately cover

and 31 dark squares. Since what was crossed out

was two light squares, the squares in the board consist

of 30 lightand 32 dark squares. Therefore is
it

impossible for 31 dominates to cover these 62

squares

32B 3NL
1d:31 D 29L

30 D 282
2d:

:
OL
god: 2 D:

Basic Terms

1: A theorem is an important sentence or mathematical expression that has been proved.

2: A proposition is a result that is less important than a theorem. It has also been proved.

3: A lemma is typically a lesser sentence or mathematical expression that is proved before a

proposition or a theorem, and is used to prove the following proposition or theorem.

4: A corollary is a result that is proved after a proposition or a theorem, and which follows quickly
from the proposition or theorem. It is often a special case of the proposition or theorem.

5: All of the above are results that have been proved — a conjecture, though, has not. A
conjecture is a statement that someone guesses to be true, although they are not yet able to prove
or disprove it.
⑳ ⑧ ⑧ ⑳

n 6:31 regions
⑥ =

~ -
O

·
⑧
n5
=

n 1
=

n2
=

n 3
=
n =
4
16 regions
I region regions 4 regions 8 regions
 Definition (The pigeonhole principle). The principle has a simple form and a general form. Assume
k and n are positive integers.

Simple form: If n + 1 objects are placed into n boxes, then at least one box has at least two objects
in it.

General form: If kn + 1 objects are placed into n boxes, then at least one box has at least k + 1
objects in it.

4 5
2 3

Example 5: The population of the Philippines in 2021 is about 113.9 million people. How many
residents are guaranteed to have the same birthday according to the pigeonhole principle?

-8,000 311, 202. 183 = 3112

311802 x 366 + 1
113,899,933m
=

Proposition: Given any five numbers from the set {1, 2, 3, 4, 5, 6, 7, 8}, two of the chosen
numbers will add up to 9.
box the numbers 198, second box corresponl
Proof: let correspond to
one a

-
2;7,
↓ 3rd box
to34, and 4th to 4; 5. Note thatall these
box
pais
add up 9.
to

18 2!7 344 4 ;5

Given
any fire number from [1,1,3,4,5,6,7,8], upon placing these

number in the box to wie itpreponds, there be

must some box that
number in it to add up to a
has two
Assignment 1
1: If I remove two squares of different colors from an 8 × 8 chessboard, must the result have a
perfect cover?

2: If I remove four squares — two black, two white — from an 8 × 8 chessboard, must the result
have a perfect cover?

3: For every m and n, does there exist a perfect cover of the m × n chessboard by 2 × 1
dominoes? If not, for which m and n is there a perfect cover?

4: Given any collection of 10 points from inside the following square

(of side-length 3), there must be at least two of these points which
are of distance at most √2.

5: Given any 101 integers from {1, 2, 3, . . . , 200}, at least one of these numbers will divide
another.