Math IOQM

PHP1: n holes, n+1 pigeons, at least 1 hole with > 1 pigeons. PHP2: n holes, nk+1 pigeons, at least 1 hole with > k pigeons. Q1. Pr. th. If there are 5 points inside a unit square, then the distance between at least any two points is less than 1/sqrt(2). A1. Divide in 4 smaller squares => at least 2 will be inside one square. Max distance inside that square is 1/sqrt(2). Q2. There are 14 sock pairs in a basket. How many you need to pick to be sure that you have 1 pair at least. A2. 15. PHP3: If mean of n +ive integers is k then at least 1 of them is >= k and at least 1 of them is <= k. Proof: If a1 = a2 = ... an = k then H.P. If a1 <= a2 <= a3 ... <= an then if a_i > k => a_j < k H.P. Q3. Suppose numbers from 1 through 20 are placed in some order around a circle. Prove that i) The sum of some three consecutive numbers must be at least 32. ii) The sum of some four consecutive numbers must be at least 42. Let the triplets be (a1,a2,a3) (a2,a3,a4) ... (a20...

Q1. How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are indistinguishable.)  S1. 7!/3!2! Q2. Seven 6-sided dice are rolled. The probability that the sum of the numbers on the top faces is 10 can be written as n/6^7 where n is a positive integer. What is n? S2. x1+x2..x7 = 10 Each of them is minimum 1. For stars and bars: x1+x2...x7 = 3 9C6 ways out of 6^7 ways. 84/6^7 n = 84 Q3. Suzanne went to the bank and withdrew 800 dollars. The teller gave her this amount using 20 dollars bills, 50 dollars bills, and 100 dollars bills, with at least one of each denomination. How many different collections of bills could Suzanne have received? S3. 20x + 50y + 100z = 800 2x + 5y + 10z = 80 5y will be even, y = 2k 2x + 10k + 10z = 80 x + 5k + 5z = 40 x = 5(8 - k - z) x >= 1 => 8-k-z > 0 => k+z <8 => k+z <= 7 For k+z <= 7 with k>=1 and z>=1 how many ...

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. 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 ...

Q1. A DNA chain is composed of basic building blocks in the form of four chemicals, known by the symbols A,C,T,G. Consider three-letter chains consisting of these symbols (with or without repetitions). How many such chains are there? S1. 4*4*4 = 64 Q2. Consider the set {a,b,c,d,e}. How many three-letter words can be made out of them, with or without meaning? How many of these will have at least one vowel in them? Answer these questions both for the case when repetitions of letters are allowed and for the case when repetitions of letters are not allowed. S2. 2.1 With repetition: 5*5*5 = 125 Without: 5*4*3 = 60 2.2 With repetition: Total words: 5^3 = 125 Without any vowels = 3^3 = 27 Answer = 125 - 27 = 98 Without: Total: 5*4*3 = 60 Without vowels = 3*2*1 Answer = 60 - 6 = 54 Q3. A permutation (a1,a2,a3,a4,a5) of (1,2,3,4,5) is called heavy-tailed if a1 + a2 < a4 + a5. What is the number of heavy-tailed permutations? S3. Total such: 5! = 120 Let's fix 1,2 to a1,a2 => 2!*3! = 12...

1. Find the total number of words formed by the letters a,a,b,b,c. S1. 5!/2!.2! 2. In how many ways can you arrange 2 beads of red colour, 2 beads of blue colour and 3 beads of black colour in a ring? Note that beads with the same colour are identical and arrangements that can be obtained by rotating (or) flipping the ring are identical. S2. First attempt(wrong): (7-1)! circular permutations Divide by 2!2!3! to account for repeated elements. Divide by 2 to account for flipping. Answer = 15 This is wrong, correct answer is 18. Why? Let's see using a smaller example. 2 blue, 3 black. (5-1)! circular permutations Divide by 2!3!. So far so good. Mistake is when we divide by 2 for flipping. Why do we even divide by 2 for flipping. Let's say we have 4 distinct beads. Here is one necklace: 1 --- 2 |       | 4 -- 3 and flipping it we get: 2 --- 1 |       | 3 -- 4 So 1-2-3-4 was clockwise and it became counter clockwise. Flipping gives a distinct perm...

1. 5 chairs, 4 people? How many ways can they sit? 5C4*4! = 120 2. 10 mangoes, 12 apples, 16 guava, 15 bananas. How many ways to eat 3 fruits? Case 1: Every single fruit is distinct. We have 53 fruits in total. So 53C3. That is if the order of eating doesn't matter. If the order of eating matters, then: 53.52.51 Case 2: Fruits of one type are all same.  Case 2.1 - Order of eating doesn't matter. Then this is simply stars and bars. (n+k-1)C(n) where 'n' is the number of items and 'k' is the number of buckets. Here,  n = 3 k = 4 So: All 3 fruits are same: 4C1 = 4 2 Same 1 distinct: 4C2 * 2C1 = 12 All 3 distinct: 4C3 = 4 Total: 20 Case 2.2 - Order of eating does matter. 4 * 4 * 4 = 64 Case 3: One fruit of each type, i.e. I eat 1 mango, 1 apple, 1 banana for e.g. Case 3.1 Fruits of same type are also distinct We have to consider 4 different cases(4C3): Mango, banana, apple = 10*15*12 Mango, banana, guava = 10*15*16 Mango, apple, guava = 10 * 12 * 16 Apple, banana, g...

  Where 'n' is a positive integer. For e.g.

  This is Tower of Hanoi/Brahma or Pyramid puzzle. An = minimum number of ways to shift the entire stack to 3rd tower via 2. Now, let's say we somehow transfer the entire stack except the last disk to 2. There are A_(n-1) ways to do that. Now, the last disk can be moved to 3rd tower in 1 move. And then again A_(n-1) ways to move these disks to 3 via 1. So A_n = 2*A_(n-1) + 1. This is first order non-homogeneous linear recurrence. So divide by 2^n on both sides. And eventually you get An = 2^n - 1. Let An = number of ways for A to get ball back after 'n' passes. If A gets the ball back after 'n'th pass then some other player had it after (n-1)th pass. Number of ways for A to have the ball after (n-1) passes = A_(n-1). => number of ways for A to NOT have the after (n-1) passes = Total ways - A_(n-1) Total ways for ball to move during (n-1) passes = 4^(n-1). Why? Because each player can pass the ball in 4 ways during each pass. => A_n = 4^(n-1) - A_(n-1) This is ...

Bijection principal: To solve some tough counting problems it's helpful if you can show that it maps to another easier counting problem. One to one. Exhaustive. Example 1: For e.g. how many shortest paths to travel from (0,0) to (m,n) in a grid? R denotes right, U denotes up. So 'm' Rs and 'n' Us. (m+n)!/m!n! Example 2: Number of partitions of a natural number: 2 -> 2, 1+1 3 -> 3, 2 + 1, 1 + 2, 1 + 1 + 1 Solution 1: You have 'n' 1s lined up with (n-1) gaps between them: 1 _ 1 _ 1 _ 1 _ 1 You are free to put a partition on each gap or not. So 2 choices per gap. 2^(n-1) Solution 2: n can be expressed as 1 variable: X1 -> (n-1)C(0) 2 vars -> x1 + x2 = n and x1,x2 >= 1 => n-2 identical objects into 2 distinct buckets: (n-2+2-1)C(2-1) = (n-1)C(1) 3 vars -> (n-1)C(2) ... (n-1)C(n-1) Adding them and applying binomial theorem the sum is equal to : 2^(n-1) Now coming back to Bijection Principal: This last problem can be mapped to another problem....

Earlier lectures: Lecture 1 Lecture 2 Theory: 1. First order linear non-homogeneous: An = f(n).A_(n-1) + g(n) Solution approach: Divide each term by f(1).f(2)....f(n) and convert it to Bn = B_(n-1) + g'(n) then telescope. 2. First order linear homogeneous: An = f(n).A_(n-1) Solution approach: A2/A1 * A3/A2 * A4/A3 ... = f(2).f(3)...  2a. An = k.A_(n-1) (G.P. solution) 3. Second order homogeneous with constant coefficients: An = k.A_(n-1) + m.A_(n-2) Two ways to solve this. 3a.  Try to make it Bn = (some constant) * B_(n-1) Where Bn = An - p.A_(n-1) To do that do this: An - p.A_(n-1) = k.A_(n-1) + m.A_(n-2)  - p.A_(n-1) And then by equating coefficients find the value of p. Now it's a G.P. in Bn. Solve for Bn and then equate that to An - p.A_(n-1). Now it's a first order linear recurrence. Solve it. 3b. Second method: Let An = X^n. This will give you a quadratic characteristic equation. Solve to get roots a,b. An = p.(a^n) + q.(b^n) Now find values of p,q by using ini...

  Solution: Total ways: 64C2 Now subtract invalid: 2 main diagonals: 2*8C2 8 rows and 8 columns: 2 * 8* 8C2 Smaller diagonals: 4 of each type 4 * [2C2 + 3C2 + ... 7C2] Simplify using hocky stick identity . = 4 * [8C3] So finally: 64C2 - 4*8C3 - 18*8C2 = 1288 Case 1: Axis-aligned squares. 1x1 squares  = 15*15 2x2 = 14*14 .... 15x15 squares = 1*1 total = 1^2 + 2^2 .... 15^15 = 1240(sum of first n natural number squares) Case 2: tilted squares. 1 tilted square in each 2x2 axis aligned square: 2 tilted squares in each 3x3 axis aligned square: 3 in 4x4 14 in 15x15 Total: 1*14^2 + 2*13^2 + 3*12^2 .... 14*1^2 = Sigma(k=1 to 14) (k * (15-k)^2) Finally: 4200 + 1240 = 5440 = Answer