Laserpants's Changamoto

If $a$ and $b$ are two non-negative integers such that $a + b = 5$, which of the following statements are then always true?

Answer:

Both statements are true.

First statement

If $a = b$, then $a + a = 2a = 5$, which means that $a = 2.5$. This is impossible, since $a$ was assumed to be an integer.

Second statement

By contradiction

Let's assume that $a \le 2$ and $b \le 2.$ But then $a + b \le 4.$ So (by De Morgan’s laws) therefore either $a > 2$ or $b > 2$.

Logic proof

If it is not the case that $a > 2$, then $a$ must be strictly less than $3$. So,

$\lnot(a > 2) \equiv a < 3 \quad$ and $\quad a < 3 \implies 5 - a > 5 - 3 = 2$.

Now, $a + b = 5 \implies b = 5 - a$, so $\lnot(a > 2) \implies b > 2$. And this is all we need, since $\lnot P \implies Q$ is logically equivalent to $P \vee Q$, as the following truth table shows.

$P$	$Q$	$P \vee Q$	$\lnot P$	$\lnot P \implies Q$
$F$	$F$	$\bf{F}$	$T$	$\bf{F}$
$F$	$T$	$\bf{T}$	$T$	$\bf{T}$
$T$	$F$	$\bf{T}$	$F$	$\bf{T}$
$T$	$T$	$\bf{T}$	$F$	$\bf{T}$

Exhaustion

Although not the most elegant of solutions, simply considering all possible values of $a$ and $b$ also serves as a direct proof of both statements. Since $a$ and $b$ are non-negative, $0 \le a, b \le 5$.

$a$	$b$
$0$	$\bf{5}$
$1$	$\bf{4}$
$2$	$\bf{3}$
$\bf{3}$	$2$
$\bf{4}$	$1$
$\bf{5}$	$0$

Generalized proof by induction

The statement can be seen as an instance of the more general form, $$ \forall a, b, z \in \mathbb{Z}_{\ge 0} : a + b = 2z + 1 \implies a > z \vee b > z, $$

with $z = 2$. Since $b = 2z + 1 - a$, we can instead phrase this as $$ a > z \vee 2z + 1 - a > z. $$

The proof will then proceed by induction. Let $P(n)$ be the proposition that $n > z$ or $2z + 1 - n > z$. The base case $P(0)$ holds, since $2z + 1 - 0 > z$. It remains to show that $\forall k \in \mathbb{Z}_{\ge 0} : P(k) \implies P(k + 1)$. So, assuming (by the induction hypothesis) that either $k > z$ or $2z + 1 - k > z$ holds, then

if $k > z$, we have that $k + 1 > z + 1 > z$, or
otherwise $2z + 1 - k > z$, which means that $2z + 1 - (k + 1) = 2z - k \ge z$, and therefore either

$2z + 1 - (k + 1) > z$, or
$2z + 1 - (k + 1) = z$, implying that $k + 1 = 2z + 1 - z = z + 1 > z$,

in each case for which $P(k + 1)$ is true.

\(P\)	\(Q\)	\(P \vee Q\)	\(\lnot P\)	\(\lnot P \implies Q\)
\(F\)	\(F\)	\(\bf{F}\)	\(T\)	\(\bf{F}\)
\(F\)	\(T\)	\(\bf{T}\)	\(T\)	\(\bf{T}\)
\(T\)	\(F\)	\(\bf{T}\)	\(F\)	\(\bf{T}\)
\(T\)	\(T\)	\(\bf{T}\)	\(F\)	\(\bf{T}\)

\(a\)	\(b\)
\(0\)	\(\bf{5}\)
\(1\)	\(\bf{4}\)
\(2\)	\(\bf{3}\)
\(\bf{3}\)	\(2\)
\(\bf{4}\)	\(1\)
\(\bf{5}\)	\(0\)