There are many ways to organize work on this project, depending on the
background and focus of your class. What follows are some ideas for getting
started and progressing through the work with classes of a few different
backgrounds.
Introducing the Project
If your class has a background in computer science or has a programming focus, you
may want to start with the context of a new ordering of the binary numbers (see the
Extensions) to motivate work on the project. Students can play with the problem of
re-ordering the binary numbers for a few minutes; you can then explain that solving
a problem in a different context will actually help them solve the binary
number problem. Then, introduce the subsets problem as stated in the project
page.
If your class has a background in combinatorics, they may have studied ways to
count subsets. You can lead into this project by asking them how many subsets a set
of three, four, or n elements has. A natural follow-up question is, "Suppose I don’t
just want to know how many; I actually want to write them all down. How
could I do it?" Students will probably suggest something like, "List all the
one-element subsets first, then the two-element subsets, and so on." You can
push them to refine this method so that they know (for example) when they
have listed all the two-element subsets without repeating any or leaving
any out. This will probably take most of a class day or more, if you allow
students to refine and generalize their methods for listing all the subsets of an
n-element set. Finally, explain that you want to put a new constraint on
the listing of the subsets: As you move from one to the next on your list,
you want to add one new element or remove one old element. Suggest that
they start by working on sets with small numbers of elements (one, two,
three, or four), with the goal of creating a general method for finding such a
listing.
If your class has no background in the ideas presented here, that’s fine; just start
a few steps back. Review what a set is (simply "a collection of objects" will do)
and what a subset is (any set of elements that all come from the original
set, including Ø--the empty set--and the whole set). Make sure students
understand that in a description of a set, the order of the elements does not
matter (i.e., the sets {a, b} and {b, a} are the same). This will be a potential
cause for confusion later in the project, since the order the subsets are
listed will matter, but the order of objects listed within a subset does
not.
Ask students how many subsets there are of the set {a, b, c}, and let them
work on that question for quite a while. Students without a background in
combinatorics will likely try to come up with a strategy for listing all the subsets,
which is fine, since creating a particular kind of listing is the point of this
project. Give students plenty of time to work on this problem, and ask them to
convince themselves that they have not left off any subsets or listed any
twice. Finally, ask several students to share their strategies with the whole
class.
You may find that students will omit Ø and the complete set {a, b, c} in their
listing. You can explain that Ø is a subset of any set at all, and that the whole set
indeed fits the definition of subset. (If students resist calling the whole set a subset of
itself, you may want to introduce the term "proper subset"; explain that it is an
important distinction they are making, and one that mathematicians care about as
well.)
You may want to spend a couple of days on work like this (i.e., counting and
listing all the subsets for sets of one, two, three, and four elements). Before digging in
to the project work, it would help students to know that there are 2n subsets for a
set with n elements and to be able to reason why that is--either through a
recursive argument of building up bigger and bigger sets and seeing the
number of subsets double, or through a more combinatoric argument that each
element is either in or not in a given subset, giving 2n possible choices (two for
each of the n elements). It’s also helpful to know that the subsets can be
split exactly in half by considering "sets that contain x" and "sets that
don’t contain x," where x is an element of the original set. All of this will
likely come up in the course of working on the project, so it’s up to you how
much time you want to spend up front exploring sets, subsets, counting, and
listing.
Working on the Project
Depending on how familiar students are with finding
recursive solutions, this project may take anywhere from a couple of days to several
weeks of class time. After students have had a day or so to come up with a suitable
listing (or several suitable listings) for sets of three elements, ask them to work with
other small sets, with the explicit goal of finding a general method. If students are
struggling with sets of four and five elements, you may want to spend one day of
class time on the
Warm Up Problems, talking explicitly about how to move
from a set with one element to a set with two, from two to three, and so
on.
If students work on the warm up problems, you may also want to introduce the
graph-theoretic approach to the problem, and ask students to work on finding
Hamiltonian paths (a path that visits each vertex exactly once) along other graphs to
get used to the ideas there.
Closure
Once students have convinced themselves that they can always find a
sequence that works, there are many options for bringing closure to the
activity:
- Ask students or student groups to present their different approaches to
the class or write a final paper. A nice touch is to ask students to include
some early work in the final product, to explain how they initially thought
about the problem and how their thinking evolved.
- For students who can program, a nice final product is a program that will
take as input either a set or a number of elements in a set and output the
desired sequence of subsets. Note that a programming language with some
list-processing capabilities (Mathematica, LISP, or even Logo) makes this
task much easier!
- If you started with the question about binary numbers, have your students
return to that question and see how the listing of subsets allows them to
create such an ordering for the binary numbers.
- Have each student take a different extension problem to work on for a
week or more on their own, and then present their solution to--or at least
progress on--that problem to the class. (This is particularly nice, because
it reduces redundancy in the presentations.)
