## Penn Alexander: subset counting and Gray codes

I’m volunteering again this year with the middle school math club at Penn Alexander. I’m going to try to be better this year about posting what we do each week, for posterity’s sake and in case it inspires anyone else!

Last week, we got out a huge bucket of red, blue, yellow and green square tiles, and I started by asking them to count the number of subsets they could form from red, blue, and yellow tiles—I didn’t use the word “subset”, though, I just demonstrated what I meant with a few examples. This prompted immediate wild guessing (six! nine!) but also some good questions, such as whether duplicate tiles were allowed (no) and whether the order of the tiles mattered (no). One surprise was that I really had to encourage them repeatedly to get out enough tiles that they could actually form all the subsets right there in front of them; initially most were sitting there with three tiles and just trying to move them around and count in their head. If I did it again I would spend more time encouraging them to think about systematic ways to ensure that they weren’t missing any possibilities.

Anyway, eventually they all agreed on seven, and then we talked about including the empty subset. Next we added the green tile and they eventually all agreed on sixteen. They were able to count the subsets with one and two tiles in their heads by this point, and then they all pretty quickly caught on to the pattern (that the number of subsets doubles each time you add a new tile) although only a few understood why this was so.

Finally I asked them whether they could take all the three-tile subsets and put them in an order so that any two adjacent subsets differed only by the addition (or deletion) of a single tile. This was the hardest part to explain, and I had to demonstrate what I meant several times. But eventually most of them understood what we were trying to do, and a few did figure it out—one student even figured out an ordering for all sixteen four-tile subsets, and with a bit of prompting from me figured out a general algorithm for finding orderings for even more tiles!

The inspiration for this activity came from this website, where you can find a bunch more information and resources.