Identical Objects and Divisors

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Three identical apples, four identical oranges and five identical mangoes. In how many ways can you select at least one fruit? Twelve fruits, each one in or out: two to the power twelve, minus one. Four thousand and ninety five, right? Hmm. The true answer is only one hundred and nineteen! So where did the extra ways come from? And the same idea counts divisors in seconds. Questions like these come up often in JEE papers. So, let's begin.

0:35Identical objects: only the count matters

So, the key idea. When the objects of a kind are identical, picking this apple or that apple is the same thing, right? So a selection is fixed only by how many of each kind you take. Now tell me. From three identical apples, how many choices? Four! Yes, exactly! Zero, one, two or three apples. Taking no apple is also a choice. Clear? Now in general: p alike objects of one kind, q alike of another, and r alike of a third. So p plus one choices, then q plus one, then r plus one. Multiply them. And this count includes taking nothing at all. With me? But usually the question says: select at least one object. What do we change? Correct! Exactly one selection takes nothing at all: the empty one. So subtract one. Forgetting this minus one is a common slip, okay? And if some objects are different? Each different object is in or out: two choices. So each one multiplies the count by two. The cross on screen means times. Right? Now our fruit puzzle. Three plus one, times four plus one, times five plus one. The small dots mean times: four times five times six, one hundred and twenty. Minus one for the empty basket: one hundred and nineteen. Mystery solved! Two to the power twelve treated every single fruit as different, but identical apples are not different. Got it?

2:02Divisors: identical objects in disguise

Now the beautiful part. Write a number N as a product of powers of different primes: p one to the power a one, times p two to the power a two, and so on, up to p k to the power a k. The small numbers below each p are subscripts that label the primes; the a's on top are the powers; the dots mean the pattern continues. Now think. What does a divisor of N look like? Yes! It uses only these primes, each at most as many times as in N, okay? So for each prime, p sub i, we take zero copies up to a sub i copies. Those copies are just like identical apples! Right? So the number of divisors is a one plus one, times a two plus one, and so on, up to a k plus one. Taking no prime at all gives the divisor one, and taking everything gives N itself. Both are counted. Clear?

2:54Sum of divisors

Let's try three hundred and sixty: two cubed, times three squared, times five. Three plus one, times two plus one, times one plus one: twenty four divisors, without listing one! Okay? Now, what if the question asks for their sum? Twenty four numbers to add? Is there a shortcut? There is! One bracket for each prime, with all its powers: one plus two plus four plus eight, then one plus three plus nine, then one plus five. Multiply them out, and every term is one divisor, exactly once! Fifteen times thirteen times six: one thousand one hundred and seventy. Nice, right? In general, the sum of divisors is a product of such brackets. The big capital pi you see on screen means: multiply, and the small i below it means one bracket for each prime. Each bracket is one, plus p sub i, and so on, up to p sub i to the power a sub i. It adds up to p sub i to the power a sub i plus one, minus one, all over p sub i minus one. With me?

3:58Factor pairs, coprime factors and lcm

Now, in how many ways can N be written as a product of two positive factors, a times b, order not counted? Each divisor pairs with exactly one partner. So if d is the number of divisors, we get d over two ways. Okay? But wait. What changes if N is a perfect square? Very good! The square root of N pairs with itself. So add one before halving: d plus one, over two. Careful here, okay? Next, two coprime factors, with no common prime. Each prime power goes wholly to one factor: two choices for each prime. If k is the number of different primes, that is two to the power k ordered ways. Order not counted? Halve it: two raised to the power, k minus one. Clear? So three hundred and sixty: twenty four divisors, not a square, so twenty four over two, twelve ways. Three different primes, so coprime: two raised to the power, three minus one, that is two squared, four ways. Right? Last one: ordered pairs a, b of positive integers whose l c m, the least common multiple, equals N, okay? Careful, this a sub i is the power of the prime, not the number a. For each prime, at least one of the two numbers must carry the full power a sub i. Full power in a, and anything from zero to a sub i in b: a sub i plus one pairs. The same the other way round. But both full is counted twice, so subtract one: two a sub i plus one choices. Multiply over all the primes. Got it?

5:32Example 1: at least one ball from red, blue and green balls

Now Example one. From five identical red balls, four identical blue balls and three different green balls, in how many ways can at least one ball be chosen? Pause the video, and try it. Done? Okay, let's check. Red balls are identical, so only the number matters: zero to five, six choices. Blue: zero to four, five choices. With me? Now the green balls. Zero, one, two or three: four choices, right? No, no, careful! The green balls are different, so which ones you pick matters. Each is in or out: two times two times two, two cubed, eight. Clear? So, six times five times two cubed, that is six times five times eight: two hundred and forty. Minus one for the empty selection: two hundred and thirty nine ways. Perfect!

6:25Example 2: divisors of 720, even and multiples of 12

Now a slightly harder one. Seven hundred and twenty equals two to the power four, times three squared, times five. Find the number of its divisors, proper divisors other than one, even divisors, and divisors that are multiples of twelve. Pause the video, and try all four. Done? Okay, let's check. Part a: four plus one, times two plus one, times one plus one. Five times three times two: thirty divisors. Easy, isn't it? Part b: proper divisors other than one. So thirty minus one, twenty nine, right? Oh no, careful! Proper divisors never include the number itself. So remove both one and seven hundred and twenty: thirty minus two, twenty eight. Got it? Part c: even divisors. Each must contain at least one two. So the power of two runs from one to four: four choices, not five. Four times three times two: twenty four. Okay? Part d: multiples of twelve. Twelve is two squared times three. So what must such a divisor contain? Yes, exactly! At least two twos and at least one three. Write it as two to the power a, times three to the power b, times five to the power c. The sign on screen means greater than or equal to: a at least two, b at least one. So a is two, three or four: three choices. Then b is one or two, and c is zero or one: two choices each. Three times two times two: twelve. That's it!

8:03Quick revision: identical objects and number of divisors

So, quick revision. Identical objects: p plus one, times q plus one, times r plus one, and minus one for at least one. Each different object: times two. And divisors are identical objects in disguise: add one to each power, and multiply. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!