Mathematics Content: Counting Problems
Tuesday Evening Session, February 2011
Warm-Up Problem
(http://www.ece.ucsb.edu/~parhami/pres_folder/f38-counting-problems.ppt)
How many squares can you find that have four of these dots in the corner?
Now, remove exactly four dots so that no square can be formed with the dots that remain. (If you got that easily, try the same problem for the diagram below, but you will need to remove six dots.)
Counting Arrangements
(http://www.ece.ucsb.edu/~parhami/pres_folder/f38-counting-problems.ppt)
How many ways can you arrange the letters O, P, S, T? How many of these arrangements form ordinary English words?
The number of ways is 4 x 3 x 2 x 1 = 24. Explain this rule, and then use it to find the arrangements when there are five distinct letters to arrange.
Now, how many ways can you arrange the letters O, P, T, T? Explain your answer like the previous problem and test it on five letters with one repetition (O, P, S, T, T).
Now, how many ways can you arrange the letters O, T, T, T? Explain your answer like the previous problems and test it on five letters with a triple repetition (O, P, T, T, T).
Finally, how many ways can you arrange the letters O, O, T, T? Explain your answer like the previous problems and test it on five letters with two repetitions (O, P, P, T, T).
Counting with Patterns: Breaking Chocolate
(http://www.cut-the-knot.org/proofs/chocolad.shtml)
Divide an 8 x 4 chocolate bar into individual pieces using the smallest number of breaks. How many breaks did you need?
Counting with Patterns: Tower of Hanoi
http://www.superkids.com/aweb/tools/logic/towers/
The object is to move the disks to another peg in the smallest number of moves as possible. Note that a move consists of moving one disk from one peg to another peg, and that no disk can be placed on top of a smaller disk. How many moves does it take for ten disks?
You can use the applet http://www.superkids.com/aweb/tools/logic/towers/ to play the game. (This will work on the iPad. If you have a computer, a better applet can be found at http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm.)
If you know how many moves it takes to move 9 disks, how could you determine the number of moves to move 10 disks? Why does this work?
# of disks / # of moves1
2
3
4
5
6
7
8
9
10
Counting with Patterns: Compositions
(From a workshop given by Dr. Brian Hopkins, St. Peter’s College)
A combinatorial composition is defined as an ordered arrangement of nonnegative integers which sum to a number n. For example, there are four compositions of the number three, namely:
3
2 1
1 2
1 1 1
By looking at small cases and noticing patterns, determine the answers to the following questions. Once you find the pattern, you should explain why the pattern works.
· How many compositions of the number n?
· How many compositions of n do not contain ones?
· How many compositions of n only have odd numbers?
· How many compositions only have ones and twos?
Practice Problems
1. What are all the possible results of tossing a penny, a nickel, and a dime?
2. What are all the possible results of tossing three quarters?
3. How many different outcomes can you have if you toss a coin four times and the result from the first and second tosses are the same?
4. How many ways are there to distribute three balls (one red, one blue, one green) to 10 people? A person can get more than one ball. (Hint: Think of assigning a three-digit number to each arrangement.)
5. How many ways are there to order a meal consisting of one sandwich and one beverage at a restaurant that serves six different sandwiches and ten different beverages?
6. A true-false test contains 10 questions. In how many ways can a student answer the questions if every question is answered?
7. A true-false test contains 10 questions. In how many ways can a student answer the questions if some questions may be left unanswered?
8. A matching test contains 10 questions, and each answer must be used exactly once. In how many ways can a student answer the questions if every question is answered?
9. A certain Northeastern state has a strange rule for two-letter combinations that are legal for its license plates. To keep people's plates from accidentally spelling possible offensive words, they use the rule that any license plate that has a vowel as its first letter must also have a vowel as its second letter. How many two-letter prefixes are possible on license plates in this state? (They consider only the five letters A, E, I, O, and U to be vowels.)
10. How many five-digit numbers have all distinct digits and are odd?
11. On a TV show, there are 8 contestants. One of them (call her Jill) has won a prize dinner, and is allowed to select three of the others to join her. How many ways are there for her to make her selection?
12. A club with 17 members needs to elect a president, a vice president, and a secretary. Assume no one person can fill more than one role.
a. In how many ways can the offices be filled?
b. If Susan is not willing to be president, how many ways can the offices be filled?
c. If Sam will only serve as president if Mary is vice president, then how many ways can the offices be filled?
d. If the club's bylaws require that last year's vice president become president, then how many ways can the offices be filled?
13. An organization has 6 women and 10 men.
a. In how many ways can the organizations select a three-person committee if there are no restrictions?
b. In how many ways can the organizations select a three-person committee if the committee must contain at least one female?
PA3MSP, East Region, 1