Math IOQM

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

Q1. Determine all solutions in the positive integers of 18x+5y=48 S1. y = (48-18x)/5 48-18x = 0 mod 5 3 = 3x mod 5 x = 1 mod 5 x = 1 => y = 6 x >= 6 not possible else y will become negative. what if I had done x = (48 - 5y)/18 in that case 48 = 5y mod 18 => 12 = 5y mod 18 Now, the thing is that y mod 18 can range from 0 to 17, so my trial and error will take much longer. So for these kind of equations it's always better to go for a smaller modulus, as we did in the first approach. Q2. 5x+3y=52. S2. x = (52 - 3y)/5 => 2 = 3y mod 5 => y = 4 mod 5 y = 4,9,14 => x = 8, 5, 2 Q3. Find all residues r with 0≤r≤7 such that x^2 ≡r(mod8) has a solution. S3. 0,1,4 Q5. A single bench section at a school event can hold either 7 adults or 11 children. When N bench sections are connected end to end, an equal number of adults and children together will occupy all the bench space. What is the least possible positive integer value of N? S5. a + c = N 7a = 11c 7,11 are primes => s...

Q1. Let n be the least positive integer greater than 1000 for which gcd(63,n+120) = 21 and gcd(n+63,120) = 60. What is the sum of digits of n? S1. First wrong attempt: n = 21p - 120 = 60q - 63 => q = (7p - 19)/20 p = 17 works between p = 1 to 20. So p = 17 mod 20. p = 17,37,57,77,97... 21p - 120 >= 1000 => p>=880/21 => p = 57 => q = 19 n = 21*57-120 = 1077 sum_digits(n) = 15 Why is this wrong? gcd(63, 1077 + 120) = 63 not 21. gcd(63, n + 120) = 21 means that gcd(63/21,(n+120)/21) = 1 gcd(3,p) = 1 => p can't be a multiple of 3 but we chose 57. Similarly: gcd(n+63,120) = 60 => gcd((n+63)/60,2) = 1 => gcd(q,2) = 1 => q is odd. So coming back to: q = (7p - 19)/20 for p = 77, q = (77*7 - 19)/20 = 26 but q has to be odd. for p = 97, q = (97*7 - 19)/20 = (630 + 49 - 19)/20 = 660/20 = 33. It works. So, n = 60*33 - 63 = 1980 - 63 = 1917 sum_digits(n) = 18 Q2. Prove that 10^(3n+1) cannot be represented as a sum of 2 cubes(integers). S2. Typically when dealing wi...

Q1. Does there exist an integer x satisfying the following conditions? 10x = 1 mod 21 5x = 2 mod 6 4x = 1 mod 7 S1. No. Why? [1] =>  10x = 1 mod 21 => 10x = 1 mod 3 and 10x = 1 mod 7 => x = 1 mod 3 and 3x = 1 mod 7 => 36x = 12 mod 7 => x = 5 mod 7 So we have x = 1 mod 3 and x = 5 mod 7 [2] =>  5x = 2 mod 6 => 5x = 6k + 2 => 5x = 2 mod 3 => 2x = 2 mod 3 => 4x = 4 mod 3 => x = 1 mod 3 And 5x = 0 mod 2 => x = 0 mod 2 So we have x = 1 mod 3 x = 5 mod 7 x = 0 mod 2 [3] => 4x = 1 mod 7 => 8x = 2 mod 7 => x = 2 mod 7 Which is a contradiction to existing solutions. Q2. For how many n between 1 and 2520 do we have n^3 = 1 mod 2520? S2. 2520 = 2^3 * 3^2 * 5 * 7 So n^3 = 1 mod 8 => n = 1 mod 8 n^3 = 1 mod 9 => n = 1,4,7 mod 9 n^3 = 1 mod 5 => n = 1 mod 5 n^3 = 1 mod 7 => n = 1,2,4 mod 7 For each of those options there is a unique solution (using CRT) between 1 and 2520. So total 9 valid solutions. Q3. Find positive integers a,b,c ...

  Homework(proofs): Q1. S1. n = 1 => (2k+1)^(2^1) = 4k^2 + 4k + 1 = 4k(k+1) + 1 = 8p + 1 = 1 mod 2^3(since k(k+1) is even) So works for n = 1 Assume (2k+1)^(2^n) = 1 mod 2^(2^(n+2)) _____[1] and using this prove for n+1: (2k+1)^(2^(n+1)) = 1 mod 2^(2^(n+3)) LHS = (2k+1)^(2^n.2^1) = [(2k+1)^(2^n)]^2 = [2^(n+2).m + 1]^2 using [1] = 1 + 2.m.2^(n+2) + m^2.[2^(n+2)]^2 = 1 + m.2^(n+3) + m^2.2^(2n+4) If you take mod 2^(n+3), it's clearly 1. H.P. Q2. Call a natural number n convenient, if n^2 + 1 is divisible by 1000001 . Prove that among the numbers   1,2,…,1000000, there are evenly many "convenient" numbers. S2. So essentially we need to find some sort of complement for each 'n' satisfying this. If we can show that for each 'n' satisfying this, there is another number satisfying this, we are done. Simplest 'complement' here is -n but that's negative. So let's think circular and try N-n where N = 1000,001 (N-n)^2 +1 = N^2 + n^2 - 2N.n + 1 = n^2...