You can demonstrate possible combinations by actually pushing the “buttons” on
the lock you’ve drawn. Make sure students understand the task (to count the number
of combinations and see if it lives up to the billing of “thousands”) and the rules for
the presses which are:
- Each button may be used at most once.
- Each push may include any number of buttons, from one to five.
Depending on the level of you class, you may want to introduce the two fundamental rules of counting: One way to accomplish rules (1) and (2) is to overcount and adjust. You can also, as a class, list all the combinations for a 2-button lock. There is a small enough number to list them all out, but there are enough to get at some common points of confusion: - The null combination counts as a combination (the door is unlocked).
- Order counts between presses, but not when you press more than one
button at once.
So the press combinations:
are the same, and should not be listed separately. But, the combinations:
are different, and they should each be listed. - You don’t have to use all the buttons. (|1| is a reasonable combination.)
Allow the students to spend the majority of the period (at least 30 minutes) exploring ways to find the number of combinations for a 5-button . You can set the students to work as individuals or in small groups of 2 or 3. Usually, students will start out by trying to write down all the combinations for a 5-button lock. Soon, they will discover they need some systematic way of counting the combinations. As you walk around and observe students work, pay attention to students with creative, elegant, or clear systemmatic approaches, and be sure to ask them to share their work at the end of class. Also, be prepared for some groups or students to be stuck, or to think they’re done quickly. (Often, they’ll shout out “152!” as an answer without any explanation.) It can be challenging to convince them to keep working without saying they’re wrong or giving away the answer. For these groups of students, it helps to start them on a strategy, especially one that will help them see any combinations they’ve missed. See the Hints document for more details on each of these: - Think of locks with any number of buttons. Solve the problem for 1, 2, 3, and 4 button locks. Make a table of combinations, and look for patterns.
- Classify the combinations by how many buttons they use. It is especially helpful to combine this with (1) above.
- Break down the possible combinations into how many “presses” they have. One press means pressing down one or more buttons simultaneously. So the combination |2|3 4 5|1| is three presses.
- Look at the shape of the combinations. How many look like | * *| * |, or | * | * *| * |, and so on.
- Write a program in a computer algebra system to generate the actual combinations. Then, all that is left to be done is count them.
- Make a list of all the combinations on a four-button lock and come up with a systematic way to extend these to the combinations of the 5-button lock.
- The combinations come in two types: those that use all five buttons and those that use fewer. Count these separately.
If a group thinks they are done, but have only counted the combinations that use all five buttons, for example, you might say, “Some combinations don’t use all 5 buttons. So there are two kinds of combinations, and you’ve counted all of one kind. How can you count the others?” If a group is completely stuck, working with a smaller number of buttons is helpful. You can also encourage them to fill in a table like the one here, and to look for patterns.
You should judge how much your students need in the way of hints or ideas. “Try a table!” might be enough for a group that has already been looking at locks with different numbers of buttons. Other groups may need more structure to get started. At the end of the first day, ask several groups to share strategies but no answers. Ask how they organized their work, what questions they asked themselves, and so on. If you have one or two strategies that you want to be sure students see, you can ask groups to present them or you can explain them yourself. You might also spend some time talking about approaches that are similar to each other, to get students thinking more broadly about kinds of approaches. You might decide to encourage students to pursue one of the five main approaches: - A decomposing strategy: How can the combinations on n buttons be described by combinations on n - 1 buttons? How can combinations with m pushes be counted by combinations with m - 1 pushes?
- An extending strategy: How can combinations on n - 1 buttons be extended to combinations on n buttons?
- A direct calculation: Concentrate on the numbers of buttons used.
- A direct calculation: Concentrate on the numbers of pushes used.
- A combinatorial strategy: Find all the different shapes of pushes and use combinatorics to count the combinations for any particular shape
## 2 After Day 1Where you go after the first day of the project is up to you. Here are some approaches teachers have used in the past: ## 2.1 Finish IndividuallyAfter the first day of group work, students are asked to complete the project individually. Encourage the students to ask questions as they arise. They usually turn in a rough draft - explaining their approach, their answer, and any questions that haven’t been addressed - a week or so after the initial work. This keeps the students working on the problem and prevents losing momentum from the first day.The rough drafts can help you see if there are major misunderstandings or common mistakes students are making. You can spend some class time, if necessary, going over these issues when students get comments on their rough drafts. They then finish up the projects on their own. ## 2.2 Continuing Group WorkYou may want to devote a second day of class time to students working in their groups. At the end of the first day, they may see connections to other stragies and get ideas for how to continue their work. On the second day, encourage each group to pick one of the strategies that was discussed and pursue it to get an answer for the number of combinations of a 5-button lock.Many groups will arrive at a numerical answer by the end of the first day, or early on during the second. Often, they do this by a brute-force (though clever) listing of the combinations. Allow students with different answers to compare methods to see where under and over counts may have happened. Once the students agree on the numerical solution, you can ask them to start making some connections and following up on other questions: - Can you prove that your answer is right? That is, how can you be sure you haven’t missed any combinations or counted any twice?
- How could you generalize the solution? Can you find the number of combinations for 3-, 4-, and 6-button locks? n-button locks? (see Extension Problems)
- One student said they only have to count the combinations that use all five of
the buttons. They double this answer, and claim they have the total number of
combinations. Does that fit your data? Does it work for other numbers of
buttons? Can you explain why it happens? In order to answer these
questions, consider this list of combinations for a three button lock:
Combinations for a 3-button lock Combinations using Combinations using 3 buttons less than 3 buttons |1|23| no pushes |2|13| |2|1| |3|12| |12| |1|2|3| |13| |1|3|2| |23| |2|3|1| |3|2| |3|1|2| |3|1| |3|2|1| |1|3| |23|1| |1|2| |13|2| |1| |12|3| |2| |2|1|3| |3| |123| |2|3|
- Finding a one-to-one correspondence between the combinations that use all the buttons and those that do not use all of the buttons is one way to show that the two groups have the same amount of elements. Can you find an algorithm to map each element of the left column to one and exactly one element of the right column? Would this rule work for a 5-button lock? Would it work for an n-button lock? How does this information help to answer the above questions?
For students who know about elementary combinatorics and/or students who have worked on the trains project (see Warm Up Problems), you might ask them directly how they could use the formula to help them organize their work and solve the problem. For more advanced groups, you can ask them to come up with a closed form or recursive formula for the number of combinations on an n-button lock. You can also encourage them to come up with their own extensions to the problem by changing the question in some way (perhaps changing one or more of the rules about pressing buttons). ## 2.3 Filling in and Coming BackIf your students don’t yet have the background to tackle some of the more general solutions, you can interrupt work on the project (make sure it is well-documented first) for a day or more of “background building.” You might want to cover some of these topics:- the notation for binomial coefficients and application to the binomial theorem,
- summation notation,
- the in terms of factorials,
- some other work with arithmetic and geometric series,
- the technique of counting objects by putting them in 1-1 correspondence with better understood sets, and
- counting by extending known sets, for example counting the number of n-digit numbers using only 1s and 2s by building them up from the single digits 1 and 2 in a systematic way.
When you come back to the problem, ask students to find a way to use one or more of these tools as they work on it. |

Translations of mathematical formulas for web display were created by tex4ht. |