# Winter 2011 MATH 209: Discrete mathematicsBranko Ćurgus

Saturday, March 19, 2011

• Here is the histogram of the final grades.

Wednesday, March 16, 2011

• This is what I wrote during the final exam.

Thursday, March 10, 2011

• Do the exercises: 10, 12, 14-16, 20, 21, 23, 25, 30, 31, 37, 39.
• Here is the histogram of the grades on Exam 3 and the histogram of the averages of all three exams.

Tuesday, March 8, 2011

• Do the exercises: 1-13, 21, 22, 28, 29, 30.
• Some solutions from Section 4.3 as a Mathematica file are here and a pdf print-out of the same file is here.

Monday, March 7, 2011

• Do as many exercises as you can from 1-43.
• Some hints: 23: There are nine positions to place women after man are placed; this can be done in C(9,5) ways. 35: Place 1s first. Then there are 10 spots to place 0s between 1s. 37: Consider the complement of the set. 40: First answer how many ways are there to seat six people on a straight bench. Then count how many distinct seatings on a bench lead to the identical seating around a circular table. 43: Have in mind that all six runners can tie for gold and so on.

Tuesday, March 1, 2011

• Do the exercises: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.

Monday, February 28, 2011

• Do the exercises: As many as you can from 1-33. Also 36, 37 (the answer should involve a single formula involving n), 38-42, 47, 48, 49.

Friday, February 25, 2011

• Read the first part of Section 3.4, up to Recursively defined sets and structures.
• Do the exercises: 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15, 16, (if you have taken Math 204 do 18, 19)

Friday, February 18, 2011

• Do the exercises: 1, 2, 3, 5, 6, 7, 8, 9, 10, 15, 18, 19, 20, 24, 25, 26, 32, 36, 37, 51, 62,

Thursday, February 17, 2011

• Please note that the terms one-to-one correspondence and bijection are synonyms; see Definition 8 on page 101. I am disappointed that the author uses "one-to-one correspondence" in Section 3.2. I prefer bijection. Recall that a function is a bijection if it is both an injection and a surjection. I expect that you should be able to construct simple bijections between countable sets. For example between ${\mathbb Z}_+$ and ${\mathbb Z}$, between ${\mathbb Z}_+$ and odd integers, between ${\mathbb Z}_+$ and even integers, and similar.
• I am posting two Mathematica notebooks. In January 11 post I briefly explained how to use Mathematica. After downloading, you should evaluate the notebook and then experiment with the content.
• In the first notebook I give explicit formulas for a bijection between ${\mathbb Z}_+$ and ${\mathbb Z}_+\times{\mathbb Z}_+$ and its inverse. These formulas are illustrated with appropriate graphs.
• In the second notebook I give a formula for a bijection between ${\mathbb Z}_+$ and ${\mathbb Q}_+$. This formula is more complicated and I do not know the formula for the inverse. In this notebook I also solve Exercises 9, 10 and (a) and (b) of Exercise 32. In order to solve these exercises in Mathematica I needed explicit formulas for each of the sequences. Some of them were not easy to find.

Monday, February 14, 2011

• Read Section 3.2. Do the exercises 2, 4, 6, 9, 12, some of 13-18, 19, 20, 21, 23, 31, 32,
• Here is the histogram of the grades on Exam 2 and the histogram of the averages of Exam 1 and Exam 2.

Monday, February 7, 2011

• The proofs given in Examples 1, 3, 4, 7, and Theorem 1 might appear on exams.
• We will discuss the following conjectures: Goldbach's conjecture (Example 10), the Twin prime conjecture (Example 12), the 3x+1 conjecture (Example 13). You should be able to state each of these conjectures and illustrate it with examples.
• Do the exercises: 1,4, 5, 6, 22, 25, 32, 41, 42

Monday, January 31, 2011

• Read Section 1.7. Do the exercises 2, 3, 11, 14, 18, 19, 20
• Read Section 1.8. Do the exercises 1, 2, 4, 8, 9, 10, 11, 12, 13, 14, 19, 23, 25, 26, 27, 28, 29, 31, 44, 48, 49, (some from) 55-60, 65, 66
• Wikipedia's Function page:

Thursday, January 27, 2011

• Read Section 1.6 . Do the exercises 1 - 21, 24, 25, 27, 28.

Tuesday, January 25, 2011

• This is what I wrote during the exam.

Thursday, January 20, 2011

• The proposition $\sqrt{2}$ is irrational is proved by contradiction in Example 21 on page 66 in the textbook.

• In class I proved the implication If $x^2 = 2$, then $x$ is irrational.

• In fact, I proved the contrapositive: If $x$ is rational, then $x^2 \neq 2$.

The colored contrapositive is: $x$ is rational implies $x^2 \neq 2$.

• Here is a proof. In this proof we start with a green box. Each box that follows after this green box is a consequence of preceding green boxes. The point is that you need to understand why.

1. Assume that $x$ is rational.

2. Then:

There exist integers $a$ and $b$ such that $b \neq 0$, not both $a$ and $b$ are even, and $x =\dfrac{a}{b}$.

3. Next we consider two cases. Case I: $a$ is odd,     Case II: $a$ is even.

4. Consider Case I first. Assume that $a$ is odd.

5. From Line 4 we deduce $a^2$ is odd.

6. By Line 2 we have $b$ is an integer. This implies $2b^2$ is even.

7. From Lines 5 and 6 we deduce $a^2 \neq 2b^2$.

8. From Lines 2 and 7 we deduce $x^2 =\dfrac{a^2}{b^2}\neq 2$ . (This completes the proof for Case I.)

9. Now consider Case II. Assume that $a$ is even.

10. By Line 9 we have: There exists an integer $c$ such that $a = 2c$.

11. By Line 10 we have $2c^2$ is even.

12. From Lines 2 and 9 we deduce $b$ is odd.

13. From Line 12 we deduce $b^2$ is odd.

14. From Lines 11 and 13 we deduce $b^2 \neq 2c^2$.

15. From Lines 10 and 14 we deduce $2b^2 \neq 4c^2 = a^2$.

16. From Lines 2 and 15 we deduce $x^2 =\dfrac{a^2}{b^2}\neq 2$. (This completes the proof for Case II.)

Friday, January 14, 2011

• Read Section 1.5. Do the exercises 21, 23, 24, 25, 26, 27, 29, 31, 32, 33, 35, 36, 37, 39, 40, 43, 44, 46, 49, 51, 55, 56, 64, 65, 70.

Tuesday, January 11, 2011

• Read Section 1.4. Do the exercises 1, 2, 9, 10, 16, 19, 20, 24, 25, 26, 27, 28, 29, 30, some of 31-36, 37, 38, 41, 42, 43, 44, 45.

Tuesday, January 11, 2011

• Read Section 1.3. Do the exercises 1, 2, 9, 11 - 19, 28, 30, 31, 33, 34, 41, 46, 55, 56, 57.