Proposition: Given n+1 integers among the numbers from 1 to 2n, at least one will be a divisor of another.The solution is based on placing numbers in boxes labeled with their largest odd divisor. Given any two numbers in the same box, the smaller will necessarily divide the larger. Observe that there are only n boxes.
We also started 5.1, Recurrence Relations. I started discussing a method for determining the number of onto functions from a set with n elements to a set with n or fewer elements.
How many functions are there from a set with r elements to one with n elements?
If you get sent out to the doughnut shop to buy a dozen assorted donuts how many different assortments (types, number of each type) can you come home with?
How many arrangements are there of the letters in the word MISSISSIPPI?
October 26, 2000

Announcements:
TEST GRADES from 40 0 9 10 13 13 13 13 14 15 15 16 17 17 17 17 17 17 19 19 19 19 20 20 21 21 21 21 21 21 21 22 22 22 22 23 23 23 23 23 23 24 24 24 24 24 24 25 25 25 25 25 25 25 25 26 26 26 26 27 27 27 27 27 27 27 27 28 28 28 29 29 29 29 30 30 30 30 30 30 31 31 31 32 32 32 32 33 33 34 34 34 34 34 34 34 34 34 34 34 36 36 38 40 40 MTB > describe TEST GRADES N MEAN MEDIAN TRMEAN STDEV SEMEAN C2 104 25.163 25.000 25.340 7.172 0.703 MIN MAX Q1 Q3 C2 0.000 40.000 21.000 30.000 MTB > histogram TEST GRADES Histogram of TEST GRADES N = 104 Midpoint Count 0 1 * 5 0 10 2 ** 15 14 ************** 20 17 ***************** 25 32 ******************************** 30 20 ******************** 35 15 *************** 40 3 ***
 (8 points) An abstract proof to prove a function is onetoone or onto.
 (6 points) A proof about the cardinality of a particular set.
 (12 points) Proving for some particular f and g that f is O(g) but that g is not O(f).
 (6 points) Comparison using worstcase time complexity of two procedures each of which is implemented using different algorithms where the worstcase time complexity of the algorithms to be used is known.
 (8 points) Basic proof using the definition of a  b.
Lecturer: Eli Brettler
Office: South 508 Ross
Telephone: 7362100 Extension 66321
Email:
brettler@mathstat.yorku.ca
WWW: http://www.math.yorku.ca/Who/Faculty/Brettler/
Normal Office hours: MW 1112:30 and by appointment
Lectures: MWF 12:30  13:30 CLH C
Tutorials: Wednesday 10:30  11:20, Thursday 12:30  1:20 N 501 Ross
Text: Kenneth H. Rosen, Discrete Mathematics and its Applications, Fourth Edition
Coverage: Chapters 1.6  1.8, 2.1  2.5, 3.2  3.4, 4.1  4.3, 4.6  4.7 5.1  5.5, Chapter 8
Homework: Homework problems will be given but will not be collected for grading. Click for a selection of homework problems .
Quizzes  Sept. 29, Nov. 3  15% 
Class Tests  Oct. 13, Nov. 17  40% 
Final Exam  Examination Period  45% 
Note: There will be no makeups for missed tests or quizzes. If you miss a test or quiz for medical reasons and provide a medical certificate, the weight of the test will be transferred to the final exam. Otherwise, the mark for the missed work will be 0.
Answers and Solutions:
For the pdf versions you need the free Acrobat reader.
Note: The last date to drop the course without academic penalty is November 10. It is extremely important to realistically assess your course performance prior to this date. .