Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers Spring 1999 6:00 - 8:50 pm Tuesday STV 332 Dr. Roger Day (day@ilstu.edu)

 Syllabus Grades & Grading Session Notes Assignments and Problem Sets Tests and Quizzes

## Session 1: 12 January 1999

### Perfect Covers of Chess Boards

• Description and Exploration
• An Exemplary Combinatorics Problem Situation

### The Pigeonhole Principle

• An Initial Problem
• Generalizing the Principle
• A Concluding Problem

### Assignment #1

#### Perfect Covers of Chess Boards

We will explore the problem of finding the perfect covers of an n-by-m rectangular chess board with dominoes measuring 2-by-1 units. A perfect cover means that there are no gaps or overlaps when we cover the board entirely with the dominoes.

We first consider two questions:

1. What restrictions are there are n and m?
2. How many ways are there to cover an n-by-m board?

We will work in small groups to determine the restrictions on m and n and ncourage multiple ways to justify our results. We will then consider the second question, again exploring the strategies used among the groups.

To extend the problem, we can look at a pruned 8-by-8 chess board. Does a perfect cover exist for such a board?

Another extension is to consider perfect covers of a j-by-k-by-l rectangular prism, using a 1-by-1-by-2 domino.

We'll carry out an activity designed to remix the student groups and to encourage you to get to know your colleagues. We will next return to the perfect cover problem and use our exploration to identify fundamental components of a problem-solving approach to combinatorics problems:

• Can a task be completed?
• How so?
• In how many ways?
• What are some extensions and variations to the problem?

In using these key questions to exemplify the type of investigations that will underscore course activities, we will emphasize the need to justify our efforts as we progress in solving a problem. We will talk about the need to consider or search for elegant and creative ways to approach problems.

#### The Pigeonhole Principle

We will next explore a problem situation designed to highlight the Pigeonhole Principle.

How many students would be required to place soda orders, one soda per student, in order to insure that at least one of the six listed sodas would be ordered by at least two students?

The phrase "worst-case scenario" helps us determine the maximum number of students that could place orders without meeting the condition and then consider what must be done from there to meet the condition.

Next, consider two variables in the original problem situation: (1) the number of sodas available, and (2) the number of repeat orders desired. We can use n (here, n=6) to represent the first value and k (here, k=2) to represent the second. You are challenged to use n and k to write a statement that characterizes the principle used to solve the problem with these variables in place.

Does the following statement describe the principle behind the solution to the original problem, using the context of boxes and pigeons? Is so, how? If not, why not?

When placing pigeons into n boxes, the number of pigeons required to insure that at least one of the boxes has at least two pigeons is n+1 pigeons.

Student groups will generate similar statements to describe the more general case with n boxes and at least k pigeons in one of the boxes. Also, you'll be asked to write and solve a problem, different from the sodas-and-students context, with which to test your general statements. Here are some sample problems from other students. Are they all accurate?

We'll exchange your problems and solve them. We'll use any group questions to help address misunderstandings about the Pigeonhole Principle.

Here is one of the last pigeonhole problems we're likely to explore during the session:

We have 10 boxes labeled 1 through 10 into which we place pennies. How many pennies are required to insure that at least one box contains at least as many pennies as the label on the box?

Groups will explore the problem.

#### Assignment #1

The rest of the first session will be used to discuss the syllabus, course requirements, and other course components. The first set of textbook problems and supplementary problems will be assigned as indicated here.