Intuitive Proofs — Integrated Mathematics

Notes on Jay Cummings, Proofs: A Long-Form Mathematics Textbook.

Definition 1.1 (Definition 1.1). A perfect cover of an board with dominoes is an arrangement of those dominoes on the chessboard with no squares left uncovered, and no dominoes stacked or left hanging off the end.

Proposition 1.2 (Proposition 1.2). There exists a perfect cover of an chessboard by flat dominoes.

Remark (Proof idea). The proposition is asserting that “there exists” a perfect cover. To say “there exists” something means there is at least one example of it. Therefore, any proposition like this can be proven by simply presenting an example which satisfies the statement.

Proposition 1.3 (Proposition 1.3). If one crosses out the top-left square of an chessboard, the remaining board will not be perfectly covered by dominoes.

Proof idea proof. Observe:

Remark (Proof idea). Each domino covers squares, so the number of squares covered by whole dominoes must also be even. Thus it is impossible for whole dominoes to cover an odd number of squares (the dominoes covering a number of the form , where , and the odd number of squares being of the form ).

Proof. Since each domino covers squares and the dominoes are non-overlapping, if one places our dominoes on the board then they will cover squares, which is always an even number. Therefore a perfect cover can only cover an even number of squares. Notice, though, that the board has remaining squares, which is an odd number. Thus, it cannot be perfectly covered. ∎

Notice that the proof idea is correct but not as formal and rigid as the real proof.

“It is logic we prove. It is intuition we discover.” (Henri Poincaré)

Proposition 1.4 (Proposition 1.4). If one crosses out the top-left and bottom-right squares of an chessboard, the remaining squares cannot be perfectly covered by dominoes.

Proof. Observe that the chessboard has remaining squares, and since every domino covers squares, dominoes are required. Also observe that every domino on the chessboard covers exactly one black square and one white square. Thus dominoes on the chessboard will collectively cover white and black squares. Next observe that the crossed-out squares are both white, giving us white squares and black squares. Thus, it is impossible to have dominoes cover these squares. ∎

Note. A proof should be 100% complete without images/pictures, but you may use some only to illustrate your words.

Question 1.5 (Q1). If I remove two squares of different colors from an chessboard, must the result have a perfect cover?

Proof. If we have an chessboard we have white and black squares. Remove one of each and we have of each. So we have dominoes, , which require precisely one black and one white square each. Notice that the number of dominoes needed equals the count of black and white squares individually. Then to place one domino means black and white. We continue this process times, resulting in black, white, and no dominoes or partial dominoes left; thus giving us a perfect cover. ∎

Remark (Correction). Equal colour counts are necessary for a perfect cover and do not suffice: the argument never shows that each domino can be placed on two adjacent uncovered squares. The answer to Q1 is still yes. To prove it, join the squares into one closed path (up the first column, then back and forth across the other seven columns one row at a time from the top down, ending next to the start), so that the squares along the path alternate in colour. Removing one black and one white square cuts the path into two pieces, each of even length because the removed squares have different colours, and each piece is covered by dominoes laid on consecutive pairs of squares.

Question 1.6 (Q2). If I remove four squares (two black, two white) from an chessboard, must the result have a perfect cover?

Remark (Proof idea). Notice this follows a similar format as Q1. So then if I have dominoes for black and white squares, the subtraction remains the same.

Remark (Correction). Equal colour counts do not guarantee a perfect cover, and the answer to Q2 is no. Label the squares as on a standard chessboard ( is a corner and is black) and remove and (both white) together with and (both black). Then the corner square has no uncovered neighbour, so no domino can cover it, and the same holds for .

Question 1.7 (Q3). For every pair of positive integers , does there exist a perfect cover of the chessboard by dominoes? If not, for which and is there a perfect cover?

Remark (Proof idea). Let’s think about this. We know that if and is an integer of the form , i.e. that integer is odd, then there exists no perfect cover for an chessboard by dominoes. (Perhaps this has to do with the fact that dominoes always cover times the number of dominoes in terms of square space, that is to say they are in the form , where .) Then perhaps the only form of where there is a perfect cover is the form , where is an integer of the form (i.e. even). This is because the product must be of the form and the dominoes cover a number of the form , where is the number of dominoes.

Question 1.8 (CQ1). How many ways can one cover an chessboard with dominoes?

Remark (Proof idea). My guess is that there are ways to cover a chessboard with dominoes if is even. (Disproven by the chessboard.) Notice some cases: has way, has ways, has ways.

Remark (Correction). The board has domino tilings, not , so the pattern does not continue (the numbers of tilings of the board for are ). The guess would give for the board, so it is indeed disproven.

Question 1.9 (CQ2). What if I change the domino to be another shape and ask all the previous questions again?

Question 1.10 (CQ3). Can we generalize these questions/results to higher dimensions?

Naming results

A theorem is an important result (a mathematical statement that is true) that has been proved.
A proposition is a result that is less important than a theorem. It has also been proved.
A lemma is a typically small result that is proved before a proposition or theorem, and is used to prove the following proposition or theorem.
A corollary is a result that is proved after a proposition or theorem, which follows quickly from the proposition or theorem. It is often a special case of the proposition or theorem.
A conjecture is a statement that someone guesses to be true, although they are not yet able to prove or disprove it.

1 Intuitive Proofs

Naming results