We began by looking at some approaches to the “How many subsets?” problem.
Listing out all of the subsets is a great way for students to get their hands dirty, and it allows for various patterns to emerge from the lists.
Here we have categorized the subsets in a natural way, by size. (Note: you can always have fun by arguing whether or not the empty set should count!). Lots of great symmetry here in this diagram, and patterns to explore. In particular, this is a great way to illustrate two fundamental principles of combinatorics.
First, is the number of ways to choose r things from n, so it makes sense that this number is the number of subsets of size r: to make a subset of size r from a set of size n, you need to really choose r of the n available things.
Furthermore, the various lists illustrate the relationship between and . How do you make a subset of size 1? Pick one of the elements from the five. But notice that what’s left over is a subset of size 4! Thus, for every way you can take one thing from five, there is a corresponding way to take four things from five.
Lastly, this problem provides a great opportunity to change your perspective. Instead of counting the subsets by size, think of naming every subset as a word consisting of Ys and Ns. Each letter of the word corresponds to a particular element of the set; Y means “Yes, you are in the subset”, and N means “No, you are not in the subset”. Here are some examples:
Every subset can be uniquely identified in this manner, and the beauty of this approach is that it is easy to count how many five-letter words there are of Ys and Ns: it’s just .
Not only is this a great way to illustrate the changing your perspective strategy, but you can also explore the basic idea of a combinatorial argument. In essence, we have counted the same thing (the number of subsets) in two different ways; thus, the ways must be equal! This basic idea gives us one of the fundamental combinatorial identities:
In the second half of the session we played around with a Mandelbrot Team contest on binary numbers. At the Mandelbrot Contest website, you can look at some sample contests (both individual and team), order books of past contests, and register for the official contests.
The individual Mandelbrot contests are usually pretty challenging, but they contain great problems, and the team contests are wonderful. The Mandelbrot Team contest takes a rich mathematical problem and breaks it down into 5 or 6 interconnected parts that range from simple exploration to sophisticated abstraction. These are a great way to build team dynamics in your classes, and a great model for constructing your own guided learning activities, too!
While working through the contest, we had some fun exploring binary representations, binary addition, and binary fractions! Larry showed us a cool way to find a numbers binary representation: the upside-down division method shown here. And he also showed us a fun way to convert fractions into binary by repeated multiplication by 2.