Showing posts from January, 2018

Contrapositive, contradiction and construction: common proof methods

In this post we will talk about three different, all very common, ways of making proofs: contrapositive, contradiction and construction.

(jump to the contrapositive or to the contradiction)
Proofs by construction are probably the proofs that make more sense or are more intuitive in nature. When you prove something by construction, you explicitly build the thing that you described to exist, or give an explicit way of verifying what you described. This is very important because more often than not, mathematics can prove things like "an object X satisfying this and that property exists", but without providing means to find such object.

A good example of a proof by construction is the proof that every function $f: \mathbb{R}\to\mathbb{R}$ can be decomposed into a sum $f(x) = O(x) + E(x)$ where $O(x)$ is an odd function and $E(x)$ is an even function, i.e.

$$\begin{cases}O(-x) = -O(x)\\
E(-x) = E(x)\end{cases}\ \forall x \in \mathbb{R}$$

To prove this statement, we w…

Problem #05 - number me right

Today's problem has gotten me thinking about it several times for several reasons. In particular, the first time I came across it I was pretty sure I knew the answer but didn't really know how to formalize a proof. It was only a couple of years later, when I remembered the problem for no reason at all, that I was able to answer it completely.

Problem statement: imagine you have an infinite table with a checkerboard pattern. In the bottom leftmost corner you put a $0$. For every other cell, you insert the smallest non-negative integer that hasn't been used neither in the same row, to the left of the cell, nor in the same column, below it. So, for example, the first row will have the numbers $0, 1, 2, 3, \cdots $. What is the number that appears in the $1997$th row, $2018$th column?

The key is in understanding that the $1997$th row and the $2018$th column have nothing special. Hint 1
Write down a small board and fill it in following the rule of the problem statement. Look for…