Illinois State University Mathematics Department

MAT 409: Topics in Algebra and Combinatorics for K-8 Teachers

Summer 2006
Dr. Roger Day (

Test #1
Possible Solutions


Set D contains the following digits: {0,4,8}; set A contains the following letters: {E,U,X,Z}; set T contains the following icons:

(a) Lymmytra will choose one item from among those contained in the three sets and write a poem about it. How many choices does Lymmytra have as the focus of her poem? (3 points)

Solution: 12 choices
The three sets are mutually disjoint and we seek one element from among them. Add the number of elements in each set.

(b) Maxwell imagined the 3-symbol codes that could be created using first a digit from D, next a letter from A, and finally an icon from T. How many different 3-symbol codes of this form could he create? (3 points)

Solution: 60 different codes
Create a three-symbol code in the order specified. There are 3 choices for symbol in first position, 4 choices for symbol in second position, and 5 choices for symbol in third position. Multiply in order to match each choice in each position.

(c) Natasha created a line-up of the 9 symbols from sets A and T. Her only requirement was that a vowel must be at the beginning of her line-up or a vowel must be at the end of her line-up, but not a vowel in both those positions. How many different line-ups are possible for Natasha? (4 points)

Solution: (2*7*7!)*2
There are two ways to place a vowel in the first position. now, to be sure vowel not placed in last position, place one of the 7 other symbols there. Finally, permute the remaining 7 symbols into the remaining (interior) seven positions. now, repeat this but start with a vowel in the last position.


While waiting to get fingerprinted at Livingston County Jail, I watched employees open a door after entering a code by pushing a digital keypad. The keypad is similar to the one shown here.

From my vantage point, I could see neither the door nor the keypad. I could see people pushing buttons from the side. After carefully watching several people enter the door, I concluded that the sequence of keystrokes they used looked like the figure shown below.

  • I knew the order of the keystrokes, as indicated by "first, second" and so on shown here.
  • I did not know which keypad was struck first.
  • I did know that the fourth push was directly below the first and second, and that the third and fifth pushes were directly below the fourth.

Based on this information, determine the number of different 5-number codes that could possibly unlock this door.

Solution: 96 possible 5-digit codes (6*2*2*2*2)
From the information gathered, the first push must have been on the 1/2 pad, the 3/4 pad, or the 5/6 pad. This is because we know there are two key pads below the starting key pad that must be pushed. Therefore, there are 6 choices for the first digit in the code. now, from here on, there are two choices for each digit in the code, because we know the button-pushing sequence that follows the first button push. For each of these remaining four pushes, there are two digits to choose from.



Thirteen people are gathered in a small, musty, windowless room. The lead-based paint is peeling off the walls. Among the thirteen people, the only first names represented are Allen, Betsy, and Carl. The only last names represented are Watson, Xian, Yates, and Zawalski. Each person has exactly one first name and one last name. Show that at least two people have both the same first and last names.

With exactly three first names and four last names possible, by the multiplication principle there are exactly 12 unique first-name/last-name pairs. But we have 13 people. By the pigeonhole principle, at least two of the thirteen people must have identical names.



Consider the letters in the word formalist.

(a) How many unique arrangements are there for the letters in this word? (2 points)

Solution: 9!
Permute the nine distinct letters in the word.

(b) How many arrangements exist if each arrangement must begin and end with a vowel? (2 points)

Solution: 3*2*7!
To begin, fill the first and last positions. There are three ways to select the first vowel and two ways to select the next. Now, we permute the remaiing seven letters in the seven positions available.

(c) How many arrangements exist if all consonants must be kept together? (3 points)

Solution: 3!*4*6!
Place the three vowels. There are 3! ways to arrange them. now, within and outside these vowels, there are four positions. Select one of the four positions and insert the group of six consonants. These consonants can be permuted, within their grouping, in 6! ways.

(d) How many 4-letter sets can be created using only the letters in the word? (3 points)

Solution: C(9,4)
From the nine letters in the word, select 4 to create a set. This is a combination of 9 items taken 4 at a time.



A school cafeteria contained a line of identical tables. Three boys who dined there were such bitter enemies that they could not be trusted to sit close to each other. No two or three of them could sit at the same table, and, in fact, the cafeteria monitor required that there always be at least one buffer table (occupied by others or not) between any two tables where these bitter enemies sat.

(a) What is the minimum number of tables, all in a line, that is required to meet the cafeteria monitor’s seating restrictions for the three enemies? (2 points)

Solution: 5 tables
With three boys, must have a table between each. minimum. So the least number of tables is 5:

Boy - - Table - - Boy - - Table - - Boy

(b) How many ways could the three enemies be seated, under these restrictions, if there were exactly 8 identical tables in line at the school cafeteria? (4 points)

Solution: P(6,3)
With 8 tables available, three must be used by the enemies and five as buffers. Begin by looking at the five buffer tables. Notice there are six places between or outside these five tables: _T_T_T_T_T_. Now permute the three enemies into three of these six spaces. This can be done in P(6,3) ways.

(c) Generalize the solution to (b) for B enemies and T tables. State any restrictions relating the quantities B and T. (4 points)

A generalization of the solution just stated is P(T-B+1,B). The restriction, determined from the permutation statement just stated or from similar analysis as carried out in (a) above, is that the total number of tables, T, must be greater than or equal to 1 less than twice the number of enemies: T >= 2B-1.



Four mediators listen to arguments and independently respond in one of three ways:

Agree, Disagree, Pass

Here are two examples of how the mediators report their responses to an argument:

Example A: 2-1-1                              

  • Mediator Amright:   Agree                    
  • Mediator Beelow:    Agree                    
  • Mediator Capstone:  Disagree                
  • Mediator Doormat:  Pass                      

Example B: 2-1-1

  • Mediator Amright:    Pass
  • Mediator Beelow:     Agree
  • Mediator Capstone:   Disagree
  • Mediator Doormat:   Agree


  • The aggregate response is the same for each example: 2-1-1 (2 agree, 1 disagree, 1 pass, expressed in that order).
  • The examples show two different ways the mediators independently responded, because at least one mediator in the group responded differently to the two cases.

(a) When only their aggregate response is considered, how many ways can the mediators respond to an argument? (5 points)

Solution: 15 aggregate responses
By brute force listing, we can determine all possible aggregate decisions:

Later in the course, we'll learn a more efficent strategy for solving such problems.

(b) When each mediator's independent response is considered, how many ways can the group of mediators respond to an argument? (5 points)

Solution: 3^4 = 81 ways
Each mediator can respond in one of three ways, and each mediator's response is independent of the others. Thus, we multiply the number of possible responses each can make in order to match up all possible ways the mediators can independently respond.


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