Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers

### Sample Responses to Course Assignments

This page shows sample student solutions to typical problems from an assignment and from a test. The responses are categorized as less than adequate, adequate, and more than adequate so that you can begin to understand my expectations regarding submitted solution responses for homework, quizzes, and tests.

The examples were selected from actual student papers. For some, I have edited the responses in order to make the response better fit a category. The posting of specific responses is intended to help you become a better communicator of your solutions and the thoughts behind your solutions. It is not my intention that any student's work has in any way been singled out for criticism or other attention. Please speak to me if you have concerns about this.

As you read through these samples, try to generalize the evaluation criteria inherent for each of the response levels. We can discuss your generalizations.

Assignment Problems and Sample Solutions

.

### Problem #3

.

The smallest of r consecutive integers is n. What is the largest?

How many integers between 1 and 2000 are multiples of 11 but not multiples of 3?

In a group of 5 people, show that there are two who have the same number of acquaintances in the group. Generalize your result to show that in a group of n people, there are two who have the same number of acquaintances.

.

Sample 1-L1

n + r - 1 is the largest

Sample 2-L1

181/3 = 60
181-60 = 121

Sample 3-L1

If a and b know each other and no one else in the group, they have the same number of acquaintances. It doesn't matter whether the group has 5 people or n people.

.

Sample 1-L2

n + r - 1 represents largest integer;
example: 4 5 6 7
n
r total

Sample 2-L2

121
2000 /11 = 181.8
2000/33 = 60.6
181-60 = 121

Sample 3-L2

In a group of 5 people, there could be 0-4 acquaintances [chart]:
Person # of people she knows
A 0
B 1
C 2
D 3
E must know someone since person D knows 3 people

Sample 1-L3

n = smallest integer
r = # of consecutive integers
k = largest integer
n + (r - 1) = k

Sample 2-L3

121: delete 33,66,99, . . . , 1980 = 60
181-60 = 121

Sample 3-L3

If one person knows 0 then have four people to fill 3 boxes. If everyone knows at least one person, then 4 boxes to fill.

.

Sample 1-A1

n + r - 1
r = 10 integers
n = 7 (smallest)

7 + 10 - 1 = 16 largest

(n) smallest r (#s) largest n + r - 1
2 1 2
2,3 2 3
2,3,4 3 4

Sample 2-A1

11,22,33,44,55,66,77,88,99 [Solver showed large X through 33 and 66 and 99.]
Out of nine numbers in sequence, three are pulled out of the sequence from above. So in a sequence with 181 members [answer to 9a], 60 would be pulled out, leaving 181-60 or 121.

Sample 3-A1

There are five possible combinations for five people, so it seems that there could always be a different one for each person. However, since it is impossible for one person in the group to be an acquaintance with everyone else (4,0) while another person in the group has no acquaintances (0,4), they are mutually exclusive. since that leaves only four combinations for five people, two people will have the same combination of acquaintances.

In any group of n people, the number of possible combinations will always be (n - 1) so at least two of n people will have the same number of acquaintances.

.

Sample 1-A2

r = 8, n = 50, 50 + 8 = 58, n + r - 1
50,51,52,53,54,55,56,57,58
(1),(2),(3),(4),(5),(6),(7),(8),(9)
[Each integer in first row here was shown paired with integer in second row here.]
You have to subtract 1 because there are only eight consecutive integers not nine. General: There are r consecutive and you need to subtract 1 to account for the extra integer.

Sample 2-A2

33,66,99, . . . , 1980: multiples of 3 and 11
(1980-33)/33 + 1
147/33 + 1
60 integers are multiples of both 3 and 11, so 181-60 = 121 integers.

Sample 3-A2

With 5 people, the number of acquaintances is only 0-4. You can never have 0-4 inclusive because one person cannot know anyone and someone else know everyone. Therefore, one number has to be duplicated. Then there are at least two people with the same number of acquaintances.

With n people, there can only be n - 1 acquaintances. There can be 0 to n - 1 acquaintances but there are n positions and n - 1 choices so there are at least two with the same number of acquaintances.

.

Sample 1-M1

n + r - 1
I added the number of consecutive integers to the lowest integer and subtracted 1 because it had already been counted as a consecutive integer. When counting, consecutive integers means the number between and including the first and last. But when given the smallest integer you are concerned with how many integers to get to the largest, so you add 1 less than the number of consecutive integers

Sample 2-M1

There are 181 multiples of 11 from 1 to 2000. The largest common multiple of 3 and 11 (i.e., 33) in the sequence from 1 to 2000 is 1980: 33, . . . , 1980. Then using the result shown in problem 8, (1980-33)/33 + 1 = 60. We also could have generated the value 60 by noting that 2000/33 = 60 remainder 20.

Therefore, there are 181-60 or 121 multiples of 11 and not multiples of 3 in the sequence of integers from 1 to 2000.

Sample 3-M1

If no one knows anyone else in the group, they all have 0 acquaintances and we've met the condition. Likewise, if all five people know each other, they each have 4 acquaintances.

More generally, the possible numbers of acquaintances for five people is the set {0,1,2,3,4}. If one person has 4 acquaintances, that person knows the other four people, so none of these five can have 0 acquaintances. Likewise, if one person has 0 acquaintances, that person knows none of the other four people, so no one in the group can have 4 acquaintances.

Therefore, looking at the choices {0,1,2,3,4}, if someone knows 4 people, 0 cannot be chosen; if 0 is the number of acquaintances for one person, 4 cannot be chosen. Therfore, from the five possible elements in the set, only four can be used in any one situation. If five people have to select from four choices, we must have at least one value selected more than once. Referring to the pigeonhole principle, the four choices represent the boxes and the five people are the pigeons.

Since for five people there are four choices, in a group of n people there will be n - 1 possible number of acquaintances, and by the PHP at least two people will have the same number of acquaintances.

.

Sample 1-M2

n + r - 1 is the largest
Example: r is 5: n, n + 1, n + 2, n + 3, n + 4
When starting with n and listing consecutive integers, the largest integer will be obtained by adding 1 less than the number of consecutive integers required to the smallest which is n.

.

Test Questions and Sample Solutions

.

### Question #5

.

In the expansion of the binomial for any term state the restrictions on a and b.

At Bagwanna State University, students' programs of study must include course credit in mathematics, science, English, history, and the arts. Each student must complete a total of exactly 46 credits that include these areas of study. Furthermore, no less than 6 credits must be in mathematics, at least 8 credits must be in science, and 10 or more credits must be from English. How many different student programs, based on credits earned, can be designed under these restrictions?

.

Sample 4-L1
(2 of 4 points earned)

The sum of a + b must be equal to T. a + b = t

Sample 5-L1
(10 of 15 points earned)

>= 6 math
>= 8 science
>= 10 English =

24 determined
22 left to place (46-24)
3 determined
4 dividers
C(22+3-1,5-1)
C(24,4)

.

Sample 4-L2
(2 of 4 points earned)

a + b = t

Sample 5-L2
(10 of 15 points earned)

C(27,5) How many ways can I design a program with the 22 remaining credits and the six categories? I have 22 credits and 5 borders to place, thus I have 27 items and I must choose 5 places to place my borders.

C(27,5) represents the number of different student programs that can be designed under the given restrictions.

.

Sample 4-A1
(3 of 4 points earned)

(n + m)(n + m)(n + m) . . .

a + b = t

a >= 0
b >= 0

but a & b are both = 0 if and only if t = 0

Sample 5-A1
(12 of 15 points earned)

C(26,4) or 14,950 10 + 8 + 6 = 24 accounted for; 46 - 24 = 22 left to determine: C(26,4)

Because 24 hours have been accounted for there are 22 left to determine. I combined these 22 hours with the 4 dividers and chose the placement of the four dividers to determine the number of hours for each area of study. There are C(26,4) possible different student programs.

.

Sample 4-A2
(3 of 4 points earned)

The sum of a and b must equal t. A or B may not be larger than t.

Sample 5-A2
(12 of 15 points earned)

C(29,4)
M S E H A = 46
Since the restrictions are that Math needs 6, Science needs 8, and English needs 10 or more credits, we can first place these minus one to account for solving over positive integers. We now have 25 credits for the 5 subjects. Based on this we must solve over the positive integers, since each subject needs at least one. Using C(m + r - 1, r - 1) where "m" equals the desired responses (25) and r - 1 is the number of dividers needed to separate the 5 subject areas we conclude that C(25 + 5 - 1, 5 - 1) or C(29,4) represents the number of different student programs to design.

.

Sample 4-M1
(4 of 4 points earned)

a + b = t

Note:
If T < 0 then the answer will be .
If T > 0 then a and b will be 0 or positive.
If T = 0 then the answer is 1.

Sample 5-M1
(15 of 15 points earned)

C(24,4)

M >= 6, S >= 8, E >= 10, H >= 1, A >= 1
M + S + E + H + A = 46
M + S + E + H + A = 20

Now able to select over non-negative numbers C(n + k -1, k - 1), 20 + 5 -1, 5 - 1

C(24,4)

.

Sample 4-M2
(4 of 4 points earned) where J represents the set of integers

Sample 4-M2
(15 of 15 points earned)

C(24,4)

M >= 6 (M represents mathematics)
S >= 8 (S represents science)
E >= 10 (E represents English)
H >= 1 (H represents history)
A >= 1 (A represents the arts)

I am assuming there are 1-credit courses in history and the arts because it is not specified and a student must have course credit in all 5.

M + S + E + H + A = 46, but 26 credits are accounted for by restrictions so (46 - 26 = 20)

M + S + E + H + A = 20.

This equation can be solved over the non-negative integers now. C(24,4)

(There are 5 categories with 4 dividers and 46 tally marks must be placed with the placement of some pre-specified.)

.