Identical Boxes

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Riya has five different items and two boxes that look exactly alike, and neither box may be empty. She uses the formula for different boxes: two to the power five, minus two. Thirty ways. Her friend Kabir works on the same items and the same boxes, and he says fifteen. Same items, same boxes, but half the answer. So who is right? Something to think about, right? Today we find out, with a new idea: identical boxes. In JEE, questions on putting things into identical boxes come up often. So, let's begin.

0:40Identical boxes: what still matters?

So, what do identical boxes really mean? Picture two boxes that look exactly alike: no names, no labels, no colours. Fill them in some way, and then swap the two boxes. Tell me, is that a new way? No, it is not! Correct. Nobody can even tell that the boxes moved. So, with identical boxes, swapping two boxes gives nothing new. Okay? Now, when the objects are different, only the groups themselves matter: which objects sit together. Not which box holds them, because the boxes have no names. Right? And when the objects are identical too, even two groups of the same size look alike. So only the sizes of the groups matter: how many objects go in each box. Clear?

1:26Different objects, identical boxes, none empty

Alright, first case: different objects into k identical boxes, with no box empty. The letter k is just the number of boxes. Since the boxes have no names, all we do is split the objects into k unnamed groups. That's it. Okay? Let's try four different objects and two boxes. First, group sizes three plus one: choose the three objects that go together. Four C three, that is four ways. That capital C, with four at its top left and three at its bottom right, is four C three: the number of ways to choose three things out of four. With me? Now sizes two plus two. Choose two objects for one group: four C two, that is six ways. So, six, right? Oh no, careful! Pick objects one and two, and three and four are left. Pick three and four, and one and two are left. It is the same split! The two groups have the same size and no names, so every split is counted twice. So, four C two, over two: three ways. Got it? So, two boxes give four plus three: seven ways. And with three boxes, the only sizes are two, one and one. Choose the pair: four C two, six ways. The other two objects sit alone, one in each box. Right? Now, for five different objects, keep these values in mind. With k equal to two, the answer is fifteen; with k equal to three, twenty five; and with k equal to four, ten. Two of these values, we will prove in today's examples. Okay? Now suppose a box may stay empty. Then we add the cases by the number of boxes actually used. Four objects in three identical boxes: all in one box, one way; two boxes used, seven; three boxes used, six. One plus seven plus six: fourteen. Clear?

3:28Identical objects into identical boxes

Now the last case: identical objects into identical boxes. The objects look alike, and the boxes look alike, so only the sizes matter. We write n, the number of objects, as a sum of positive parts, one part for each box that gets objects. Such a sum is called a partition of n, okay? Quick question. With identical boxes, is three plus one different from one plus three? No, not at all! The boxes have no names, so the order of the parts means nothing. So always list the parts in decreasing order: three plus one, never one plus three. This way, nothing gets counted twice. Got it? Now take four objects and two boxes again, with no box empty, but this time the objects are identical. The sizes are the same as before: three plus one, and two plus two. But now each pattern of sizes is just one way. So, two ways, not seven! Big difference, right? And when a box may stay empty, n is split into at most k parts, not exactly k parts. Clear?

4:33Example 1: 5 different items into 2 identical boxes

Now, remember Riya and Kabir from the start? Let's settle it. In how many ways can five different items be put into two identical boxes, with neither box empty? Pause the video, and try it first. Done? Okay, let's check. First, pretend the boxes are different. Each of the five items chooses one of the two boxes: two to the power five, that is thirty two. The small five at the top right is the power. Remove the two ways where one box stays empty: thirty. That is Riya's answer. Right? But our boxes are identical. Take any one of those thirty ways, and swap the two boxes. Do we get a new way? No! Very good. Riya's thirty counts every split twice: once as it is, and once with the boxes swapped. The two groups can never be equal, since the items are different and no box is empty. Okay? So, divide by two. Two to the power five, minus two, all over two: fifteen. Kabir was right! Mystery solved. Clear? Let's check it with group sizes, the way we just learnt. Sizes four plus one: five C four, five ways. Sizes three plus two: five C three, ten ways. Five plus ten, fifteen again. Perfect!

5:55Example 2: 5 toys in 3 identical boxes, 10 sweets in 3 heaps

Now a harder one, with two parts. In how many ways can five different toys be put into three identical boxes, with no box empty? And in how many ways can ten identical sweets be split into three non-empty heaps? Pause and try. Hint: list the group sizes first. Done? Okay, let's check. Toys first. Five toys, three boxes, none empty. What group sizes are possible? Three, one, one; or two, two, one. Correct! Take three, one, one first: choose the three toys that go together, five C three, that is ten. The other two toys sit alone, so there is nothing more to choose. With me? Now sizes two, two, one. Choose the toy that sits alone: five ways. Then choose a pair from the other four: four C two, six ways. Five times six, thirty, right? No, no, wait! The same trap again. The two pairs have the same size and sit in identical boxes, so each split is counted twice. Five times four C two, over two: fifteen. Okay? So the toys give ten plus fifteen: twenty five ways. Clear? Now the sweets. They are identical, and the heaps have no names. So what matters now? Only the sizes, yes! So we need the partitions of ten into exactly three parts, in decreasing order. Topper's trick: start with the biggest part as large as possible, and come down. Eight, one, one. Seven, two, one. Six, three, one. Six, two, two. Got it? Then five, four, one. Five, three, two. Four, four, two. And four, three, three. The biggest part cannot go down to three, because three plus three plus three is only nine. So we stop here. Right? Count them: eight ways. So, twenty five ways for the toys, and eight for the sweets. That's it! Very good!

8:06Quick revision: unnamed groups and partitions of n

So, quick revision. Identical boxes: swapping two boxes gives nothing new. Different objects: split them into unnamed groups, and divide out the repeats when groups have equal sizes. Identical objects: count the partitions of n, with the parts in decreasing order. Now go and try the practice problems on this page. You can do them, I am sure. All the best!