Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers Spring 1999 







Perfect Covers of Chess Boards


The Pigeonhole Principle


Summation and Product Notation 

Assignment #1 
We will explore the problem of finding the perfect covers of an nbym rectangular chess board with dominoes measuring 2by1 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:
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 8by8 chess board. Does a perfect cover exist for such a board?
Another extension is to consider perfect covers of a jbykbyl rectangular prism, using a 1by1by2 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 problemsolving approach to combinatorics problems:
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.
We will next explore a problem situation designed to highlight the Pigeonhole Principle.
Referring to the soda menu from Blaise's Bistro, we ask:
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 "worstcase 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 sodasandstudents 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.
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.




