Pigeonhole Principle If $n+1$ objects are distributed into $n$ boxes, then at least one box contains two or more of the objects. Proof For each $i\in \set{1, …, n}$, let $a_i = $ number of objects in box $i$. Then, $a_1 + … + a_n = n+1$ Let $a_j = \text{max } a_i$. Then, \begin{align*} n+1 &\leq n\cdot a_j \\ \frac{n+1}{n} &\leq a_j \\ 1 < \frac{n+1}{n} &\leq a_j\\ 1 &< a_j \end{align*} Note that this conclusion doesn’t hole if you have $n$ objects or less. ...

Binomial Coefficient and Binomial Identity Pascal’s Triangle \begin{matrix} {0 \choose 0}\\ {1 \choose 0} & {1 \choose 1}\\ {2 \choose 0} & {2 \choose 1} & {2 \choose 2}\\ {3 \choose 0} & {3 \choose 1} & {3 \choose 2} & {3 \choose 3}\\ {4 \choose 0} & {4 \choose 1} & {4 \choose 2} & {4 \choose 3} & {4 \choose 4}\\ .\\ .\\ . \end{matrix} Pascal’s Formula For all integers $n$ and $k$ with $1 \leq k \leq n - 1$, we have: $$ {n \choose k} = {{n-1} \choose k} + {{n-1} \choose {k-1}} $$ ...

Definition A combination of a set $S$ is a term usually used to denote an unordered selection of the element of $S$. It is simply a selection of a subset of $S$. $r$-combination = $r$-subset. $n\choose r$ is the number of $r$-subset in the set of size $n$. Theorem For $0 \leq r \leq n$, we have: $$ P(n, r) = r! {n \choose r} \text{ and } {n \choose r} = \frac{n!}{r!(n-r)!} $$ Proof ...

Deterministic Finite Automaition Definition: $(Q, s, A, \delta)$ $Q$: A set of all the possible state. $s \in Q$ : starting state. The state to start the machine. $A \subseteq Q$: The set of states we accept. Return “good” when we end there. $\delta$: A function $Q \times \Sigma \rightarrow Q$. The set of all transition functions. There is an interesting DFA design question. The question is as follows: Given a bit-string (a string that contains only 0s and 1s), design a DFA that accepts the string if and only if the number represented by the string is divisible by 5. ...

Gomory’s Theorem If you move two cells of a $8 \times 8$ chessboard of opposite colors, the remaining cells can be fully domino tiled. Proof Draw a closed path that passes through every square exactly once. (Draw a big C and then draw back and forth horizontally) Choose the two cells to be removed, and the closed path we have will be sperated into two paths. If we lable the close path we chose in the beginning from 1 to 64 in the order we drew it, white cells have odd numbers, and black cells have even numbers (or reversed). ...

Consider a $n \times m$ chessboard… $$ \int{f(x)dx} $$ Since $94 = 4 + 5x$ for some $x \in \mathbb{N}$, my claim is that the first player wins when it chooses $4$ in the beginning. Then, whenever the second player choose $a, x \in\set{1, 2, 3, 4}$, the first player just add it to 5. So choose $5-a$. By doing this, the first player always reaches $10x + 9$ or $10x + 4$ for $x \in \mathbb{N}$. Since $94$ is included, the first player must win. ...

I have had a wonderful summer as I have been able to take Math 417 with Professor Chales Rezk. He is a very very good teacher and I have learnt a lot from him. Thanks! These are the notes I have taken during the course. It includes the greate Theorems, Lemmas and Propositions that we have learnt in the course. Previous Next     / [pdf] View the PDF file here.

The four basic counting principle Suppose that a set $S$ is partitioned into pairwise disjoint parts $S_1, S_2, …, S_n$. Addition principle: $$ |S| = |S_1| + |S_2| + … + |S_m| $$ Ex: Path counting: In a $3 \times 3$ grid, if you can move 1 step upward or 1 step to the right. How many ways do we have to move from bottom-left to top-right corner? The idea is to break this problem into smaller problems. Addition principle guarrantees that we can add the numbers together. ...