Program: English — B10 · Bahasa Indonesia — B10 · Mathematics Program home · Beranda Program Matematika · Original source — Original author’s reader — Discrete Mathematics: An Open Introduction, 4th edition · Open related page · Open related page Mathematics program — English Program — Bahasa Indonesia Original author’s website ↗ Book contents Original English by Oscar Levin. This unofficial mirror includes local math and search assets and frozen exercise statements. Remote computation, live checking and external websites still need internet access. Use the original website for its live services.
Skip to main content
Contents Index Embed Dark Mode Prev Up Next \(\usepackage{cancel}
\def\d{\displaystyle}
\def\N{\mathbb N}
\def\B{\mathbf B}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R}
\def\C{\mathbb C}
\def\U{\mathcal U}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\X{\mathcal{X}}
\def\Y{\mathcal{Y}}
\def\pow{\mathcal P}
\def\inv{^{-1}}
\def\st{:}
\def\iff{\leftrightarrow}
\def\Iff{\Leftrightarrow}
\def\imp{\rightarrow}
\def\Imp{\Rightarrow}
\def\isom{\cong}
\def\bar{\overline}
\def\card#1{\left| #1 \right|}
\def\twoline#1#2{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\def\mchoose#1#2{
\left.\mathchoice
{\left(\kern-0.48em\binom{#1}{#2}\kern-0.48em\right)}
{\big(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\big)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
{\left(\kern-0.30em\binom{\smash{#1}}{\smash{#2}}\kern-0.30em\right)}
\right.}
\def\o{\circ}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Worksheet Preview Activity
If
\(a b\) is an even number, then
\(a\) or
\(b\) is even.
Which of the proofs below appear to be valid proofs of this statement? Note: You can assume all the algebra below is correct (because it is).
1.
Suppose \(a\) and \(b\) are odd. That is, \(a=2k+1\) and \(b=2m+1\) for some integers \(k\) and \(m\text{.}\) Then
\begin{align*}
ab \amp =(2k+1)(2m+1)\\
\amp =4km+2k+2m+1\\
\amp =2(2km+k+m)+1\text{.}
\end{align*}
2.
Assume that \(a\) or \(b\) is even -- say it is \(a\) (the case where \(b\) is even will be identical). That is, \(a=2k\) for some integer \(k\text{.}\) Then
\begin{align*}
ab \amp =(2k)b\\
\amp =2(kb)\text{.}
\end{align*}
3.
Suppose that \(ab\) is even but \(a\) and \(b\) are both odd. Namely, \(ab = 2n\text{,}\) \(a=2k+1\) and \(b=2j+1\) for some integers \(n\text{,}\) \(k\text{,}\) and \(j\text{.}\) Then
\begin{align*}
2n \amp =(2k+1)(2j+1)\\
2n \amp =4kj+2k+2j+1\\
n \amp = 2kj+k+j+\frac{1}{2}\text{.}
\end{align*}
But since
\(2kj+k+j\) is an integer, this says that the integer
\(n\) is equal to a non-integer, which is impossible.
4.
Let \(ab\) be an even number, say \(ab=2n\text{,}\) and \(a\) be an odd number, say \(a=2k+1\text{.}\)
\begin{align*}
ab \amp =(2k+1)b\\
2n \amp =2kb+b\\
2n-2kb\amp =b\\
2(n-kb)\amp =b\text{.}
\end{align*}
Therefore
\(b\) must be even.
5.
Which of the proofs above are valid proofs of the statement?
Source-provided solution — read without completing the interaction
Correct.
Incorrect. This is a valid proof, but not of the statement given. It is proving something else.
Correct.
Correct.
Mathematics program — English Program — Bahasa Indonesia Original author’s website ↗ Book contents Program: English — B10 · Bahasa Indonesia — B10 · Mathematics Program home · Beranda Program Matematika · Original source — Original author’s reader — Discrete Mathematics: An Open Introduction, 4th edition · Open related page · Open related page 
