Stuffing Sacks

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:

stuffing sacks 1

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:

Stuffing sacks 3

Here is the drawing for 4 bags, again showing that there are only 4 ways of stuffing the 4 sacks:

Stuffing sacks 4

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?

Stuffing sacks 5

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:

Stuffing sacks 5

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.

output_lBakYF

Using this rule, and trial and error, I was able to produce all 9 different arrangements for 5 bags:

Stuffing sacks 7

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.

 

 

Advertisements

Leave a comment

Filed under Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s