A Black squirrel carries 1 nut at a time and a Grey squirrel carries 2 nuts at a time. If there is a pile of N nuts, how many possible ways can the two squirrels carry these nuts back to their home? For example, if there are 3 nuts, then there are 3 ways:
Different variations of this problem use more squirrels, different numbers of nuts that each can carry, and of course usually start with asking the student to figure it out for a small number of nuts first.
So, how do we go about figuring this out? Well for a small number of nuts, you can just brute-force it, but as the number of nuts gets bigger, there are a lot of combinations to work through. So let's first start with the brute-force method for a small number of nuts, then we'll see how we can figure out more intelligently the number of combinations for larger numbers of nuts.
The brute force approach really means just thinking through every possible combination, which isn't hard but it's easy to miss a combination here or there. So the trick is doing it systematically. A couple ways to do this would be, for example:
The first 3 approaches are the ways that I've seen most people first try to solve the problem, or at least the easier to explain. The last approach is actually the one that pays off in solving this problem. But first, let's go over the first 3, which are basically keeping the number of trips of one squirrel constant to reduce the problem. Then we'll go over the last approach.
Grey squirrel takes 0 trips, then 1 trip, then 2 trips, etc.
The way I usually explain this is by drawing a table to help the kids think through systematically and not miss any combinations. And a simple notation for each combination helps quickly determine if you're double-counting or if you're missing a combination. (Credit for this notation goes to one of the 4th graders that I was working with. ) Let's use 1s and 2s to denote each Black and Grey squirrel trip, for the example above with 3 nuts, the three combinations are:
What nice about this notation is that you can quickly validate each combination (the numbers have to add up to 3 in this case), and you can quickly spot a duplicate combination.
So going back to our "Grey squirrel takes 0 trips, then 1 trip, then 2 trips" let's say the total number of nuts is 5:
For a total of 8 ways for 5 nuts. By far a fail-safe way of figuring out the total number of combinations, but at least it breaks down the problem to more manageable smaller problems. And breaking down the problem by Black squirrel trips or by starting with the most number of trips instead of the fewest is pretty much the same, so I won't go over these.
Black squirrel takes first nut, then Grey squirrel takes first nut
Another systematic way to approach this problem is to break it down by who goes first, for example, first the Black squirrel takes the first nut, and you figure out all combinations. Then you have the Grey squirrel take the first two nuts and you figure out all combinations. In other words, using the notation above, you're going to find all combinations where the first value is 1, then all combinations where the first value is 2. And taking it a step further, you can find all combinations where the first two values are 1,1 then where the first two values are 1,2, then where the first two values are 2,1 and where the first two values are 1,2, etc.
So if the total number of nuts is 5:
Continue to solution