Math IOQM

1. How many ways to distribute 10 different balls into 3 different bags such that none of the bags is empty? S1. Distinct objects/distinct buckets => PIE(Principle of Inclusion Exclusion) Step 1: Total cases: 3^10 since each ball can go into any of the bags. Step 2: Subtract those cases where one bag is empty: 3C1 to choose one bag. And now each ball has 2 options: 2^10. So total 3*2^10 cases need to be subtracted to account for one empty bucket. In step 2 consider what happens in detail: When we made one bucket empty, 10 balls have to go into 2 buckets: 2^10. This also includes the cases when all the balls go to one bucket. So considering empty bucket1 also considers the cases where bucket 1 and 2 are both empty. Similarly when we consider bucket2 as empty we are also considering the case where both bucket 1 and 2 are empty. Essentially we are double subtracting the cases where 2 buckets are empty. So we need to add them back. 3C2 to choose 2 buckets to remain empty. Now each ball ...

Q1. Three distinct vertices are chosen at random from the vertices of a given regular polygon of (2n+1) sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points? S1. Fact: The center of a regular polygon lies strictly OUTSIDE a triangle if and only if all three chosen vertices lie on a single semicircle. Explanation: Each regular polygon has a semicircle. If there are even vertices we will have diameters joining 2 vertices. In odd, we don't. For e.g. in a pentagon, Diameter from '1' lands on side 3-4. Here 2n+1 = 5 => n = 2 Here 3 vertices are in 1 half and 2 vertices in other half. If you make a triangle using 3 consecutive vertices it won't contain the center, else it would. For e.g. 1-2-3 doesn't but 1-3-5 does. Here total ways to create a triangle 5C3 = 10 Triangles with center outside: 1-2-3, 2-3-4 ... 5-1-2 = 5 such With cente...

Q1.  Show that there does not exist a function (f: N -> N) which satisfies (a) f(2)=3 (b) f(mn) = f(m).f(n) for all m,n in N (c) f(m) < f(n) whenever m < n. S1.

Q1. Objects A and B move simultaneously in the coordinate plane via a sequence of steps, each of length one. Object A starts at (0,0) and each of its steps is either right or up, both equally likely. Object B starts at (5,7) and each of its steps is either left or down, both equally likely. What is the probability that the objects meet? S1. Total distance between them: 12 Each step reduces distance by 2. So steps needed to meet = 6 During 6 steps, x co ordinate of A can go all the way upto 6. But B can't reach 6 since it's going left from 5. So they can meet at only x = 0,1,2,3,4,5 What is the probability that A's x co-ordinate is 'k' after 6 steps? 6Ck * p^k * (1-p)^(6-k) where p is probability that A will move right and (1-p) is the probability of moving up. Here p = 1/2 So it becomes 6Ck * (1/2)^6. How does B reach x = k? It has to move left by 5-k. k = 5 - (5 - k) What is the probability that out of 6 steps taken by B, 5-k are to the left? 6C(5-k) * (1/2)^6 Sinc...

Q1. In a group of 20 students: 5 are Yellow House 7 are Red House 4 are Blue House 4 are Green House How many ways can you choose: (i) 12 kids, such that exactly 3 kids from each house are present. (ii) 10 kids, such that at least 2 kids from each house are present. (iii) 15 kids, such that at least 3 kids from each house are present. S1. Attempt 1: (i) 5C3 * 7C3 * 4C3 * 4C3 (ii) 5C2 * 7C2 * 4C2 * 4C2 * 12C2 (iii) 5C3 * 7C3 * 4C3 * 4C3 * 8C3 In the above attempt, (i) is correct. But (ii) and (iii) are overcounting. Why? In (ii), Let's say we pick A,B from yellow house and the during 12C2 pick C from yellow house.  We also have counted the case where we first pick A,C from yellow and then pick B during 12C2. So this is wrong. Same for (iii). Another thought: to use stars and bars where houses are buckets and students are objects. But for stars and bars, the objects have to be same to each other. Here they are distinct. But stars and bars can tell us how many ways are there to group ...