Matt Enlow (math teacher in MA) posted a fascinating problem online today, one he thinks of when storing all those plastic bags from the grocery store. You shove them so they all lie in a single bag, and throw that bag under the sink. Here’s the question: how many different ways can you store these 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 for clarification:
Can you figure out how many ways for 6 bags? 13 bags?
You are now officially nerdsniped.
A number of people had trouble calculating 4 bags correctly, so I’ll post the number of ways 4 bags could be stored after the jump at the bottom, so you can at least see if you’re starting off correctly…
Additional Information: Matt and I figured the solution to this problem together on twitter. It was an interesting thing. We didn’t really “collaborate,” but we both refined some of our initial data (for 5 bags, he undercounted, and I overcounted). It seemed we were both thinking of similar things — one idea in particular which I’m not going to mention, which was the key for our solution. What blew my mind was that at the exact time Matt was tweeting me his approach that he thought led to the solution, I looked at my paper and I had the exact same thing (written down in a slightly different way). I sent him a picture of my paper and he sent me a picture of his paper, and I literally laughed out loud. We both calculated how many arrangements for 6 bags, and got the same answer. Huzzah! I will say I am fairly confident in our solution, based on some additional internet research I did after.
Obviously I’m being purposefully vague so I don’t give anything away. But have fun being nerdsniped!
Update late in the evening: It might just be Matt and my solution is wrong. In fact, I’m now more and more convinced it is. Our method works for 1, 2, 3, 4, 5, and 6 bags, but may break down at 7. It’s like this problem — deceptive! I’m fairly convinced our solution is not right, based on more things I’ve seen on the internet. But it is kinda exciting and depressing at the same time. Is there an error? Can we fix the error, if there is? WHAT WILL HAPPEN?!
The number of ways 4 bags can be stored is… (after the jump)
4. I promise you this is right, so if you only have 3, you’re missing one!
Continuous Everywhere but Differentiable Nowhere 
I see that the problem has been pulled from Brilliant. I take it that is due to the flaw you two discovered. I’m curious as to whether you’re willing to post the work you did that proved problematic, as that sort of thing can be HIGHLY instructive for students (and non-students, too).
Just to see if I’m heading in the right direction so far: I found four arrangements for four bags, as you claimed, and I found seven arangements for five bags. About to look at six and seven when I get home and have more than an envelope to play on. My first thought before trying anything was that this would have something to do with power sets, but now that doesn’t appear fruitful. Until I try six and seven, not sure I’ve got much of an inkling here, but this is definitely fun. Thanks for posting.
There are 9 arrangements for five bags. The sequence I got initially looked like:
1,1,2,4,9,20,49,117, …
That’s wrong for 7 and 8 though because I’m over counting. It took me a while to understand where the over counting happened, but now I’m convinced I have the right answer.
Spoilers: https://oeis.org/A000081
Help me out, I’m not seeing the over counting. How did you see where it’s happening?
My answer is the same as your original sequence.
I see it now! The overcounting starts happening at 7 bags, because of the 3,3 trees under it. There are not 4 ways to make a 3 and a 3, because there’s a duplicate. There are only 3 ways.
Same thing can happen anytime you have identical trees under the root.
I will modify my solution!
Yes, that’s exactly what I figured out. For 8 bags, the 3,3,1 tree has a duplicate.
This gets worse at the 10-bag solution when there is a 1, 4, 4 tree with 6 duplicates and a 3, 3, 3 tree with (I think) 16 duplicates.
It gets even harder when duplicates nest within duplicates.
TRICKY.
while i was trying to finish my taxes, i gave this problem to my 7-year-old to keep him occupied. he had a blast working on it! i was so impressed when he got close to the right answer — this was a challenging problem! thanks for sharing.
That was a challenging problem. Perfect example of the role of recursion. I created a program to generate solutions. Removing the duplicates was not as hard as I thought. I switched from the geometric progression of the repeating terms to the combination formula.
Greg
Had a beautiful, simple-ish explanation typed in here. And then my pattern broke, rendering said explanation useless. Nerdsniped again!
I came up with the following way of counting. In the following explanation, the number itself represent a straight up stack of bag inside bag. E.g
1 = Just 1 bag
2 = 1 + 1 = 1 bag inside another bag
3 = 1 + 1 + 1 = 2 + 1 = 1 + 2
For bags adjacent to each other, I use the symbol @. So
1 @ 1 = 2 bags, 1 adjacent to another
1 @ 1 @ 1 = 3 bags, all adjacent to each other
For ‘n’ total number of bags, we want to have all possible combinations of ‘n-1’ total bags using + and @. So for 4 total number of bags, we need all possible combinations of 3 total bags using + and @. These are:
1 + 1 + 1 = 3
1 @ 1 @ 1 = 3
1 + (1 @ 1) = 3
2 @ 1 = 3
So the 4 combinations for 4 total bags are obtained by adding 1 to each of the above using the + operation, i.e. putting each one of these inside another bag.
1 + (1 + 1 + 1) = 4
1 + (1 @ 1 @ 1) = 4
1 + (1 + (1 @ 1)) = 2 + (1 @ 1) = 4
1 + (2 @ 1) = 4
Similarly for 5 total bags, need to find all combinations of 4 bags using + and @. Fortunately we already have the 4 above. We can generate additional 4 by putting the one extra bag as an adjacent bag.
1 @ (1 + 1 + 1) = 3 @ 1 = 4
1 @ (1 @ 1 @ 1) = 4
1 @ (1 + (1 @ 1)) = 4
1 @ (2 @ 1) = 4
The only remaining one is 2 @ 2 = 4. So that makes it 9 combinations for 5 total bags. So my sequence so far is 1, 1, 2, 4, 9
I haven’t derived a general formula yet. Am I on the right track?
You are! (I didn’t have a chance to look through the work, but your sequence so far is good.) The question is what do you get for 7 bags. I was correct for up to 6 bags, but then my pattern/work broke down at 7. Le sigh.
Anyone find an equation for the stuffing sacks?
The Online Encyclopedia of Integer Sequences link (https://oeis.org/A000081) has a few different equations for the sequence.
Personally, I like this one:
A(x) satisfies A(x) = x*exp(A(x)+A(x^2)/2+A(x^3)/3+A(x^4)/4+…)
It defines the sequence in terms of itself.
Mark