I came across an interesting problem posted by a fellow teacher. Think about all those plastic bags you get from the grocery store. Say you shove them into in a single bag, and throw that bag under the sink. How many different ways can you store those bags?
For 1 bag, there is only 1 way.
For 2 bags, there is still only 1 way.
For 3 bags, there are 2 ways.
Here is a picture to illustrate:
How many ways for 4 bags? 5? How about 20 bags?
Give the problem a try for 4 bags. Once you think you have an answer, click here to confirm.
If you want, I encourage you to try to find the number of ways for 5 and 6 bags.
As I started to try to find all the combinations for 5 bags, I found that drawing the individual bags became cumbersome. I wanted a better method of diagramming. Ready and waiting was my trusty friend, graph theory.
I represented the bags as nodes and connected 2 nodes if one bag contained the other. Here is what the graph would look like for the 1, 2 and 3 bag cases:
Here is the drawing for 4 bags, again showing that there are only 4 ways of stuffing the 4 sacks:
Before we make the jump to 5 bags, we need to explore the graph theory representation a bit more. Consider these 2 different drawings, do they represent the same situation?
On one hand, the drawings are clearly different. One has a branch going to the right and one has a branch going to the left. On the other hand, if we draw out the stuffing situation that they represent, the two situations seem identical:
Indeed, the reason these 2 stuffing arrangements are the same, is because it doesn’t matter what order the 2 smallest bags are in. The only thing that matters is which bag they are contained in.
To visualize this with our graph, we are going to add a rule. You can transform the graph by dragging around the nodes, as long as you do not disconnect the lines. As you can see, I can easily transform the left graph into the right graph; showing they represent the same situation.
Using this rule, and trial and error, I was able to produce all 9 different arrangements for 5 bags:
I challenge you to try to find all of the combinations for 6 bags. Hint: the answer is larger than 14 and less than 25.