Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers

Possible Solutions: Supplementary Problems Set A

1. Suppose that we subdivide the given equilateral triangle into four congruent equilateral triangles of side length 0.5 units (see figure below). [Can you justify this construction?] By the P-H-P, at least one of these four triangles must contain two points. Call these points A and B.

The greatest distance between two points in or on an equilateral triangle occurs when the two points are unique vertices of the triangle. [Can you justify this assertion?] Each of the four congruent equilateral triangles has vertices that are 0.5 units apart.

This justifies that for five points within the original equilateral triangle there are two points no more than 0.5 units apart.

2. In the group of five people, the number of possible acquaintances for each person is in the set {0,1,2,3,4} if we assume that a person is not an acquaintance of him or herself.

Suppose that someone in the group has 0 acquaintances. Then for the remaining four people, the number of possible acquaintances is in the set {0,1,2,3}. If one of these four has 0 acquaintances, we're done, as we now have two people with the same number of acquaintances. If not, four people have 1, 2, or 3 acquaintances, and by the P-H-P, there must be two with the same number of acquaintances.

Suppose, however, that no one in the group has 0 acquaintances. Then there are five people each with acquaintances numbering from {1,2,3,4}. By the P-H-P, at least two people must have the same number of acquaintances.

3. Let A, B, C, D, E, and F represent the six people (see figure below). Concentrate on person A. This person must be friends with at least three people or must be enemies with at least three people (why?). Suppose person A is friends with B, C, and D (see bold lines in figure). Then if either B and C are friends, C and D are friends, or B and D are friends, we have met the requirements of the problem. If none of those friendships hold, then B, C, and D are mutual enemies.

4. One way to approach this problem is to label the days of the non-leap years using positive integers from 1 through 365 and the days of the leap years using positive integers from 1 through 366.

The table below shows the labels for the 13th day of each month, both for non-leap years and leap years. In parentheses after a 13th's label is the remainder when the label is divided by 7. Call this an index number for the 13th of each month.

Non-Leap-Year Labels and Index Numbers for 13th of Each Month
Leap-Year Labels and Index Numbers for 13th of Each Month
13 (6)
13 (6)
44 (2)
44 (2)
72 (2)
73 (3)
103 (5)
104 (6)
133 (0)
134 (1)
164 (3)
165 (4)
194 (5)
195 (6)
225 (1)
226 (2)
256 (4)
257 (5)
286 (6)
287 (0)
317 (2)
318 (3)
347 (4)
348 (5)

The index numbers, then, represent a day of the week. Although we don't know what day of the week each index number represents, because we have not indicated on what day of the week January 1 falls, we can be assured that a Friday the 13th occurs sometime during the year, because all possible index numbers, 0 through 6, do occur at least once in each list (non-leap-year and leap-year).

5. Here's a grid layout of the streets Georgette walks every day. Added to the grid are values representing the number of ways Georgette could walk to get to that point. For instance, three blocks right and two block down is the value 10. This represents the number of different ways she could walk from her home to that point. Continuing this accounting of how many ways there are to get to each intersection point (not all shown here) results in 5005 different ways Georgette could walk from home to work.


6. For the first question in this problem, we need to consider all the ways Seth could group together cards with duplication allowed. That is, think of Seth looking at a layout of 50 cards, 5 copies of each of 10 different cards. Seth can take any group of 5 he wants from those 50. Let us label the cards A, B, C, and so on through card J.

We might organize the possible groups he could choose by first looking at groups with all the same card: AAAAA, BBBBB, CCCCC, DDDDD, and so on. There are 10 such groups. We might then consider altering just one card in each of these: AAAAB, AAAAC, ..., AAAAJ, BBBBA, BBBBC, ..., BBBBJ, ...., JJJJI. How many of this type are there?

If we are careful enough to organize our list to account for all possibilities with no missed or repeated groups of 5, we would eventually count 2002 different groups of 5.

For the second question, actually a simpler problem to solve, we could also organize our counting as we did above, perhaps starting with ABCDE, ABCDF, ABCDG, and so on, through to FGHIJ. There are 252 of these types of groups of 5.

7. This is a problem to which we can apply the Pigeonhole Principle. If every one of the 50 letter boxes were to get 4 letters, none of them would have the required 5 letters. with the next letter delivered, however, our requirement would be met. Thus we need 50*(5-1)+1 = 50*4+1 = 201 letters to meet the described condition.

Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes