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, 1416, 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: 113, 21, 22, 28, 29, 30.
 Some solutions from Section 4.3 as a Mathematica file are here and a pdf printout of the same file is here.
 Monday, March 7, 2011

 Read Section 4.3.
 Do as many exercises as you can from 143.

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 133. Also 36, 37 (the answer should involve a single formula involving n), 3842, 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 onetoone correspondence and bijection are synonyms; see Definition 8 on page 101. I am disappointed that the author uses "onetoone 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 and , between and odd integers, between 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 and and its inverse. These formulas are illustrated with appropriate graphs.
 In the second
notebook I give a formula for a bijection between and . 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 1318, 19, 20, 21, 23, 31, 32,
 Please check:
 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) 5560, 65, 66
 Wikipedia's Function page:
 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
is irrational
is proved by contradiction in Example 21 on page 66 in the textbook.
 In class I proved the implication If
, then is irrational.
 In fact, I proved the contrapositive: If
is rational, then .
The colored contrapositive is: is rational implies .

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.
 Assume that is rational.
 Then:
There exist integers and such that
,
not both and are even, and .

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

Consider Case I first. Assume that is odd.

From Line 4 we deduce is odd.

By Line 2 we have is an integer.
This implies is even.

From Lines 5 and 6 we deduce .
 From Lines 2 and 7 we deduce .
(This completes the proof for Case I.)

Now consider Case II. Assume that is even.

By Line 9 we have: There exists an integer
such that
.

By Line 10 we have is even.

From Lines 2 and 9 we deduce is odd.

From Line 12 we deduce is odd.

From Lines 11 and 13 we deduce .

From Lines 10 and 14 we deduce .
 From Lines 2 and 15 we deduce .
(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 3136, 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. Rightclick on the underlined word "Here"; in the popup 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 113 and most of 1429. 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, 5155.

Here is a pdf file of the first few sections of the book.