MATHEMATICS 198 &C1: Mathematics Via Problem-Solving

Call # 05056
10 M W F
??? Altgeld Hall
3 hours

This course introduces students to mathematical ideas, improving their ability to understand and communicate careful arguments via practice in problem-solving and writing proofs. We develop techniques to solve interesting problems that may sound like "brain-teasers" (sample problems appear below). After understanding the structure of logical statements, many problems can be solved using elementary techniques involving functions, induction, counting models, and equivalence relations. Later techniques include the pigeonhole principle, recurrence relations, and limits.

Mathematics is an active process of thought; one learns mathematics best by doing mathematics. Understanding of mathematical ideas is clarified by communicating them to others. For these reasons, this course will run in seminar format, with no lectures. Class time will be spent mostly on student presentations of solutions to problems, with comments by fellow students and by the instructor. For well-motivated students in a small group, this format provides a more enriching experience than a lecture course about proofs, and it encourages students to develop their talents more fully and quickly.

Skills in written communication of logical arguments are also valuable. Students will write solutions for two problems per week in addition to the problems discussed in class. Most of the problems and the development of mathematical ideas useful for solving them come from the text Mathematical Thinking: Problem-Solving and Proofs, by John D'Angelo and Douglas West.

This course has no college-level mathematics prequisite. Furthermore, since it introduces students to the discovery and communication of logical arguments, students should not have taken Math 247 or 300-level mathematics courses before or with this course. It will be good preparation for advanced courses (or occupations) where such skills are used.

Here are examples of problems we may solve:

1. Does every year have a Friday the 13th?
2. Which positive integers are sums of consecutive smaller positive integers?
3. How does one count the squares of all sizes in a square grid, or the triangles of all sizes in a triangular grid?
4. At a party with five married couples, no person shakes hands with his or her spouse. No two people other than the host shake hands with the same number of people. With how many people does the hostess shake hands?
5. If each resident of New York City has 100 coins in a jar, is it possible that no two residents have the same number of coins of each type (pennies, nickels, dimes, quarters, half-dollars)?
6. How can we find the greatest common divisor of two large numbers without factoring them?
7. Why are there infinitely many prime numbers?
8. A dart board has regions worth a points and b points, where a and b are positive integers with no common factors. What is the largest point total that cannot be obtained by throwing darts at the board?
9. A bear's cage has two jars of jelly beans, one with x beans and the other with y. Each jar has a button. When a jar has at least two beans, pressing its button gives one bean to the bear and moves one bean to the other jar. Under what conditions (on (x,y)) can the bear eat all the beans except one?
10. 1500 soldiers arrive in training camp. A few soldiers desert. The sergeants divide the remaining soldiers into groups of 5 and discover that there is 1 left over. When they divide them into groups of 7 or 11, there are 3 left over. How many soldiers deserted?
11. Are there more rational numbers than integers? Are there more real numbers than rational numbers? What does ``more'' mean for infinite sets?
12. Airlines A and B serve the same airports. Can A have a better on-time performance than B at every airport but worse on-time performance than B over the full system?
13. Candidates A and B in an election receive a and b votes, respectively. If the votes are counted in a random order, what is the probability that candidate A never trails?
14. Can a 6 by 6 chessboard be covered with 1 by 2 rectangles so that the arrangement cannot be cut along any horizontal or vertical line?
15. How many positive integers less than 1,000,000 have no common factors with 1,000,000?
16. After n students take an exam, the papers are distributed randomly for peer grading. What is the probability that no student gets his or her own paper?
17. There are n girls and n boys at a party, and some boy/girl pairings are compatible. Under what conditions is it possible to pair off the girls and boys using only compatible pairs?
18. How many regions are created by drawing all chords joining n points on a circle, if no three chords have a common point?
19. Why are there only five Platonic solids (the tetrahedron, cube, octahedron, dodecahedron, and icosahedron)?
20. n spaces are available for parking along a curb. Rabbits take one space, and Cadillacs take two spaces. In how many ways can we fill the spaces? In other words, how many lists of 1's and 2's sum to n?
21. What numbers have more than one decimal expansion?
22. For each point in a tennis game, the server has probability p of winning the point, independently of other points. What is the probability that the server wins the game?
23. Two thieves steal a circular necklace with 2m gold beads and 2n silver beads arranged in some unknown order. Can they cut the necklace along some diameter so that each thief gets half the beads of each color? Does every circular wire always contains two diametrically opposite points having the same temperature? How are these questions related?

INSTRUCTOR: Douglas West received his Ph.D. in mathematics from the Massachusetts Institute of Technology. He then taught one year at Stanford University and three years at Princeton University before joining the U. of I. faculty in 1982. He has published two textbooks and numerous research articles. His area of research is discrete mathematics, especially graph theory and partially ordered sets. He is currently Vice Chair of the Activity Group in Discrete Mathematics of the Society of Industrial and Applied Mathematics, and he is an Associate Editor of the American Mathematical Monthly. He also sings in the chorus of the Illinois Opera Theatre and is an avid squash player.