Winter 2011
MATH 209: Discrete mathematics
Branko Ć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

Read Section 4.5.
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

Read Section 4.4.
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

Read Section 4.3.
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

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

Monday, February 28, 2011

Read Section 4.1.
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

Read Section 3.3.
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,
Please check:
- The On-Line Encyclopedia of Integer Sequences
- In particular 1,2,2,3,3,3,4,4,...
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

Read Section 3.1.
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:
- Function

Thursday, January 27, 2011

Read Section 1.6 . Do the exercises 1 - 21, 24, 25, 27, 28.
Some relevant Wikipedia links:

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.
Start reading Section 1.5.

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.
Read Section 1.4.
Today in class I demonstrated how to use Mathematica to explore simple propositions. Here is the Mathematica file that I used. It is called 20110111.nb. Right-click on the underlined word "Here"; in the pop-up menu that appears, your browser will offer you to save the file in your directory. Make sure that you save it with the exactly same name. After saving the file you can open it from Mathematica. You need to find a campus computer with Mathematica installed on it (for example BH 209, BH 215). You will find Mathematica as follows (this sequence might differ on different campus computers) Start -> Programs -> Mathematica. Open Mathematica first, then open 20110111.nb from Mathematica. You can execute the entire file by the following manu sequence (in Mathematica): Kernel -> Evaluation -> Evaluate Notebook. To execute the individual cells, place the cursor in that cell and press Shift+Enter.
If you have problems running this file please let me know. I think that it is well worth your time to learn how to use Mathematica.

Friday, January 7, 2011

Read Section 1.2. Do the exercises 1-13 and most of 14-29. Also do 49 and 51.

Tuesday, January 4, 2011

The information sheet
The textbook loan form
Read Section 1.1. Do the exercises 6, 7, 10, 12, 13, 15, 16, 20, 21, 22, 23, 24, 27, 30, 39, 40, 41, 51-55.
Here is a pdf file of the first few sections of the book.