Part A: Sets

Transcript

0:00Introduction

Hello everyone! Here is one small puzzle before we start. In a town of one hundred people, seventy read newspaper A, eighty read newspaper B, and ninety read newspaper C, okay? Now tell me: is it possible that nobody reads all three papers? Most students say, why not? But no, it is not possible! Some people are forced to read all three. How many, at least? We will find out by the end of this class. This is our mixed problem class on sets: the tools, the tricks, and the traps that JEE loves to set. So, let's begin.

0:40Two sets: how big can the union be?

So, first tool: the union of two sets. Say n of A is four, and n of B is six, okay? How many elements can A union B have? Ten, always? No, not always. It depends on the overlap, right? Look, n of A union B equals n of A, plus n of B, minus n of A intersection B, okay? So here it is ten, minus the overlap: the dark part in the middle. Clear? And how big can the overlap be? At least zero, and at most four, because the overlap sits inside A, and A has only four elements. The sign on screen is read, less than or equal to. So the union is least when the overlap is four, that is, when A sits completely inside B; the sign on screen means, is a subset of. Then the union is just the set B itself: six elements. And it is greatest, ten, when the overlap is zero: the sets are disjoint, like the picture. And one bonus from the same question. n of A cross B, the Cartesian product, is four times six: twenty four. That number does not change, whatever the overlap. It stays fixed.

1:55Neither A nor B: use De Morgan's law

Next tool. U is the universal set, the whole box, and n of U is seven hundred, n of A is two hundred, n of B is three hundred, and n of A intersection B is one hundred. We want n of A prime intersection B prime: the elements in neither set. So where do they sit in the diagram? Outside both circles, yes! That means outside A union B, completely. So, by De Morgan's law, A prime intersection B prime equals the complement of A union B, okay? The little dash on screen, the prime, means complement. So first the union: two hundred plus three hundred, minus the one hundred we counted twice. Four hundred. And neither is seven hundred minus four hundred: three hundred. So remember: for neither, first find the union, then subtract it from the universal set.

2:50Topper's trick: decide each element on its own

Got it? Now a trick that toppers use. How many subsets of the set one to ten contain one and two, but not three? Look, don't list them! One and two must be in, and three must be out. So three elements are already decided. Each of the other seven is free: take it or leave it, two choices each. So two to the power seven: one hundred and twenty eight. Now the same trick, one level up. How many ordered triples A, B, C of subsets of one, two, three, four are there, with A inside B, and B inside C? Choosing the sets one by one gets messy, right? So choose for each element instead: where does it enter the chain? It can be in A, and then it is in all three; or in B but not in A; or in C only; or in none of them. So, how many choices for each element? Four, exactly! And each element chooses on its own. So four to the power four: two hundred and fifty six. No listing, no tension. Nice and simple.

3:59JEE trap: do these two curves meet?

Now, a famous trap. Set A has all the points on the curve y equals e to the power x, with x real; the bold R on screen is the set of real numbers. Set B has the points on y equals e to the power minus x. Find A intersection B, okay? Many students write, the empty set. Are they right? No, no, careful! Let's solve it. For a point in both sets, e to the x must equal e to the minus x. Multiply both sides by e to the x: e to the two x equals one. The double arrow means, implies. So x is zero, and y is e to the zero, that is one. So A intersection B has exactly one element, the point zero comma one: a singleton. Not the empty set, that circle with a slash. The curves do meet! So in JEE, always solve first, and only then say, empty.

4:57Example 1: numbers up to 100 with gcd(n, 6) = 1

Let's do example one. How many integers n, from one to one hundred, have g c d of n and six equal to one? The g c d is the greatest common divisor. Pause the video, and try it first. Done? Okay, let's check. Six is two times three. So the g c d of n and six is one exactly when n is divisible by neither two nor three. The two-way arrow means, if and only if. Neither, hmm. Which tool does that remind you of? Yes, De Morgan! Count the opposite first. Divisible by two: fifty. Divisible by three: thirty three, because three times thirty three is ninety nine. Divisible by both two and three means divisible by six: sixteen numbers, because six times sixteen is ninety six. So, divisible by two or three: fifty plus thirty three, minus sixteen. Sixty seven. So the answer is one hundred minus sixty seven: thirty three. And look, the trap: if you forget to subtract the sixteen, those numbers get counted twice. Always remove the overlap, all right?

6:12Example 2: least and most readers of all three papers

Now the harder one, and it is our opening puzzle. In a town of one hundred people, seventy read newspaper A, eighty read B, and ninety read C, okay? Find the least, and the greatest, possible number of people who read all three. Pause the video and try it. Hint: think about the people who miss a paper. Done? Okay, let's check. Turn it around. Who does not read A? One hundred minus seventy: thirty people. Not reading B: twenty. And not reading C: ten. Now, anyone who does not read all three misses at least one paper, right? So, at most, how many such people can there be? Thirty plus twenty plus ten: sixty, at most. Only at most, because one person may miss two papers, and then gets counted twice. So at least one hundred minus sixty, that is forty people, read all three. And forty really happens, when the non-readers of A, B and C are three separate groups. So, our puzzle: can nobody read all three? Impossible! At least forty, always. And the greatest? Everyone who reads all three also reads A, so it is at most seventy. And seventy happens when A sits inside B, and B sits inside C, like a chain. So least forty, greatest seventy. All clear?

7:41Quick revision: union, counting subsets, least in all three

So, quick revision. One: for two sets, add both and subtract the overlap; and neither is the universal set, minus the union. Two: to count subsets, decide each element on its own, then multiply. Three: the least number in all three sets is the total, minus the most who can miss a set. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!