Solving Discrete Problems. Math 2020, Fall 2005. H. A. Verrill

Course text book:

The art and craft of Problem solving, by Paul Zeitz.

Additional text: "The art of problem posing" by Stephen Brown and Marion Walter.

Handouts for the first class (will be added here soon). Included are grading scheme, class meeting time and place, office hours, etc.

Useful web pages:

The art of problem solving web site.
The Spring 2005 version of this course.

Week 1, class 1 August 22 2005

Handouts:

Class outline

1) Discussed outline of the course (see first handout)
2) Completed questionaire (second handout)
3) Hand shake problem: For a group of 5 or so students, what's the fastest way everyone can shake hands? Regarding this problem, we discussed:
- Using a graph to find a solution
- Using symmetry to find a solution
- How to prove the solution found is the best possible solution e.g., for 8 people, there must be at least 7 handshake times. For 5 people, at least 4 - though it turns out you need at least 5 times people have to shake hands, since one person it always left out.
- Other questions we could ask about this situation.

Week 1, class 2 August 24 2005

Class notes taken by Breland
Topics:
- 1) went over Monday's quiz, especially review logs
- 2) Another hand shaking problem

Week 1, class 3 August 26 2005

Class notes taken by Amy G.
Topics:
- 1) Went over Monday's homework - Important point: what assumptions do you make when trying to solve a problem?
- 2) Start on looking at proof by induction
  Links about proof by induction:
  - There is a nice web page at GATECH, with domino explanation of proof by induction, and link to more examples.
  - David Summer's page on induction.
Homework, on induction, due next Wednesday, August 31, Exercises 2.3.27, 2.3.28, 2.3.31, optional: 2.3.35.

Week 2, class 1 september 7 2005

Notes taken for this class, by Shannon O.
Handout for this class, with homework on induction to be handed in this Friday.
Handout with details about a project we will start soon.
Problem done in this class: coloring vertices of a triangulation of a polygon. See page 53 of the text book for a proof.
Proof of the vertex coloring problem

Week 2, class 2 september 9 2005

Notes taken for this class, by Lauren W.
This class was on more examples of induction.

Week 3, class 1 september 12 2005

Class notes taken by Katie
Topics:
- Group work on projects
- Method of proving sum formulas by induction

Week 3, class 2 september 14 2005

Class notes taken by Shannon O.
Topics:
- Example of proof by induction for sums - sums of squares formula.
- Answering and asking some questions about induction.
- Group work on some induction puzzles.

Week 3, class 3 september 16 2005

Class notes taken by Katie.
Answers to questions from Wednesday
Today we did more work on the four problems handed out on Wednesday. Proofs of two were given in class.
Some web pages with more info about these problems:
- Cut the knot's tower of Hanoi
- Cut the knot's chocolate bar
- Tiling with L-shapes page (plus tower of Hanoi)
- L-shaped tiling java applet
- Math world page on Fibonacci numbers includes details about the domino tiling problem we discussed.
- R. Knott's Fibonacci page includes the domino problem, with a link to solution.

Week 4, class 1 september 19 2005

Class notes taken by Aimee.
The four induction problems we've been looking at
Pictures showing key idea of how each case can be seen in terms of the previous cases.
Today's class:
- Proof of the formula for number of ways of tiling the 2xn rectangle with dominoes
  Reference: See R. Knott's page with solution to this problem
- Proof that its possible to tile a 2ⁿx2ⁿ board with one square removed with L-shapes.
  Reference: See D. Garcia's solution and take a look at C. Mawata's java applet. More information about this problem is given by N. Starr.

Week 4, class 2 september 21 2005

Class notes taken by Shannon O.
Today we discussed a method of generating new problems from old problems. The case of the tower of Hanoi problem was discussed in detail on the board, other cases discussed in small groups.
Homework (due Friday September 23): Write a list of attributes for each of the problems on the handout given out last time, except the Tower of Hanoi problem, which was discussed in class.

Week 4, class 3 september 23 2005

Today we worked on generating new problems on induction.
We discussed the attributes of the induction problems we've been looking at.
Homework based on the discussions, due Friday September 30:
- Q1: Given a 3-dimensional "chocolate bar", with sides of integer lengths, n, m, p, i.e., an n x m x p block, how many breaks are needed to break the chocolate bar into 1x1x1 cubes? Make a conjecture about the number of breaks needed, and prove this by induction.
- Q2: If you have a chocolate bar with a random shape, and you want to break it into n-peices, also of random shapes, what is the minimum number of breaks needed? Prove your conjecture by induction.
- Q3: If you have a n by m board, and you have T-shapes, consisting of 4 unit squares, what is the smallest number of squares left over when you've filled the board with as many pieces as possible?
- Note, the first two questions have a precise answer, which should be proved, similarly to the proof of the original chocolate bar question, with proof on the questions and answers handout. Question 3 is an open ended question. See what you can come up with for different values of n and m, and if you can find any general rules.
Homework that was due today has been taken in as "bonus" homework, so as not to effect those who were unable to hand it in. If you did do the homework on time, but were unable to come to class, just give it to me next class.
Final versions of group projects will be due next Wednesday, unless the university is closed Monday, in which case they will be due Friday. Bring 6 copies of your final project. If you want, you can just bring me one copy earlier in the day, and I will make copies. Each group will look at the project of another group to make any really final comments. If there are more comments, then corresponding changes will have to be made; if not, then the next class, everyone will receive a copy of the project.
Next Wednesday we will start to talk about counting problems.

Week 5, class 1 september 28 2005

Class notes taken by Katie.
Updated list of attributes, which is an updated version of the handout given last Friday. Also includes a list of "What if not" questions from group work.
Homework due Wednesday October 5
Today's class was about combinatorics. We followed the book, chapter 6.
Remember, group work is due this Friday!

Week 5, class 2 september 30 2005

Class notes taken by Danny.
Today we disccussed more about permutations, as in text book chapter 5.
We talked about different ways of arranging colored pieces in a loop. We used Tangle toys to build examples. One question was: How many ways are there to make a circlular loop from 4 different colored segments, each forming one quarter of a circle. E.g.: There are lots of similar questions, e.g., how many loops are there of length 6, using 2 red, 2 blue, 1 yellow and 1 green piece?
We gave out projects for evaluations. Group homework, to be turned in next Thursday, is to write a report on these projects. Your report could be about a page long, and should comment on the following:
- Is the project correct, and can you tell whether it is correct without too much effort, i.e., do the writers explain the steps they make?
- Are there examples, where this would be helpful? You may suggest an example if you want.
- Are there diagrams or graphs, where this helps, and are they correct? You could suggest a diagram if you want.
- Is it readable, and is language used correctly, e.g., are words like "definition", "theorem" and "induction" used in the right way?
- Any over all comments or suggestions for improvements.
Don't forget the induction homework, due next Wednesday!

Week 6, class 1 October 3 2005

More counting of number of ways to take different things.
How many "intertwine bouncing balls" are there? (I bought the ones I used in class from (school aids, on Interline Highway)
It turns out there are 12 possible balls from 6 bands in the colors red, yellow, pink, green, orange, blue.
Here is a set of problems we started looking at . Answers to 1-5 are here.

Week 6, class 2 October 5 2005

Class notes taken by Amy S.
Today we discussed why the binomial numbers occur in Pascal's triangle (page 210 in text book).
Homework due Friday 14 October:
- For each of the examples listed on pages 208-209, find a similar example, with the same mathematical notation, but different numbers and different things being counted than in the given examples.
- Plus: 6.1.26, 6.2.14, 6.2.10, 6.2.21.
Finally, we looked at some mathematics journals and magazines, and talked a little about journals.

Week 6, class 3 October 6 2005

Class notes taken by Jen.
We continued to discuss problems involving binomials, as on the handout given out on Monday.
Question 5 from the sheet is the binomial theorem; page 211 of text book.

Question 4 is discussed on page 220 of the text book. The key to this question is how to encode a path from (0,0) to (m,n). There are several ways to acheive this encoding. E.g:

Method of encoding	Whether to go up or right at each unit distance	Think of as a graph - what is the y value on each unit interval in the x-direction?	As a graph, what is the change in y value from one unit interval to the next unit interval in the x direction?
example with encoding drawn in
Encoding for the example	U,R,R,U,U,R,R,R,U,R	1,1,3,3,3,4	1,0,2,0,0,1,0
Property of the encoding	Sequence of length 6+4=10, with 6 Rs and 4 Us	Sequence of length 6, consisting of integers between 0 and 4 (inclusive), and each number at least as big as the last	Sequences of integers of length 7, with sum 4.

Week 7, class 1 October 10 2005

Class notes versions by Shannon O and Charles.
Covered today:
- What homework is due when (see class notes).
- Binomial theorem (see page 211 in text book).
- Counting problems involving n lines in a plane.

Week 7, class 2 October 12 2005

Class notes by Shannon O.
Covered today:
- The take home midterm exam was given out today. Due Friday 21 October.
- How to write n as a sum of m non-negative integers (text book page 220 - 221)
- Applications of above result.
- Counting problems involving n lines in a plane. We discussed several different questions. (Mouse over image to see a few). Locate answers to various problems in Pascal's triangle.
  
  How many ...?

Week 7, class 3 October 14 2005

Class notes by Mallory.
Today we continued the discussion of counting problems involving counting things in a picture of n lines in the plane.

Week 8, class 1 October 17 2005

Class notes by Charles.
Covered today:
- Went over homework - ways of coloring, with symmetries, rotations.
- Gave out copies of the project.

Week 8, class 2 October 19 2005

Class notes by Lauren W.
Covered today:
- Example similar to an exam question.
- Continuing discussion of counting things in diagram with n lines.

Week 8, class 3 October 21 2005

Today we went over solutions to the midterm take home exam.
Here are the solutions.

Week 9, class 1 October 24 2005

Class notes by Kathy.
Handout with titles of journals, and homework
Discussion of how to prove a generalization of the triangle inequality (question 2 on take home exam).
Quick mention of magic squares problem, and related question.

Week 9, class 2 October 26 2005

Class notes by Mallory.
Proof by contradiction.
Problem about putting n equal length rods together to form a three dimensional polygon.

Week 9, class 3 October 28 2005

Class notes by Amy.
Submitting journal articles.
More proof by contradiction, with irrationals and tiling.
Some web sites on proof by contradiction:
- Larry W. Cusick's site on proof by contradiction.
- Introducing mathematics pages on proof by contraduction.
- Proof by contraduction 11 slides with several examples, by Robert Hochberg.
- Henry Cohn, (of Microsoft) has comments on the Dangers of proof by contradiction.
- Wikipedia definition of proof by contradiction.
- The encyclopaedia definition of proof by contradiction.
- Jim Loy's pages have some examples of proof by contraduction, as well as other examples of proof.
- Guide to proof strategies, including proof by contradiction
- Some notes on proof, including proof by contradiction, by Ross McConnell, at Colorado State University.
- Some examples of proving irrationality, using proof by contradiction, at cut the knot.

Week 10, class 1 October 31 2005

Class notes by Shannon.
Proof of "proof by induction" using proof by contradiction.
Pigeon hole principle method of proof.
Homework: Prove that the decimal expansion of a rational number a/b is repeating. Say where you use the pigeon hole principle in the proof. Hint: Compute some examples by long division, e.g., what is the decimal expansion of 4/7? (Do this by hand, not by a calculator; if you do this by hand, you should start to see why you get a repetition). Note, by a repeating decimal, we mean a number for which the last set of digits is repeated over and over again. This last set could just be the number 0, so terminating decimals can be considered repeating. E.g., 3456.870154353535353535353... (where the 35 repeats indefinitely) is repeating. So is 0.000446 = 0.0004460000000000... (where the digits are all zeros after the 446).
Some links on proof using the pigeonhole principle:
- Cut the knot page on the pigeonhole principle.
- Examples of applying the pigeonhole principle, by Larry W. Cusick.
- Examples of pigeonhole principle, by Gary MacGillivray.
- Wikipedia's explanation, which includes a photo of pigeons in holes

Week 10, class 2 November 2 2005

Class notes by Rebekah.
Discussion of methods of proof.

Week 10, class 3 November 4 2005

Class notes by Kathy.
Proof by computing something in two different ways.

Week 11, class 1 November 7 2005

Class notes by Danny.
More pigeonhole examples.

Week 11, class 2 November 9 2005

Class notes by Katie.
Definitions
- The converse of "P implies Q" is "Q implies P". These statements are not equivalent, i.e., one can be true, but the other false.
- The contrapositive of "P implies Q" is "not Q implies not P". These statements are equivalent, i.e., if one is true, then so is the other.
links on converse and contrapositive:
- wikipedia definition of converse
- wikipedia definition of contrapositive
- Examples of converse and contrapositive by Shuai Wang
- Planet math definition of contrapositive
- Notes on contrapositive on Peter Williams's types of proof pages
- Proof by contrapositive from Larry W. Cusick's notes on "How To Write Proofs".
- The contrapositive (and other logical rules) in Lewis Carroll's puzzles.

More pigeonhole examples.

Examples of the following form: "if there are n points in a shape S, prove that however these points are put in the shape, m of them must all be at most distance d from each other."
The values of n, S, m and d are different in different problems.
Examples:

However 25 points are put in the star shape below, there must be 3 points all at most distance 1 from each other."	However 5 points are put in a square of side length 1 there must be 2 points all at most distance sqrt(1/2) from each other."	However 5 points are put in the equilateral triangle, side length 1, there must be 2 points all at most distance 1/2 from each other."

To prove these results, you have to divide each shape into some pieces, use the pigeon hole principle to show one region must have at least m points (for whatever m is), and then use geometry to show that points in the same region are at most distance d apart.
(click here for a picture of divisions that will work for these examples; think of the regions as "holes", and the points as "pigeons").
Click here for examples of putting points in which don't satisfy the conclusion of the theorems (but don't have as many points as needed in the theorems); this is supposed to clarify the problems. If one more point is added in these examples, there will then be the number of points at most the distance apart specified, as in the theorems. (Note, the first picture only shows 18 points; can you arrange more so no 3 are all distance at most 1 apart?)
Homework (due Friday 11 November) find a similar example to the above (i.e., an example with a different shape and different numbers of points).

Another example of the pigeonhole principle: If the plane is colored in two colors, then there are some 2 points the same color distance 1 apart (see page 93, ex 3.3.1 in the text book for a solution). There are many similar such problems. See ex. 3.3.27, page 102, for some other similar problems. We will discuss at least one more examples like this on Friday.
For more examples of the pigeonhole principle, look at these notes by Gary MacGillivray.
Web page with more coloring problems in discrete math at the geometry junk yard.

Week 11, class 3 November 11 2005

Class notes by Kathryn.
Another pigeonhole example.

Week 12, class 1 November 14 2005

Class notes by Kathy.
Pigeonhole example, together with numbers mod n.

Week 12, class 2 November 16 2005

Class notes by Shannon.
Relationships on sets.
Handout with definitions
Some pages with information and examples about equivalence relations:

Week 12, class 3 November 18 2005

Class notes by Kathryn.
Relations on sets.
Homework on relations, due after thanksgiving holiday

Week 13, class 1 November 21 2005

Class notes by Shannon.
Equivalence relations on sets.
Solutions to odd exericises, for homework given out on Friday.

Week 13, class 2 November 23 2005

In this class we went over odd questions, exactly as in printed notes:
Solutions to odd exericises, for homework given out on Friday.

Week 14, class 1 November 28 2005

Class notes by Charles.
Some examples of using equivalence relations.

Week 14, class 2 November 30 2005

Class notes by Katie.
An example using equivalence relations, pigeonhole principle, and some combinatorics.
Started on study of symmetries.
Handout on wallpaper patterns:

Week 14, class 3 December 2 2005

No notes; see hand outs for previous classes.

Week 15, class 1 December 5 30 2005

Discussions of symmetries of wallpaper patterns.
Symmetries of polyhedra.
Solutions to quizes (see handouts for week14 class 2) +:
- Sheet A
- Sheet B

Week 15, class 2 December 7 30 2005

Symmetries of the dodecaheron.
Building a dodecahedron following Jim Plank's instructions:

Week 15, class 3 December 9 30 2005

Students give a short presentation on each journal.
Here are the journals:

Last modified: Tue Aug 30 13:39:21 CDT 2005 <