227 lines
6.6 KiB
TeX
227 lines
6.6 KiB
TeX
|
\documentclass[12pt]{article}
|
||
|
|
\usepackage{ntnu}
|
||
|
|
\usepackage{ntnu-math}
|
||
|
|
|
||
|
|
\author{Øystein Tveit}
|
||
|
|
\title{MA0301 Exercise 9}
|
||
|
|
|
||
|
|
\usepackage{amsthm}
|
||
|
|
\usepackage{mathabx}
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
\ntnuTitle{}
|
||
|
|
\break{}
|
||
|
|
|
||
|
|
\begin{excs}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
\begin{align*}
|
||
|
|
p \rightarrow (q \vee r) &\equiv \neg p \vee (q \vee r) \\
|
||
|
|
&\equiv \neg p \vee q \vee r \\
|
||
|
|
&\equiv \neg (p \vee \neg q) \vee r \\
|
||
|
|
&\equiv (p \vee \neg q) \rightarrow r \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
R does not define a partial orderering, because it is not transitive.
|
||
|
|
|
||
|
|
$aRb$ and $bRc$, however $\neg aRc$
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
\begin{subexcs}
|
||
|
|
\subexc{}
|
||
|
|
\begin{gather*}
|
||
|
|
xyz + xy\overline{z}+\overline{x}y \\
|
||
|
|
xy + \overline{x}y \\
|
||
|
|
y
|
||
|
|
\end{gather*}
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
\begin{gather*}
|
||
|
|
y + \overline{x}z + x\overline{y} \\
|
||
|
|
y + \overline{x}z + x \\
|
||
|
|
y + z + x \\
|
||
|
|
x + y + z
|
||
|
|
\end{gather*}
|
||
|
|
|
||
|
|
\end{subexcs}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
Step 1:
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
\sum^1_{n=1}\frac{1}{(2n-1)(2n+1)} &= \frac{1}{2\cdot1 + 1} \\
|
||
|
|
\frac{1}{(2\cdot1-1)(2\cdot1+1)} &= \frac{1}{3} \\
|
||
|
|
\frac{1}{(1)(3)} &= \frac{1}{3} \\
|
||
|
|
\frac{1}{3} &= \frac{1}{3} \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
Step 2:
|
||
|
|
|
||
|
|
Assume
|
||
|
|
|
||
|
|
\[ \sum^k_{n=1} \frac{1}{(2n-1)(2n+1)} = \frac{k}{2k+1} \]
|
||
|
|
|
||
|
|
then
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
\sum^{k+1}_{n=1} \frac{1}{(2n-1)(2n+1)} &= \frac{k}{2k+1} \\[2ex]
|
||
|
|
&= \frac{1}{(2\cdot1 - 1)(2\cdot1+1)} + \frac{1}{(2\cdot2 - 1)(2\cdot2+1)} + \ldots \\[2ex]
|
||
|
|
&\qquad + \frac{1}{(2\cdot k - 1)(2\cdot k+1)} + \frac{1}{(2\cdot(k+1) - 1)(2\cdot(k+1)+1)} \\[2ex]
|
||
|
|
&= \frac{k}{2k+1} + \frac{1}{(2\cdot(k+1) - 1)(2\cdot(k+1)+1)} \\[2ex]
|
||
|
|
&= \frac{k}{2k+1} + \frac{1}{(2k+1)(2k+3)} \\[2ex]
|
||
|
|
&= \frac{k(2k1)(2k+3) + (2k+1)}{(2k+1)^2(2k+3)} \\[2ex]
|
||
|
|
&= \frac{k(2k+3) + 1}{(2k+1)(2k+3)} \\[2ex]
|
||
|
|
&= \frac{2k^2+3k + 1}{(2k+1)(2k+3)} \\[2ex]
|
||
|
|
&= \frac{(2k+1)(k+1)}{(2k+1)(2k+3)} \\[2ex]
|
||
|
|
&= \frac{(k+1)}{(2k+3)} \\[2ex]
|
||
|
|
&= \frac{k+1}{2(k+1)+1}
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
\textbf{Injective:}
|
||
|
|
|
||
|
|
Suppose $a,b \in \R$
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
f(a) &= f(b) \\
|
||
|
|
2a-3 &= 2b-3 \\
|
||
|
|
2a &= 2b \\
|
||
|
|
a &= b \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
thus
|
||
|
|
|
||
|
|
\[ f(a) = f(b) \Leftrightarrow a = b \]
|
||
|
|
|
||
|
|
which means that $f$ is injective \\
|
||
|
|
|
||
|
|
\textbf{Surjective:}
|
||
|
|
|
||
|
|
Suppose $a \in \R$
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
a &= 2x-3 \\
|
||
|
|
x &= \frac{a+3}{2} \\
|
||
|
|
a &\in \R
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
therefore $f$ is surjective \\
|
||
|
|
|
||
|
|
\textbf{Inverse:}
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
y &= 2x-3 \\[2ex]
|
||
|
|
x &= \frac{y+3}{2} \\[2ex]
|
||
|
|
f^{-1}(y) &= \frac{y+3}{2}
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
\begin{gather*}
|
||
|
|
(\overline{X \cap Y \cap Z}) \\
|
||
|
|
\{ x \mid x \in \overline{X \cap Y \cap Z} \} \\
|
||
|
|
\{ x \mid x \notin X \cap Y \cap Z \} \\
|
||
|
|
\{ x \mid x \notin X \wedge x \notin Y \wedge x \notin Z \} \\
|
||
|
|
\{ x \mid x \in \overline{X} \vee x \in \overline{Y} \vee x \in \overline{Z} \} \\
|
||
|
|
\{ x \mid x \in \overline{X} \cup \overline{Y} \cup \overline{Z} \} \\
|
||
|
|
\overline{X} \cup \overline{Y} \cup \overline{Z}
|
||
|
|
\end{gather*}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
Assuming 'dozen' is to be interpreted as 12
|
||
|
|
|
||
|
|
\begin{subexcs}
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
\[ \nPr{31}{12} = 67\ 596\ 957\ 267\ 840\ 000 \]
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
\[ 31^{12} = 787\ 662\ 783\ 788\ 549\ 761 \]
|
||
|
|
|
||
|
|
\end{subexcs}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
\begin{subexcs}
|
||
|
|
\subexc{}
|
||
|
|
If we imagine a row of numbers going from 1 to 40, we can rephrase the question as how many ways we can split
|
||
|
|
the numbers into $5$ chunks. Imagine a chunk as inserting $4$ delimiters like this:
|
||
|
|
|
||
|
|
\[ 1\ 2\ 3\ |\ 4\ 5\ 6\ 7\ |\ 8\ 9\ 10\ |\ 11\ \ldots\ 39\ |\ 40 \]
|
||
|
|
|
||
|
|
In this case, we split the amount of numbers so that $x_1 = 3, x_2 = 4, x_3 = 3, x_4 = 29, x_5 = 1$
|
||
|
|
|
||
|
|
By doing $\nCr{n}{r}$ where n is the number of numbers and delimiters, and r is the number of delimiters,
|
||
|
|
we will get all combinations of $x_1 + x_2 + x_3 + x_4 + x_5 = 40$A
|
||
|
|
|
||
|
|
In order to make it $x_1 + x_2 + x_3 + x_4 + x_5 \leq 40$, we will add a fifth delimiter, indicating the last block of unused numbers.
|
||
|
|
|
||
|
|
$x_1 + x_2 + x_3 + x_4 + x_5 < 40 \Rightarrow x_1 + x_2 + x_3 + x_4 + x_5 \leq 39$
|
||
|
|
|
||
|
|
This leaves us with $\nCr{39 + 5}{5} = 1086008$ different combinations.
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
In this case, we modify the problem by adjusting the inequality of $x_i$ like the following
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
x_1 + x_2 + x_3 + x_4 + x_5 &< 40 \qquad &&x_i \geq -3 \\
|
||
|
|
y_1 - 3 + y_2 - 3 + y_3 - 3 + y_4 - 3 + y_5 - 3 &< 40 &&(y_i - 3 = x) \\
|
||
|
|
y_1 + y_2 + y_3 + y_4 + y_5 &< 40 + 5 \cdot 3 \\
|
||
|
|
y_1 + y_2 + y_3 + y_4 + y_5 &< 55
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\[ (y_i - 3 = x) \Rightarrow (y_i - 3 \geq - 3) \Leftrightarrow (y_i \geq 0) \]
|
||
|
|
|
||
|
|
With this information, we use the same way of solving as in \textbf{a)}
|
||
|
|
|
||
|
|
\[\nCr{54 + 5}{5} = 5006386 \]
|
||
|
|
|
||
|
|
\end{subexcs}
|
||
|
|
|
||
|
|
\break{}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
This is a Venn diagram of the set containing the elements that satisfy $\overline{c}_1$, $\overline{c}_2$ and $\overline{c}_3$.
|
||
|
|
|
||
|
|
\includeDiagram[width=11cm, caption={$N(\overline{c}_2\overline{c}_3\overline{c}_4$)}]{diagrams/ex9_1.tex}
|
||
|
|
|
||
|
|
The following diagrams show the terms of the RHS.
|
||
|
|
|
||
|
|
\includeDiagram[width=11cm, caption={$N(c_1\overline{c}_2\overline{c}_3\overline{c}_4)$}]{diagrams/ex9_2.tex}
|
||
|
|
|
||
|
|
\includeDiagram[width=11cm, caption={$N(\overline{c_1}\overline{c}_2\overline{c}_3\overline{c}_4)$}]{diagrams/ex9_3.tex}
|
||
|
|
|
||
|
|
When we lay these two diagrams on top of each other, we can see that $N(c_1\overline{c}_2\overline{c}_3\overline{c}_4) + N(\overline{c}_1\overline{c}_2\overline{c}_3\overline{c}_4)$ is equal to $N(\overline{c}_2\overline{c}_3\overline{c}_4)$
|
||
|
|
|
||
|
|
\includeDiagram[width=11cm, caption={$N(c_1\overline{c}_2\overline{c}_3\overline{c}_4) + N(\overline{c}_1\overline{c}_2\overline{c}_3\overline{c}_4)$}]{diagrams/ex9_4.tex}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
let
|
||
|
|
|
||
|
|
$c_1 = 2 \mid n $ \\
|
||
|
|
$c_2 = 3 \mid n $ \\
|
||
|
|
$c_3 = 5 \mid n $ \\
|
||
|
|
$c_4 = 7 \mid n $
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
N(\overline{c}_1\overline{c}_2\overline{c}_3c_4) &= N(c_4) - \left( N(c_1c_7) + N(c_2c_7) + N(c_3c_7) \right) \\
|
||
|
|
&\quad + \left( N(c_1c_2c_4) + N(c_1c_3c_4) + N(c_2c_3c_4) \right) \\
|
||
|
|
&\quad - N(c_1c_2c_3c_4) \\[2ex]
|
||
|
|
&= \left\lfloor \frac{2000}{7} \right\rfloor - \left( \left\lfloor \frac{2000}{2 \cdot 7} \right\rfloor + \left\lfloor \frac{2000}{3 \cdot 7} \right\rfloor + \left\lfloor \frac{2000}{5 \cdot 7} \right\rfloor \right) \\[2ex]
|
||
|
|
&\quad + \left( \left\lfloor \frac{2000}{2 \cdot 3 \cdot 7} \right\rfloor + \left\lfloor \frac{2000}{2 \cdot 5 \cdot 7} \right\rfloor + \left\lfloor \frac{2000}{3 \cdot 5 \cdot 7} \right\rfloor \right) \\[2ex]
|
||
|
|
&\quad - \left\lfloor \frac{2000}{2 \cdot 3 \cdot 5 \cdot 7} \right\rfloor \\[2ex]
|
||
|
|
&= 76
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
|
||
|
|
\end{excs}
|
||
|
|
\end{document}
|