Math IOQM

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.

  Problem 1. Let (a) be a positive real number. Prove that one of the positive real numbers [ a,;2a,;3a,...;(n-1)a ] is at most (1/n) distant from a positive integer. S1. Let's test for n = 2 The list is simply: 'a'. And any real positive number is at most 1/2 away from a positive integer. So it works for n = 2. Let 1 <= k <= n-1. We want to show that at least one k.a is at most 1/n away from a positive integer. Let {k.a} be the fractional part of k.a. Distance of {k.a} from a positive integer is min( {ka}, 1 - {ka}). To understand, see the number line: 0______{ka}_______1 Its distance from 0 is {ka} and 1 - {ka} from 1. Let's prove by contradiction. Let's say for each 'k', 1 <= k <= n-1, {k.a}is more than 1/n away from the nearest integer. Like this: 0___1/n___{ka}___1 - 1/n____1 So {ka} is always between 1/n and (n-1)/n. Distance between 1/n and (n-1)/n is (n-2)/n. So there are (n-2) gaps each of length 1/n. Using pigeonhole argument, fraction...

1) P(x) = x^4- 4x^3 + 6x^2 - 4x - 2005. Find the integer part of the product of all non-real roots of (P). S1) P(x) = 0 => (x-1)^4 = 2006 => (x-1) = K.(2006)^(1/4) where K = -+1, -+i So non real roots are x = 1 +-i.(2006)^(1/4) Multiply: 1 + 2006^(1/2) 45^2 = 2025 45^2 - 44^2 = 89 So 2006^(1/2) = 44.something Answer: 45 2) First we will prove this: In the incircle trisects the median then the sides are in the ratio 5:10:13 where 10 maps to the base where median is landing. Once we do that, since BC = 20, other sides will become 10 and 26. Then apply Heron's formula. s = 28 s - a = 28 - 20 = 8 s - b = 28 - 10 = 18 s - c = 28 - 26 = 2 [ABC] = sqrt(28.18.8.2) = sqrt(64.7.2.9) = 24.sqrt(14) m + n =38 Ok coming to the proof of the first part. Using power of the point theorem: If DF is the tangent from D, then DF^2 = DY.DX = d/3 * 2d/3 = 2d^2/9 Similarly Tangent from A = AE then AE^2 = AX.AY = DF^2 => AE^2 = DF^2 But AE = s - a from incircle properties. And DF = (s-c) - a/2 = a+...

  1) Find the largest natural number 'm' such that:  (m^2) is the difference of two consecutive perfect cubes. AND  (2m + 79) is a perfect square. S1) m^2 = (n+1)^3 - n^3 = 3n^2 + 3n + 1 Since m,n are both natural numbers, RHS will grow much faster than LHS and at some point it will irreversibly exceed it. m^2 - 1 = 3n(n+1) So RHS is a multiple of 6 => m^2 = 1 mod 6 m^2 = 25,49 satisfy this but 24 = 3n(n+1) => 8 = n(n+1) no go. 48 = 3n(n+1) => 16 = n(n+1) no go. what next? So let's try some other approach. Once you complete the square in 'n', you will get: 3n(n+1) + 1 = 3[(n+1/2)^2 - 1/4] + 1 = m^2 4m^2 = 4 + 3[ (2n+1)^2- 1] = 1 + 3.(2n+1)^2 4m^2 - 1 = 3(2n+1)^2 (2m-1)(2m+1) = 3(2n+1)^2 LHS has 2 consecutive odd numbers which are co prime. Why? gcd(2m-1,2m+1) = gcd(2,2m-1) = 1 So RHS should split cleanly into 2 factors which don't share any prime factors. Case 1: 2m-1 = a^2 2m + 1 = 3b^2 Case 2: 2m + 1 = a^2 2m - 1 = 3b^2 Case 2: 2 = a^2 - 3b^2 => a...

Q1) Let A be a set of m positive integers, where m >= 1. Show that there is a non-empty subset (B) of (A) such that sum of all elements in B is divisible by (m). S1) Let's create prefix sums like this: S1 = a1 S2 = a1 + a2 ... Sm = a1 + a2 .. am If any one of S1,S2...Sm has a 0 remainder we are done. If not, then at least 2 of them have same remainder. Then: Sk - Sj = 0 mod m If k > j Then Sk - Sj = ak + a_{k-1} ... a_{j-1} So these are the required elements. Q2)  Let (A) be a subset of ({1,2,...,2n}) such that (|A|=n+1). Show that there exist (a, b in A) such that gcd(a,b)=1. Part 2: Can we also say the same thing when |A| = n? S2) There are at least 2 consecutive numbers in A. Proof by PHP: {1,2} {3,4} ... {2n-1,2n} Each number belongs to one bucket out of these 'n' buckets. If there are n+1 numbers, at least 2 of them will fall into same bucket. Proof by contradiction(not very solid): Let's say A has only non-consecutive numbers. Then it can have only n number...

Q1)   A square of dimension (n-1) * (n-1) is divided into (n-1)^2 unit squares in the chess board manner. Now, each of these (n^2) vertices of these squares are to be painted black or blue such that each unit square has exactly two black vertices. In how many ways can this be done? S1. Look at an individual square. There are 2 ways for it to yield 2 black vertices. One horizontal edge blue(or black), other black(or blue). Or 1 color each on top edge, and similarly on bottom edge. Once you expand the pattern, there will be only 2 ways to get it done. Each row alternates or each column alternates or both alternate. Case 1: Each row alternates. So each row can start with one of 2 colors and then the pattern is fixed. So 2^n ways since there are 'n' rows. Case 2: Each column alternates. 2^n again. Case 3: Both alternate. Exactly 2 ways like a chessboard. Total: 2^n.2 - 2 = 2^(n+1) - 2. Q2. S2. As the diagram shows a 2x2 bounding box can hold 2 different squares. That rule actually ...

Q1.  Find the number of triangles whose angular points are at the angular points of a given polygon of (n) sides, but none of its sides are the sides of the polygon. S1. Simple application of  Kaplansky's first lemma . Formula derived is: (n-k-1)C(k-1) + (n-k)C(k) Here k = 3 (n-4)C(2) + (n-3)C(3) = (n-4)(n-5)/2 + (n-3)(n-4)(n-5)/6 = (n-4)(n-5)/2[1 + (n-3)/3] = n(n-4)(n-5)/6

Q1. (n) is a positive integer. (A) is a set such that A={1,2,...,n}. Let (t_n) denote the number of subsets of (A) such that the arithmetic mean (AM) of the elements is an integer. Prove that (t_n) and (n) are both odd or both even. S1. 1. Let us ignore empty subset since A.M. is not defined for that. 2. Subsets of size 1: {1}, {2} ... {n}. There are 'n' such subsets. And each of them has their A.M. as integer. 3. Now let's consider the subsets with size >= 2 which have an integer A.M. Let G be the set of all such subsets. Let's consider a function 'f' defined for subsets of size >= 2. f(S) = S - {k} where k is the A.M. of S and k is present in S. f(S) = S + {k} where k is the A.M. of S and k is not present in S. For e.g. S = {1,3,8}, k = (1+3+8)/3 = 4 4 is not there in S. f(S) = {1,3,4,8} S = {1,2,3}, k = (1+2+3)/2 = 3 3 is there in S. f(S) = {1,2} Note 1: S and f(S) have the same A.M. Why? Let S = {a1,a2...,ak} AM = sigma(a_i)/k If you remove AM, the ne...

Q1. (combinatorial geometry problem) There is a 21-sided regular polygon with vertices (A1, A2 .... A21). Triangles are formed by joining these vertices. a) How many of these triangles are acute-angled ? b) How many of these triangles are right-angled ? c) How many of these triangles are obtuse-angled ? d) How many of these triangles are equilateral ? e) How many of these triangles are isosceles ? S1. Regular polygon can be inscribed in a circle. Each arc being of equal length. For e.g. equilateral triangle will create 3 arcs of 120 degrees each. So 21-gon will create 21 equal-sized arcs. Total possible triangles = 21C3 = 21.20.19/6 = 19.70 = 1330 b) 0 right angle triangles. Why? By Thales' theorem, diameter inscribes right angle on circumference. And a diameter divides circle into 2 equal parts. In an odd sided regular polygon, we cannot have equal number of arcs on both sides of the diameter. c) By inscribed angle theorem, for an obtuse angle on circumference, the intercept...

Q1. Prove that if the two angle bisectors of a triangle are equal, then the triangle is isosceles. ( Steiner-Lehmus Theorem ) S1. So, let's see what are we trying to prove. BE = CF and angle B = angle C We know that length of angle bisector in triangle is given by the below formula. BE = 2ac.cos(B/2)/(a+c) Similarly, CF = 2ab.cos(C/2)/(a+b) make the equal: c.cos(B/2)/(a+c) = b.cos(C/2)/(a+b) cos(B/2)/cos(C/2) = ab + bc/ac + bc We will prove by contradiction. WLOG, Angle B > Angle C => b > c also => cos(B/2) < cos(C/2) (since B/2 and C/2 are both < 90). So LHS < 1 But RHS > 1 why? Because  ab + bc > ac + bc (since b > c) And if Angle C < Angle B, again LHS > 1 and RHS < 1. So only option is that both are equal. H.P. A slippery slope: If you go a different way, you will miss the proof! It's quite tricky. c.cos(B/2)/(a+c) = b.cos(C/2)/(a+b) from here: b/c = sinB/sinC => cos(B/2)/(a+c) = sinB/sinC * cos(C/2)/(a+b) sinB = 2sin(B/2)cos(B/2) ...

Q1. S1. QR || AC by MPT. => line BHE is perpendicular to QR. In triangle AHB, using MPT, QP || BH. => QR is perpendicular to QP => angle PQR = 90 H.P. Q2. ABCD is a quadrilateral in which AB = AD . The bisectors of ∠BAC and ∠CAD intersect the sides BC and CD at E and F , respectively. Prove that (EF ||BD). S2. Using Angle bisector theorem: Triangle ABC: AB/BE = AC/EC Triangle ADC: AD/DF = AC/FC => AB/AC = BE/EC = AD/AC = DF/FC (since AB = AD) Now in triangle BDC: EF divides the sides BC and DC in same ratio => EF || BD H.P.

  Q1) Let (ABCD) be a rectangle such that (BC = 3AB). (P) and (Q) are points on the side (BC) such that BP = PQ = QC. Show that \angle DBC + \angle DPC = \angle DQC. S1. Q2. In a quadrilateral ABCD, given that angle A + angle D = 90. Pr. th. AC^2 + BD^2 = AD^2 + BC^2. S2. BC^2 = OB^2 + OC^2 AD^2 = OA^2 + OD^2 BC^2 + AD^2 = OB^2 + OC^2 + OA^2 + OD^2 Look at RHS: OA^2 + OC^2 = AC^2 OB^2 + OD^2 = BD^2 H.P. Q3.  In ( \triangle ABC ), (BM) and (CN) are perpendiculars from (B) and (C) respectively on a line passing through (A). If (L) is the midpoint of (BC), prove that [ ML = NL. ] S3. Method 1: Let LP be perpendicular to the same line passing through A. LP || BM || CN According to Intercept theorem, if 3 parallel lines cut 2 equal segments from a traversal, they will do the same with any other traversal. So MP = PN Now we will show triangle LMP congruent to LNP. LP is common side. Angle P is 90 in both. MP = PN. => LM = LN. Method 2: co-ordinate geometry Let the line thro...

Q1. The side AB of a parallelogram ABCD is produced both ways to F and G, so that AF = AD and BG = BC. Prove that FD and GC produced intersect at right angle. S1. There are 2 ways to draw the diagram here. Both give us the desired proof. Q2. In triangle AQB, points P and D lie on sides AB and AQ, respectively, such that [APQ]=[ABD]. Through D, draw the line DR∥AB, meeting BQ at R. Through B draw a line || to AQ which meets DR at C. Pr. th. RC=AP. S2. ABCD is a ||gram. AB = CD____[1] AD = BC Given [APQ] = [ABD] => Sin(A).AP.AQ = Sin(A).AB.AD => AP/AB = AD/AQ => Triangles APD and ABQ are similar by SAS. => PD || BR => BPDR is a ||gram => PD = BR and BP = DR___[2] From [1]: AP + PB = DR + RC Using [2]: AP = RC H.P. Q3. ABCD is a parallelogram. Through C, a straight line RQ is drawn outside the parallelogram, and AP, BQ, DR are drawn perpendicular to RQ. Show that DR + BQ = AP. S3.  

Q1. S1. First do angle chasing and get all angles. Now apply Sine rule in AMC. AC/sin(150) = MC/sin(7) sin(150) = sin(180-150) = sin(30) = 1/2 => AC = MC/2sin(7)___[1] In BMC: BC/sin(M) = MC/sin(97-M) BC = AC and sin(97-M) = sin(90 + 7 - M) = cos(7-M) = cos(M-7) => AC = MC.sin(M)/cos(M-7)  ____[2] Using [1] and [2]: 1/2sin(7) = sin(M)/cos(M-7) => 2sin(7)sin(M) = cos(M-7) = cosMcos7 + sinMsin7 sin7sinM = cos7cosM tan7 = cotM = tan(90-M) => M = 83 = answer Q2. S2. Isosceles triangle, altitude bisects the base. x^2 = h^2 + 225 y^2 = h^2 + 36 (x+y)(x-y) = 189 = 3^3*7 189 = 189 * 1 = 63 * 3 = 21 * 9 = 7 * 27 case 1: x+y = 189, x-y=1 => 2x = 190 => x = 95, y=94 => AD = CD = 95, perimeter = 190 + 30 = 220 case 2: x+y = 63, x-y=3 => 2x = 66 => x = 33, y=30 => AD = CD = 33, perimeter = 66 + 30 = 96 case 3: x+y = 21, x-y=9 => 2x = 30 => x = 15, y=6 => AD = CD = 15, invalid since AC = 30 case 4: x+y = 27, x-y=7 => 2x = 34 => x = 17, y=10 => AD =...

Q1. Prove that, for a, b, c ∈ ℝ⁺, a/b + b/c + c/a ≥ (a + b + c)² / (ab + bc + ca). S1. We will use Titu's lemma to prove it. First let's prove Titu's using C-S. C-S says for any real numbers: (a1b1 + a2b2 ... anbn)^2 <= (a1^2+ a2^2 .. an^2).(b1^2+b2^2...bn^2) Let's use p1 = a1/sqrt(b1)... with addl. constraint that b1,b2.. are positive reals. q1 = sqrt(b1)... It becomes: (p1 + p2 .. pn)^2 <= (p1^2/q1 ..)(q1+q2...qn) => (p1+p2..pn)^2/(q1+q2..qn) <= p1^2/q1 + p2^2/q2... This is Titu's lemma. Now, for the given question. Make LHS like this: a^2/ab + b^2/bc + c^2/ac In Titu's lemma, let's use: p1 = a, p2 = b, p3 = c q1 = ab, q2 = bc, q3 = ac So it becomes: (a+b+c)^2/(ab+bc+ca)<= a^2/ab + b^2/bc + c^2/ac H.P. Q2. If P1, P2, ..., P2014 be an arbitrary rearrangement of 1, 2, ..., 2014. Prove that 1/(P1 + P2) + 1/(P2 + P3) + ... + 1/(P2013 + P2014) > 2013/2016. S2. We will use Titu's lemma here again. Which is: a1^2/b1 + a2^2/b2 ... a2013^2/b...

Q1 . Compute the sum of all positive integers (n) for which lcm(1,2...n) can be written as the product of 10 distinct pairwise coprime positive integers , each less than or equal to (n). S1. For e.g. consider a smaller problem where we need to find 4 distinct pairwise coprime factors. For n = 5,  LCM(1,2,3,4,5) = 60. 60 = 1.2^2.3^1.5^1 So the factors are 1,3,4,5 Each pair is co prime. Each factor is less than 60. So we need first 9 primes and 1 or first 10 primes to solve this. 2,3,5,7, 11,13,17,19 23,29 are the first 10 primes. LCM(1,2... 23) = 1. 2^4. 3^2. 5^2. 7. 11. 13. 17. 19. 23 We can see the 10 factors each pairwise co prime and <= 23 Same will happen for 24,25,26,27,28. For 29,30 we will remove 1 to get exactly 10 factors. That's the last. From 31 we will have at least 11 such factors. Answer = 23 + 24... 30 = 212 Q2. S2.

Q1) (a,b,c) are real numbers such that a+b+c=0 a^2+b^2+c^2=1 Show that a^2b^2c^2 <= 1/54. S1) Let's construct a cubic equation with roots a,b,c. (a+b+c)^2 = 1 + 2(ab+bc+ca) => ab + bc + ca = -1/2 x^3 -x/2 - r = 0 where r = abc Since all 3 roots are real, the product of values of function at critical points(maxima,minima) should be <= 0. Find critical points, derivative = 3x^2 - 1/2 = 0 => x = -+1/sqrt(6) f(1/rt(6)) = 1/6.rt(6) - 1/2.rt(6) - r = 1/3.rt(6) - r f(-1/rt(6) = -1/3.rt(6) - r multiply: r^2 - 1/54 <= 0 H.P. Q2. P2) If 1/x + 1/y + 1/z = 1 for x,y,z > 0 pr. th. (x-1)(y-1)(z-1) >= 8 S2. let a = 1/x and similarly others. a + b + c = 1 x-1 = 1/a - 1 = (1-a)/a = (b+c)/a b+c >= 2.rt(bc) So expr. becomes: (b+c)(c+a)(a+b)/abc>= 8.abc/abc = 8 H.P.

Day 1: Q1. The repeating decimals x = 0.ababab... and y = 0.abcabc.... satisfy x + y = 33/37 Find the 3 digit number abc. S1. (10a+b)(1/100 + 1/10000...) = (10a+b)/100[1/1-1/100] = (10a + b)/99 (100a + 10b +c)(1/1000 + 1/1000,000....) = (100a+10b+c)/999 (10a + b)/99 + (100a+10b+c)/999 = 33/37 => 999(10a+b) + (100a+10b+c).99 = 33.99.999/37 = 27.33.99 => 111(10a+b) + (100a+10b+c).11 = 99^2 = 9801 => 2210a + 221b + 11c = 9801______[1] => a <= 4 2210*4 = 8840 => 221b + 11c = 961 b = 4 => 11c = 961 - 884 = 77 => c = 7 abc = 447 Also in [1] if we take mod 11 then: 2210a + 221b = 0 mod 11 221(-a +b) = 0 mod 11 => a = b mod 11 Since a,b are single digit => a = b 221a.11 + 11c = 9801 => 221a + c = 891 a = 4 => c = 7 Q2. Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. S2. Let's do step by step. Subset size: 3 => There are 10 ways. Total: 10 Size: 4 => 10 ways to pick 4...

 Q1. Prove that for every positive integer (n), the number [ 3^{3^n}+1 ] is the product of at least (2n+1) (not necessarily distinct) primes. S1. Prove by induction. Q2. Prove that for every positive integer (n), there exists an (n)-digit number divisible by (5^n) whose all digits are odd. S2. Proof by induction: Let's assume it holds true for k  Now we construct 5 (n+1) digit numbers using A: All 5 of them leave different remainders modulo 5 so at least one of them will leave 0 and that would give us divisibility by 5^(n+1). Why will all be different modulo 5? Let's try to prove by contradiction: 2^n + a = 3.2^n + a mod 5 => 2.2^n = 0 mod 5 false. And each time you do this you will get some even number = 0 mod 5. Which is false. H.P. Q3. Let n be a positive integer. Let 0 < a1 < a2 ... an be real numbers. Prove that at least {n+1}C{2}) of the sums +-a1 +-a2 ... +-an are distinct. S3. First we will show that this problem maps to another simpler problem. And then solve...

Q1. Show that (1 - 1/2^2)(1 - 1/3^2)....(1 - 1/(n+1)^2) = n+2/2n+2 S1. Easy to show via induction. Other way via telescopic cancellations: Kth term is (k^2 - 1)/k^2 = (k-1)(k+1)/k^2 = (k-1)/k.(k+1)/k Now separate out k-1/k and k+1/k terms and multiply: 2-1/2 * 3-1/3 * 4-1/4 .... n/n+1 = 1/n+1 2+1/2 * 3+1/3 ... n+2/n+1 = n+2/2 Hence proved. Q2. Show that: S2. Short method: r*nCr = n*(n-1)C(r-1) and take sigma simply. Longer method:  2^(n-1) = (n-1)C0 + (n-1)C1... (n-1)C(n-1) (n-1)Ck *n = nCk*(n-k) How? n * (n-1)!/k!(n-1-k)! = n! /k!(n-k-1)! But (n-k-1)! = (n-k)!/(n-k) So n * (n-1)!/k!(n-1-k)! = (n-k)n! /k!(n-k)! = nCk*(n-k) So n*2^(n-1) = n *2^(n-1) = n*[(n-1)C0 + (n-1)C1... (n-1)C(n-2)+ (n-1)C(n-1)] = nC0 * (n-0) + nC1*(n-1) ... nC(n-2)*(2)+ nC(n-1)*(1) It can be rewritten as: = nCn*n + nC1 * (n-1) ... nC2 * 2 + nC1 * 1 = (r = 1 to n)Sigma(r*nCr) = (r = 0 to n)Sigma(r*nCr) Hence proved. Q3. S3. Quite simple. Let the given sum be S. 3S = 1.3^2 + 2.3^3... n.3^(n+1) S-3S = 3 + 3^2 ......