NON-ROUTINE PROBLEMS IN MATHEMATICS (WITH SOLUTIONS) Editor Prof. V. K. Krishnan The Association of Mathematics Teachers of India B-19, Vijay Avenue, 85/37, V. R. Pillai Street, Triplicane, Chennai — 600 005. E.Mail : [email protected] Phone : (044) 844 1523.BETWEEN US Dear Reader, It is with a sense of pride and satisfaction that we place in your hands the edited version of the lessons dispatched as Correspondence Course in Non-Routine Problems Solving, The idea was conceived and executed by our senior member Prof. M.S.Rangachary. formerly Director of Ramanujan Institute for Advanced Study in Mathematics, University of Madras and ably assisted by Prof: G. Rangan, Prof. ¥: Shankaram, Prof. VK. Krishnan, Dr. S. Muralidharan, Dr. Hemalatha Thyagarajan, Sri S.R. Santhanam and Ms. R. Vijayalakshmi. They were sent as 11 lessons to the registered candidates. Though their number was few, the quality of the work was appreciated by the recipients and those who saw the lessons. It was felt that the same might be brought out in the form of.a book for reference by the prospective Olympiad participants, IIT type entrance examination aspirants and the general public to spend time with Math- ‘ematical thinking as a hobby. Prof. V. K. Krishnan from Trichur was kind enough to edit the les- sons to suit a textbook with improvements in the solutions of worked problems and in suggested solutions. I take this opportunity to express my grateful thanks to Prof: M. S. Rangachary, Prof. ¥.K. Krishnan and other learned teachers who made this publication possible. We are quite sure that the well-wishers of AMTI will ensure that this material reaches the needy and generate de- mand for further editions too. {tis my duty and responsibility to place on record our thanks to SriG Narayanan of Ramanujan Institute for technical assistance and M/s Pagesmith Laser Typesetters, M.K, Graphics and Souri Printers for bring- ing out this book in time. With Kind regards/ best wishes, Yours sincerely, AL 25.12.2001 (M. Mahadevan} A SecretaryLesson 2 Lesson -4 Lesson 5 Lesson 8 Lesson 9 Lesson 10 Lesson 11 CONTENTS Pigeon Hole Principle-I .........++-++2-+erseerereeeet 1 Inequalities ............cececeencesetareeeessecssoene 5 Divisibility of Numbers ..........--++++++ aseeieseess % Permutations and Combinations ..........--++++++++ 32 Number Theory ........005c0ssccseeeeeeeeeeeeenees 45 Concurrency and Collinearity ............ aavessoeaee 53 Mathematical Induction .............0eceeeeeseeeeie 73 Pigeon Hole Principle-I Quadrilaterals: Cyclic and Circumscribed ........... 87 Circles Related to Straight Lines Triangles ........ 105 Circles Connected with a Triangle ........ssss0005 u7 Solutions of Problems ..............--+0-sssseeeseeees 129LESSON 1 PIGEON HOLE PRINCIPLE-I Welcome to this course! Hope you will realize through this course the power of mathematical thinking. This programme will suceed if your confidence level goes up. In this lesson we start with a simple idea. Supposing you have 4 purses and 5 coins and you put the coins in these purses as you like. For instance, you can put all of them in one purse so that 3 purses are empty or you can put 2 in one, 1 in another, 2 in another and keep one empty. But some occurrence is certain to happen. Can you guess? At least one of the purses contains more than one coin. Once you have been told this fact the ‘idea’ is silly and just an offshoot of commonsense (thinking!) You might have seen holes under the roof of towers in temples, churches, mosques etc. where pigeons live. If there are n holes and there are (n +1) pigeons and all of them get into the holes, then. At least in one hole there will have to be more than.one pigeon Bearing this in mind, the idea is called the PIGEON HOLE PRINCIPLE (PHP). See the power of this principle illustrated in the following examples. Example 1: Show that given 12 integers there-exists two of” them whase difference is divisible by 11. Solution: Possible remainders when any integer is divided by 11 are 0,1,2,-- ,10.- Treat these remainders as ‘holes’ and the2 NON-ROUTINE PROBLEMS IN MATHEMATICS 12 given integers as pigeons. By PHP two of them should lie in the samie hole, i.e. should leave the same remainder when divided by 11. Hence their difference is divisible by 11. Example 2: There are balls of 4 colours in a basket. When picking up a random collection of balls, if at least 2 balls should have the same colour, what is the least number of balls in the collection? Solution: Treat the 4 colours as ‘holes’. The minimum number 5 of balls treated as ‘pigeons’ ensures that, at least 2 balls are of the same colour because of PHP. Thus the answer is 5. The following illustrates PHP being used along with some other idea. Example 3: There are 7 persons in a group. Show that some two of them have the same nuinber of acquaintances among them. Solution: Each of them can be acquainted with 0,1, 2,3,4;5,6 persons in the group. If there is one of the seven persons ac- quainted with the other 6, then there is no person acquainted with none of them, i.e., if we denote the corresponding classes of persons with an overhead bar, if 6 is not empty, then 0 is empty. In this case the seven persons are to be put in the classes T, 2, 3,4,3, 6 (6 classes) so that one of them should have more than one person by PHP. If 6 is empty,then the 7 persons are to be put in the classes 0,1,2,3,4,5 so that in this case too there are two persons in some one of these classes. This proves the assertion. Example 4: Five points are marked at random in a square plate of length 2 units. Show that a pair of them are apart by not more than V2 units. Solution: By taking the midpoints of the edges and joPigeon HOLE PRINCIPLE-[ 3 the points on opposite edges we get a grid of 4 unit squares. By PHP two of the points lie in one of these grids and the maximum distance between these points is V2 units (the length of the diagonal of the unit square) Note: Here the pigeon holes are not pairwise disjoint. PROBLEM SHEET . The city of Madras has a population of 25 fakhs. If each citizen of Madras has an asset. of value not more than 2 lakhs, show that two of the citizens have assets of the same value, when corrected to the nearest integer. . Given 10 triangles show that two of them are either equi- lateral or isosceles but not equilateral or acute angled but not isosceles or obtuse angled but not isosceles or right angled but not isosceles. 3. A is a subset of the arithmetic progression 2,7, 12,--- ,152 having 16 elements. Show that there are two distinct, elements of A whose sum is 159. What can you say if A has 14 elements? = . Given three points in the interior of a right angled trian- gle, show that two of them are at a distance not greater than the maximum of the lengths of the sides containing the right angle. o . Ifa line is coloured with 11 colours show that there exist two points whose distance apart is an integer which have the same colour. = }. Show that in any set of ten distinct two digit numbers there exists two subsets which have the same sum.NON-ROUTINE PROBLEMS IN MATHEMATICS - What is the maximum number of squares in a 4 x 4 check- board which could be coloured red so that there is no red right angle in the board? . Show that, if in a class of 15 students the total of the marks in a subject is 600, then there is a group of 3 stu- dents the total of whose marks is at least 120. . Show that there exists a power of 3 which ends with the digits 001. If the. digits 1,2,3,4,5,6,7,8,9 are divided into three groups show that the product of the numbers in one of the groups exceeds 71.LESSON 2 INEQUALITIES § 1. We know thai given:any two distinct real numbers a,b, ither a b. But to decide whether it is the former quality or the latter for any given pair of real numbers often mires use of certain facts in a clever way. Take for example 2,35. If 0 < m 0, 2" < 3”. But these inequalities as such do not help to compare 2° and 38. On the other hand, 3° = (2418 = Be3xP2¢3x2t¢1< B+4xPsax 2= P4428 = 2x B42! = 2x 24 = 2. OF course 25 = 32 and 3% = 27 are easily computable and it is evident that 2° > 33. If, however, the indices m,n of 2,3” are very s from which we lary is necessary to think of smaller indi could derive the inequality for larger indices. e.g. knowing that 2 > 33, we immediately deduce 25%12! = 2605 > g3*121 — 3363, Also. 27 > 34 since 2? x 25 > 2? x 39 = 4x32 >3x 33 = 3, Hence, eg. 27 > 34. A simpler deduction is the foutine 9 = 3? > 23 = 8 = 37 > 29. Example 1. Which number is greater 31!? or 17!7? Solution. 31}? < (32)!? = (25)!2 = 260 < 268 = 24xI7 = (2*)'7 < 167 < 17!7. So, 31!? < 1717, Example 2. Which is greater 7°? or 8°"? Solution. Note that if a, b are positive and n a natural number (a+b)" = (a+b) x-?+x (a+b) =a"-+na"~'b+ terms involving powers of a and / or b with natural numbers as coefficients. So (a +0)" > a” + na"~'d (equality occurring only for n = 1; this is an easy deduction from the binomial theorem and is some6 NON-ROUTINE PROBLEMS IN MATHEMATICS times called the Bernoulli inequality). Now 8° = (7 +1)% > 7) 491 x 7% = 7°9(7 +91) = 7%. 98 > 79.49 => 797. Hence 8°! > 7°. (Exercise: Use some other way to get this inequality). Example 3. Show that 49 < 2!33 + 3133 < 4108, Solution. Since 2.3!33 > 2!33 + 3!%3, to prove the inequality on the right. it suffices to show that 4198 > 2.3158, ie. 495 > 2. , 7, a Note that 4! > 3° so that fy > ($2) |= (1+ 28)” > 1427 x 33 > 2 (by Bernoulli’ the right is thus proved. We prove that 3'°3 > 49°-more than inequality). The inequality on s\ 19 95 the inequality on the left. Now 4° < 37.S0(#) = das <1 proving that 3'%3 > 4% and so the inequality on the left. Note: If0 1, then 2? > x. On the other hand, if 0 < z < y, then 2* < y® whatever be a>d. v2+Vv3 V24+ V3 i B22 (ai Solution. Ss > Ge (since V3> V2 and V3<2)= we = v2, proving the inequality on the left. Now, ArJi < 2¥3 = 9 (since V3 ree 2 (since ¥2 < V3 and V3 > 1). Observation. Consider the numbers yjpr, jit. Note that the pattern of the numbers in both the numerator and denom- inator of each fraction is the same, viz. Os flanked by 1. The only difference is that the denominator has one more 0 than Example 4. Show that V2-< <2. the numerator. If x is the numerator of any one of the two fractions, then the corresponding denominator is 102 — 9. De- noting the fraction by a, } = 12-2 = 10 - 2. Thus if z in- iB a = creases, 2 decreases and so ~$ increases. Hence } increases when z increases. Or, a decreases when = increases. In other words, 1%; > ygooor: The same argument applies generally asINEQUALITIES 7 indicated in Example 5. Show that k reros a aw (k+1) zeros (41) zeros Example 6. Show that (1.01)! > 1000. Solution. By Bernoulli's inequality (1 + .01)* > 1 +.08 and 80 (1.01)'00° > (1 +08)! = ((1 + .08)5)5 > (1 + .4)?5 > (1 +4)? = ((1.4)3)8 > (2.7)8 > 74 = 2401 > 1000. 12366665 _ 12366666 25633321 ~ 25633322" Solution. If the left hand number is £, then the right one is 241. From the difference Example 7. Show that if and only:if z > y, it follows that the right hand member is greater than the left hand member as desired. Example 8. Show that 1-}+4 Solution. }-}+}-f4--h 45 - eee i 4 1 1 1 (-3)+(i-§) +--+) + 1 é 1 6 +o 44 98x99” 100° Boi 07 0075 tote a 20 a > at 4 1 $,1-(j-f4 poe as + 1a) <2 Example 9. Which is greater 150° or 20000! x 19910028 NON-ROUTINE PROBLEMS IN MATHEMATICS Solution. 1503.< 150 x 150 x 150 = 30 x 30 x 30 x 125 = 27000 x 125 > 20000 x 100. Hence 150° = (150%)! > 20000! x 10019 Example 10. Find the largest of the numbers: 5100, G91 790, gas Solution. Write the powers of 5,7,8 as follows: Powerof 1 2 3 4 5 6 ot 5 5 25 125 625 3125 15625 78125 i 7 49 343 2401 16807 117649 823543 8 8 64 S12 4096 32768 262144 2097152 Thus 8¢ = 4096 > 3125 = 5° so that 88 > 8® = (81) > (55)? = 5! Next, take 2° x 39! = 6% and 88 = 255, Canceling out the common factor, we need to compare 3°! and 264, To do this, note that 2° = 256 > 3° = 243 so that 264s 9182 — (28)19 > (35)!9 = 39 > 3°! Thus, 8® > 6%. It remains to compare 7” and 8°°, From the row relating to pow- ers of 8(= 23), 2"7 = 8 x 4 = 32768 x 4 = 131072 > 117649 = 7. Hence 88° = 2°55 = (2!7)!5 > (75)!5 = 7° proving that 885 > 7°. So, 88 is the largest of the four numbers. § 2. In the previous section we considered inequalities relat- ing to given-real numbers and observed that the inequalities can be obtained using some general inequalities like the Bernoulli inequality. We now consider general inequalities. Note that the variables which occur can take only real values not non- real complex values. Most of these general inequalities revolve around the fact that for any real number x, 2? > 0. Observe that this is not the case for 2” unless n is even. Also if we consider a rationalINEQUALITIES 9 number p/q, p € 2, the set of all integers, g € N, the set of all natural numbers, then 2*/* may not be defined for some as a real number. e.g. (—5/2)°/? is not defined. On the other hand, it is known that if p is any natural number and y is a non-negative real number, there exists a non-negative real number z such that 2” = y. x is deuoted in this case, by y'/* or 4g. The use of radical y/ and, in particular, 7 (for the square root), is‘conventionally limited to this non-negative real number z. Arithmetic Mean (A.M.) of a set of n positive real numbers, @1,42,-+- ,@p is defined to be ay +02 + n +an i.e. it is the average value of the n numbers. Geometric Mean (G.M.) of the same set of numbers is de- fined to be Yay X a2 X-** X Gn. If a,b > 0, a, then *$*,b are such that the difference between consecutive terms, viz. f+ — a, b— *4 are each 7 ile. the same. This is otherwise described by telling that the three terms form an arithmetic progression (A.P.). 4% is thus an (AM. inserted between a and b to get an A.P. Again, a, Va x 6, ab an aby are each vi ile. the same a, a-6,b is said to form a geometric progression (G.P.) and Vab has been inserted (as a G.M.) between a and b to get a G.P. AM. - G.M. inequality: vas*>? 0) b are such that the quotient of consecutive terms, viz. Proof. (1) is equivalent to 2Vab < a + 6 (multiplying an10 NON-ROUTINE PROBLEMS IN MATHEMATICS inequality by a positive real number does not alter the inequal- ity), ie. 0 < a+b —2Vab (subtracting the same real number * from both sides of an inequality does not alter the inequality), ie. a+b—2Vab = (Va— Vb)? > 0 (Note that Vab, /a, Vb are uniquely defined.) which is true from our remark at the very beginning of § 2. Note. The proof shows that Vab = *# if and only if a = Vb or, equivalently. a = b (Recall the remark on the uniqueness of the nonnegative root.). To sum up Vab < “#4, ie. G.M. < A.M. and equality occurs if and only if both the quantities are equal. The G.M. - A.M. inequality is true in the general form Yar an < ate tan n equality occurring if and only if a = a2 = Op, It is easy to deduce it for a’set of 4 positive numbers from the case of 2 numbers proved earlier. For, Yajaza3ag = Yajaq- Yazaq Vara - fase 1 3 (Vaia2 + Ya3a4) ; (Je +42) + Flas + 2) a) +42 +43 +44 4 7 A IA Note. The above method of proof can be extended to.the case n= 2* for some k = 2,3,4,--+. To prove a +2 +3 Yaj0203 < 3 (2)INEQUALITIES sae for a; >0, §=1,2,3, set a1 ==}, a2 = 23, a3= 23, 2; >0, i = 1,2,3. (2) becomes 3ayzars Sh + 2} +23 or 2} +2} + 23 — 32,2273 > 0. The I-h.s. of (3) can be rewritten as (x) + 22 + 23)(2? + 23 + 23 — 2109 — 2223 — 2301) 2 2 2 ry — + (x2 — 23)? + (23 — 21) (ert +m) (ramet | 3)? + (a3 — 21)"} 20 since the sum of the three squares is always nonnegative. Note also that equality can occur if and only if 2; = 22 = 73, or a, = a2 = a3. Note. The proof for the general case of n is by finite mathe- matical induction, a topic to be taken up in another lesson. Example 11. If a,b > 0 and a + 6 = 1, show that 1 1 8+at [8+ gy 24 Solution. By A.M. — G.M. inequality 1 1 z 1 [e+ at ys+p 28+ ay 8+ a 1 1 1 in af us0(S+5) +an} 16 1 2y 64+ + ae 2V64 +16 x 4+ 16 2v144 = 2x12 24 Vv IV Vv12 NON-ROUTINE PROBLEMS IN MATHEMATICS since *$¢ = } implies } > Vab or Fez > 2. Example 12. For any positive a,b, show that 2 1)? (o+2) +(o+5) 28 a b Solution. By A.M. — G.M. inequality (3) iV ef) OY a) = bye 2) > 2) =8. 2(oos + $42) 2204 ) Vv Note. For x > 0, from A.M. — G.M. inequality it follows that rti>d2 Example 13. For any real x,y,z, show that wey tz? > ay tyzt 20. Solution. By A.M. — G.M. inequality x? + y? > 2zy, y+2? > 2yz, z? + 2? > 2y, irrespective of whether z, y,z are positive or negative. Adding these inequalities and canceling the factor 2 on both sides we get the result. Example 14. — If aj,a2,---,a, are nonnegative and 014) -++ Gy = 1 show that (1 +a1)(1 +@2)-+-(1 + an) > 2". Solution. By A.M. — G.M. inequality 1+ > i 7 7 2 Va, §= 1,2, Multiplying the inequalities (1+ a1)++-(L +n) > 2" Yayag- ay = 2",INEQUALITIES 13 Example 15. If ai,a2,a3 > 0, show that 1 1 1 9 a a2 a3 ~ a +a2+03° Solution. By A.M. — G.M. inequality a) ecco a a2 03 Yera203 ; 1 3 By the same inequality 2 pate So, ile 9 + = 2 ay" a2 a3 > a +42 +43 Example 16. If a,b,c > 0, show that a,b c —+— 2 3/2. bret cra athe /2 Solution. Bi RE da HE oie = HE so that, 1 1 L tis. =(orbro{ to teeth as, But 1 1 1 fea T T gories eoon sh ores —— + ——__ + — bret erat ate 2 Vote * cat ate Aatb+e) = (b+c)+(c+a) + (a+b) > 3¥b+etetatatb ‘80, IV Vv14 NON-ROUTINE PROBLEMS IN MATHEMATICS Note. A geometric interpretation of the A.M. - G.M. inequality. & Take segments of length a,b on a straight line putting them side by side along AB A € and BC. Take the midpoint D of AC. Erect a perpendicular to AC at B to cut the semicir- e cle on AC at BE. If E’ is the other point of intersection of ED produced with the complete circle, AC being a diameter perpendicular to the chord EE" bisects EE’. By the “secant theorem” AB - BC = a-b= E'B- EB = EB. Or, EB = Vab, ie., EB represents the G.M. of @ and 6 the A.M. being AD = radius of the circle. Since in any circle half of a chord is less than the radius (the diameter is the longest chord) Vab <= ‘#4. It is also clear that equality occurs if and only if B and D coincide, ie. a = b, §3. Another interesting inequality is Cauchy's inequality or Cauchy-Schwarz inequality as some people call it. If a, bzy are real, then lax + by] < Va? + 62/2? +92, |-| denotes the absolute value of the real number inside it, Proof. To prove (az + by)? < (a? + 6)(2? + y2) (4) a?z? + 2azby + by? < a2? + ay? + 62a? + by? 2azby < ay? + 622? ie. a*y? — 2azby + 64? >0 ie. (ay — br)? >0 which is true.INEQUALITIES 15 ‘The same method of proof shows that if aj,a2,+-+,an; b1,62,-++ ybn are all real, then layby + ag +++ sAndal S at +43 +--+ ah y/OF + OF + ++ BR. Note. If aj,bj,i 1,2,-++ ,2 are all nonnegative. there is no need to put |-| on the Lhs. e@y) axtbY =O Note. The inequality (3) also has a simple geometric inter- pretation. Let P(z,y) be a point in the plane referred to ~ a system of rectangular axes with origin O and let az + by = 0 be a given straight lax + by line through origin. Then is the perpendicular dis- d tance (PM) of (x,y) from the given straight line az + by = 0. V7 + y? is the distance of x,y from origin. Cleatly, the former is less, than or equal to the latter whatever be a,b. The slope of the line is —¢ and of the line joining origin (0,0) to (2,y) is ¥. If these two lines are perpendicular and only then ¥(—§) = -1 or $ = 4 and in this case and only in this case does equality occur. viz. PO = PM i.e. equality occurs in (3) if and only if ¥. This is also clear from the proof given éarlier. Example 17. Find the minimum value of Va? +y? when 32 + 4y = 15. Solution, [32 + 4y| < J+ PVFTR = sat ty by Cauchy's inequality. So, under the given condition va? + > B =3 and this value is reached (why?).16 NON-ROUTINE PROBLEMS IN MATHEMATICS Example 18. If a; > 0, i =1,2,-+* .7, show that ay tap te tan < nl +a;). Solution. ‘Take-6; = 1, i = 1,2,-+-, and apply Cauchy's inequality. Example 19. Prove that if x; > 0, i= 1,2,---.n. 1 1 2 Ff Boy =))> 2. (a+ +m) (2 + +2) 2n Solution. Apply Cauchy’s inequality choosing a; = 1;, 6; = +. lsisn. Example 20. Prove that for any natural number n > 1 2 ’ (b+ qghytapty ttt) s(ht ete + a)’. Solution. Choose a; = } and b; = gh, i= 1,2,--,n and apply Cauchy's inequality. § 4. Ifa,b are any real numbers and'|-| stands for absolute value, we know that Ja + | < Jal + fa}. (4) Recall that for any real number a, Ja| > 0 and |al = 0 if and only if a= 0. —a < |a| 2 for all z. Solution. If a = 2-5,b=3-x la +6] =|e-54+3—2]=2< fe—5] +|3—zI. Example 22. Show that x? — |r| +1 > 0 for all z. Solution. If |z| < 1, -|z]+1 = 1-2] > 0. Hence x? — |x] +120. If |x| > 1, 2? = |x|? > |x| so that 2? - |x| > 0,18 NON-ROUTINE PROBLEMS IN MATHEMATICS Example 23. Show that. ([:r| + yl)? — 2lz + yl +22 0 for all ay. Solution. |x| + |y| > |z + yl. so that (lal + ly)? —2(le+ yl) +1 > (lel + lull? - 2Ulel + byl) +2 ((2| = 1)? + (ly = 1)? > 0. Note. a +b] = [al + |b] if and only'if ab > 0. For. in such a case ja +b)? = (a +0)? = a? + 2ab +0? = (lal + [bl)? = {o2] + 2jal fo] + [bl2. Since a? = Jaf’, 6? = [o/2, it follows that equality occurs if and only if 2la| |b] = 2ab or |ab| = ab or ab > 0. Example 24. For what values of x does fe — 10] + |8 — 2| = 22 Solution. 2 = |x — 10 +8 — | so that equality occurs when (z - 10)(8 — x) > 0, ie, when both x — 10 and 8-2 >0or both x — 10 and 8 - z > 0. ic. either 8 > x > 10 (impossible) or 8 b> 0, 1e=t? < a4? ~Vab (= AM. - GM) < 1(¢=? 7S Veb (=A.M. - G.M.) 47-5 . tb fa—VJo)? (a~t + Solution. #4 — Vab = WEY < 16-9 if we prove that (Va + Vb)? > 4b, ne. (\V/F+1) > 4, which is the case § 2 1. The first inequality is similarly proved.INEQUALITIES 19 Recall that if a1,a2,--- ,@n are nonnegative quantities in A.P. (see §2), then a +ag +--+ an Hence, the A.M. > G.M. inequality takes the form ata, Yarar-@n<—>— $F (8) if'a,,+++ jan are in A-P. Also, if d is the common difference, viz. d = a2 — Q) = G3 — 2 = ++ = Og — OR-y = ++) = An — An-1, then ay = a) + (k — 1)d, 1 4)@n, k = 1,2,--- ,n. From these inequali- ties (a1a2-+-an)? = (a14n)(az@q-1)+-- (any) 2 (aan). Hence Vaan < /aja2~-- On (9) Combining (8) and (9) we have for an A.P. a1,a2,--- ,an of positive terms G.M. of first and last term = (/ajGq < Yajaq--G, = G < stan A.M. of the first and last term (10) Example 26. Prove that for any natural number n vas Vals 2h20 NON-ROUTINE PROBLEMS IN MATHEMATICS where n! (n factorial) = 1-2-3+-+n. Solution. Put a; = 1,a2 = 2,--- ,an =n in (10). For «« > 0. we have the identity l+ne 1+(n-1)t +(n—Dz 1+(n-2)e (a) lt+nr= for any natural number n. Note that, for & = 0,1,2,---,2-1, z__lt(ntiz T+nz lt+nz * Hence, from (11), EGE DEY" ie. Utnay! > (14 (n+ 10)" l+ur> l+nzr In particular putting z= x25, a >0 a \nl ae (+545) >(+8) and when a = 1 eee Inequalities proved using other techniques and relating to geometry will be taken up in other lessons. PROBLEM SHEET 1. Prove that <$-3-3-- Mc, 2. P. 1 1 sae 1 g rove that Thy + ig + + Jovi > 3 3. If u is a natural number, show that 1 1 2(vn+1-1) <1+24+—}4.. ( Isla aSon 10. INEQUALITIES 21 . If a,b,¢ > 0, then show that. ab + be + ca > aVbe + bea + eVab. . For any real numbers a,b,c shaw that al +b! +c! > abela+btc). If x > 0, show that. 3x3 — 6x? + 4 > 0. . Prove that for any real x x(a + 1)(x +2)( +8) > -2. . If zy € [0,1]. show that z y . If z,y > 0, find the maximum of the minimum of the values of x, b y+i. Prove that, if a,b,c,d > 0, then Vat o)(b +d) > Vab + Ved.LESSON 3 DIVISIBILITY OF NUMBERS In this lesson we take up the idea of divisibility in the nat- ural number system. For example 6 = 3.2. 3 and 2 are called divisors or factors of 6. Similarly 2,4,8,16 and 1 are divisors of 16. In general if a = be where a,b,c are natural numbers then 6 and.c are called divisors or factors of the natural number a. If and m are two given natural numbers, the largest or the greatest natural number d among:the common divisors-of | and % is called the greatest common divisor of | and m written in short as g.c.d. Note that g.c.d.(I,m) is at the least 2. Also, that g.c.d.(a,0) = a by definition, though 0 is not a natural number. The smallest.natural number k such that both / and m are divisors of k is called the JeAst common multiple of | and ‘m, written in short as lcm. Similarly, we can talk of g.c.d and |.o.m of 3,4,5 etc., or more generally, a finite set of natural numbers. Ifa and b are two integers sich that a—b is divisible by a natural number d or equivalently a and 6 leave the same remainder when divided by d, we write this as a = b (mod d). a = 0 (mod d) means that d is a divisor of a, which we also write as dla. Recall that if a natural numiber p is such that 1 and p are the only divisors of p, then p is called a prime number. If the natural numbers a and,b have d as a g.c.d. of @ and b, then we write this as (a,b) = @. If (a,b) = 1, then we see that a and b have no common divisors other‘than 1. ‘There are certain simple facts that one has to remember in testing the divisibility criteria for a number by a given number. It is obvious that-any even number is divisible by 2. Any suchDivisipiLity OF NUMBERS 23 number should end up with 0, 2, 4, 6, 8 in its unit's place. A number is divisible by 3 if and only if the sum of the digits of that number is divisible by 3. Similarly a number is divisible by 9 if and only if the sum of the digits of that number is divisible by 9 (Prove these two statements.). A number is divisible by 4 if and only if the two digit num- ber formed by the last two digits of the given number (i.e. digit in the 10th place and the digit in the unit place taken together) is divisible by 4. Similarly you can think of divisibility test for 5,6 etc. It is clear that if d divides a (notation: dja) and 6, it di- vides, a + 6. In our notation a = 0 (mod d), 6 = 0 (mod d) imply together a + 6 = 0 (mod d). More generally, a = ¢ (mod m), 6 = d (mod m) together imply a+b = c+d (mod). eg. a = c (mod m) > a—c = 0 (mod m), b = d (mod m) = 6—d = 0 (mod m) so that a-c+6—d = 0 (mod m) by our earlier observation, i.e. (a +) ~ (c+ d) is divisi- ble by m. a +6 = (c+) (mod m). In the same way we have @=c (mod m), b =d (mod m) = ab = ed (mod m). In particular, @=c (mod m) = a? = (mod m). More generally a = c (mod m) = a® = " (mod m), nEN. (Supply the details for justifying these assertions.) We now take up some problems involving these ideas. Example 1. All the 3-digit numbers from 130 to 164 are writ- ten consecutively to form the number N = 130131132--- 164. Find the largest power of 3 that divides N. Solution. Let us first find the sum of the digits of N.24 NON-ROUTINE PROBLEMS IN MATHEMATICS loccurs (164—129)+4 = 39times; 2occurs 4 Soccurs 10+4 4occurs 10+4 5 occurs 10+3 39 4times; theirsumis 8 14 times; their sum is 42 14 times; their sumis 56 13 times; their sum is 65 u 6 occurs 54+3 = 8times; theirsumis 48 7 occurs 3 = 3times; theirsumis 21 8 occurs 3 = 3times; theirsumis 24 9 occurs 3 = 3times; theirsumis 27 Total 330 Total sum of all digits in N is 330, which is divisible by 3 but not 9. Hence 3! is the highest power of 3 that divides N. Examples 2. Find the g.c.d. of 228 and 177. Solution. We now give a general process which is used to find gc.d. of two numbers using a fact known as Euclidean algo- rithm. ar 228 = LIT7+51 in| 2-1-9 177 = 351424 si] -a—% Sl = 22443 “|! si-2—3 2 = 83+0. 3] mw-8-~o9 ‘The above process can be exhibited as Thus 3 is the g. of 228 and 177: For, 228 = 1.177451 1x (3 x 51 + 24) +51 = 1 x (3 x 51 + 24) 42x 2443 = 1x (3x 51424) +2x8x 343 =3x514+3x843%K8x343 =Divisipitiry OF NUMBERS 25 3(51 +8 + 16 +1) =3 x 76. More generally we can find the g.c.d. of any two given numbers a and 6 using the above process. The fact which we used is the following algorithm: Euclidean Algorithm. If a is any integer greater than or equal to 0 and 6 is a’ natural number, then there exists a non- negative integer q such that a=bqtr where r is an integer satisfying the inequality 0 < r < 6. For, first observe that either a itself is a multiple of b or lies between two successive multiples of b. ie. bg < a < 6(q +1) for some integer q. If bg = a, then we can take r = 0 and write a = bg +r. If not, bg 4, >1rz>-++ and there can be only a finite number of r’s between 0 and 6. When rn—1 = rndn+1s then we see that (a,b) = gcd. of a and b= rq. For, it is easy to see from each of the above equations that (a,8) = (byr1) = (ris72) = +++ = (Pn 0) = Tn Check this argument with reference to Example 2. Exercise: Find the greatest common divisor of (i) 184, 7: (ii) 163, 24; (iii) 265, 53 using the above method. Example 3. Find one solution of 7z + 1ly = 13 in integers < and y and then the general solution of the equation. Solution. Note that (7,11) = 1. We have 7(-3) + (2) = 1 so that 7(13 x (-3)) + 103 x 2) = 13 (See Example 6 below). So z = —39 and-y = 26 is a particular solution. Let 2, y be any solution. Then a+ ly =13, 7(-39) +11(26) = 13 Hence T(x + 39) = 11(26 — y). Since 7 divides the left hand side, it must divide the right hand side. but 7 is relatively prime 11. So 7 divides 26-y. Thus +39 26-y fe = an integer r. Consequently, z+39=Ur, 26-y=7r, g=Ur-39, y=26-7r. On the other hand, if x = 11r—39, y = 26—7r, then the given equation is satisfied. Hence the general solution is given by z=~39+1lr, y= 26-77,Divisieitity OF NUMBERS 27 where r = 0, 41, +2,- Example 4. Show that the equation 3z + Gy = 22 has no integer solutions x and y. Solution. First note that (3,6) = 3. If we can find integers p and q such that 3p + 6q = 22, then 3 must divide 22 which is impossible. Example 5. Find the least positive number that leaves the same remainder 3 when divided by 5, 7, 15, 21 and 33. Solution. The least positive number that leaves as remainder 0. when divided by 5, 7, 15, 21 and 33 is simply the Lc.m of these numbers which is 1155. So 1158 is the required number. Example 6. Given two natural numbers a and 6, let r be the least positive integer expressible in the form az+by=r with z and y integers. Then r is the g.c.d. of a and 6. Solution. For, it is easy to see that any common divisor of a and 6 is a divisor of r. So, it is enough to show that r is divisor of a and 6. Suppose that r does not divide a. Then, using Euclidean algorithm we can express a as a=qrtswithO 1, there exist PisP2s-*+ ;Pk which are primes and a1,02,--- ,a% € N, such that n= pt! py? pyt where p1,p2,--~ ,Pk are uniquely determined but for the order of their arrangement and _~— the _correspond- ing a1,-++ a4 are uniquely determined. If m = pf'---p2#, n = q---gft,(m,n) # 1 if and only if there exists a pair (A, 1 SESH UST SL p= Gy. Also (mn) = Pert where r; = py = qj for some pair (7, j") and yj = max(ay, B;) and ane er Loam. (myn) = pips? --gfhglt of! where Bj = 0 if pj = gj for some pair (i, j) and a! = ay, = By if pi # gj for any pair (i,j) af = max(ai,f;) if pi = gy for some j. Example 11, Find g.c.d. and l.c.m. of 228 and 177.30 NON-ROUTINE PROBLEMS IN MATHEMATICS Solution. 228 = 2?.3-19; 177 =3-59. So, g.c.d. (228,177) = 3 Le.m. (228, 177) 3-19-59. Example 12. Find g.c¢.d and L.c.m of the two numbers: 2.37.11? and 3°- 117-79. Solution. g.c.d of the two numbers is 3°- 112. L.c.m. of the two numbers is 2°. 37. 117. 75. Example 13. Find the least n such that n! is divisible by 990. Solution. 990 = 2-5-3?.11. n should be at least 11. In 11! we have the factors 2,5,3.and another 3 from the factor 6. Hence n= 11 is the least desired value of n. N a PROBLEM SHEET . Find the g.c.d. ,of 576 and 73 and find integers x and y such that 576x + 73y = (576,73) . Find the g.c.d. of the numbers 2! — 1, 9120 _ 1. . Show that for any natural number n, g.cd. (2n + 13,n+7) =1. - Show that for any natural number n the fraction 12+ cannot be reduced further. . Solve the following equations in integers x and y if they have solutions and then find the general solutions10. DivistBiLity OF NUMBERS 31 (i) 3a — 4y = 29 (ii) Liz + 12y = 58 (iii) 462 + 345y = 69 (iv) 462 + 345y = 92 (v) 46x + 345y = 24 (vi) 46x + 345y = 41 From the answers to (iii), (iv), (v) and (vi) above can you guess when an equation of the form az + by = c, where a,b and c are integers will have integer solutions for z and y. . Show that if the product of an odd number of odd integers is of the form 4n+1, then at least one is of the form 4n+1. . Solve the congruence equations: (i) 52 =3(mod 11) (ii) 7¢ = 4 (mod 3) (iii) 62 = 22 (mod 8) (v) Lz = 33 (mod 58) In each case find how many distinct solutions exist. . Solve the equation (i) 23 = 2% (mod 7) (ii) 8 = 2 (mod 7) (iii) 18 = 2? (mod 7) (iv) 10 = 2? (mod 7) (v) 19 = 2? (mod 7) (vi) 20 = 2? (mod 7) . Can a number whose digits which are one hundred zeros, one hundred 1's and one hundred 2’s be a perfect square? Justify your answer. Show that there exists n such that n+1,n+2,--» ,n+1999 are all composite.LESSON 4 PERMUTATIONS AND COMBINATIONS In this lesson we will discuss, how to solve non-routine prob- lems in permutations and.combinations. The following points may prove helpful in solving these problems. 1. Multiplication Principle of Counting: If the sets X1,X2,+++Xn contain a), a2,---a_ number of elements respec- tively, then n elements, one from each set can be selected in @1a2-++@p, ways. The reason is that if there are just two sets X;, Xo, for each choice of an element of Xj, there are a2 choices of elements of X2 to go with this element. So, for the number a; of choices of elements of X1, the number of choices is a; x az. The same argument can be repeated for each choice of elements of X1,X2 when choosing element of X3 and so on. This principle of counting is clearly illustrated in the fol- lowing example. Example 1. In the following figure, there are 3 different routes from Madurai to Trichy, 4 routes form Trichy to Chennai and 2 routes from Chennai to Tirupati. Then in how many ways can one go from Madurai to Tirupati? Trichy Tirupati Madurai ChennaiPERMUTATIONS AND COMBINATIONS 33 Solution. Let the set A denote the set of routes from Madurai to Trichy, the set B those from Trichy to Chennai and the set C from Chennai to Tirupati. Now with each element of A we can associate any of the four elements of B. The number of elements in A is 3, each represeriting a route from Madurai to ‘Trichy and the number of elements in B is 4 each denoting a route from Trichy to Chennai. Also each association represents a route from Madurai to Chennai through Trichy. The number of such associations is clearly 3 x 4 = 12. Now let X be the set of 12 routes from Madurai to Chennai through Trichy. Arguing as before to form associations between elements of X and C, we can show that the number of routes from Madurai to Tirupati through Trichy and Chennai in that order is 12 x 2 = 24. Hence one can reach from Madurai to Tirupati in 24 ways. 2. Permutations and Combinations: Let there be three persons a,b.c to be arranged in a row. ‘There is op- tion therefore in the order in which they are placed. All possible ways are exhausted by the following arrangements. a, bc a,c, b baa ba, oa, b ¢ ba whose number is 6. The multiplication principle discussed in §1 can be used to conclude this fact as follows. The first place can be filled in 3 ways by putting one of a,b,c. After this the second place can be filled in.2 ways by putting one of a,b,c left out after filling the first place. After this there is only one left to be put in the third place. Thus the number of ways of34 NON-ROUTINE PROBLEMS IN MATHEMATICS arranging the three persons is 3 x 2x 1 = 6. Note. The persons are distinct. On the other hand if there is a red ball and two white balls and if they are to be put in three holes Hy, H2, H3 in that order, there are only two ways of filling H, (if the colour of the ball alone matters). Depending on whether we have chosen the red ball or the white ball, Hz can be filled in either only one way or two. In any case H3 can be filled after this in only one way. In other words, if R stands for red ball while W for a white ball the arrangements are Hy Hy Hs RWW w RW WWwWR In this case if the two white balls are put in two chosen holes the red ball has to find its place in the third one. Thus it is just a choice with no arrangement of two holes out of the three holes Hi, H2, H3. With due regard to order of occurrence, the number of ways of arranging n things is known as the number of permutations of the n things. If we are not to arrange all the n things given but only r of them, r ways. So the number of ways of placing the balls in the urns in this case is sC, x 4C1 x 3C3 x 302 = 5x4x1x3= 60. Case 2. Suppose that 5 balls are placed in 3 distinct urns as follows: 1 ball in the first urn 2 balls in the second and 2 balls in the third urn. Arguing as in Case 1, we can show that the38 NON-ROUTINE PROBLEMS IN MATHEMATICS number of ways of placing the balls in the urns in this case is sC1 x 4C2 x 202 X 30, = 5 X6 x1 x3 = 90. Now Case 1 and Case 2 are mutually exclusive and exhaus- tive cases. So the total number of ways of placing the 5 balls in three distinct urns so that no urn remains empty (by using addition principle of counting) = Number of ways in Case 1 + number of ways in Case 2 = 60 + 90 = 150. 3. Some times the construction of a function f(n) and a linear equation connecting f(n), f(n — 1) and f(n — 2) where n € N or NU {0} may prove useful as in the solution of the following example. Example 8. There are n letters and there are n envelopes with n distinct addresses to which the n distinct letters are to be sent. In how many ways can one place all the letters in all wrongly addressed envelopes. Solution. Let all the letters be denoted by a1,a2,++-aq and the envelopes with corresponding addresses by Ay, 4g,--+ , An. Let f(n) denote the required number of ways ie., the number of ways in which all the n letters can be placed in the wrong envelopes. Here n is a natural member. Now the letter a; can be wrongly placed in any one of the (n ~ 1) envelopes Ap, Ag,-++ , Ax. Suppose that a; is placed in the envelope Ay. Then two cases arise:- Case 1. Let the letter a,,k # 1, be placed in the envelope Ay which is a wrongly addressed envelope for the letter a,. In this case remove the letters ay, ay and the envelopes Ay, Ag the number of ways in which all the remaining (n — 2) letters are Placed in the (n —2) envelopes all wrongly is equal to /(n — 2), i.e., all the n letters are placed in the wrongly addressed en- velopes in f(n — 2) ways in this case,PERMUTATIONS AND COMBINATIONS 39 Case 2. Suppose that the letter a, is not placed in the envelope Ai. Then in this case all the (n — 1) letters 4, 03,-+ ,@q have to be placed wrongly in the (n—1) envelopes Aj, Aays+* )Ak-1) Ai, Asis >> sAn(2 Sk » Ak-1, Ai, Akyi,**+ , An and we are to get the number of ways in which the (n — 1) letters should all be placed in the (n — 1) envelopes wrongly. By definition of f this number is {(n—1). So, if the letter a; is placed in a particular envelope Ag,k # 1, wrongly, then the total number of ways in which all the n letters are placed in the n envelopes wrongly, is, by Case 1 and Case 2, equal to f(n— 2) + f(n— 1). But the same argument can be repeated if the letter 2 is placed into any of the (n — 1) wrongly addressed envelopes. So the total number of ways in which all the n letters can be placed in the wrongly addressed envelopes is equal to (n —1){f(n—1) + f(n—2)}. So we have the following linear relation connecting f(n), f(n — 1) and f(n—2): f(r) ~I{f(n-1) + f(r—2)} > f(n)-nf(n-1) = -{f(n-1)-(n-1f(n—2)}. Similarly, f(n=1) —(n-1)f(n- 2)=-{F(n - 2) -(n- 2) f(n - 3)} £(3) - 3f(2) = -{F(2) - f(1)}- But clearly we have f(2) = 1 and f(1) =0. So (3) — 3f(2) -{1-0}=-1, £(4) — 4f(3) (-1)(-1) = (-1), u40 NON-ROUTINE PROBLEMS IN MATHEMATICS (5) -57(4) = —(-1)? = (-1)5, Hn) =nf(n-1) = (-1? = (-1)" which implies that f(x) _ nf(m=1) _ (-1)" n! n! n! f(r) _ (m=) _ (-1" a @ei on Q) Similarly, f(n=1)_ f(m=2) _ (-1)"-! (2) (e=1)! (2-2)! f(n~2) _ f(n-3) _ (1)? (n=2)! ~ (2-3)! (aT &) £2) _ FQ) _ (-1)? Adding these n — 1 equations (from (1) to (n 1), we have nee =I)" foyant {edad a}. Hence the total number of ways in which n distinct letters can be placed into n wrongly addressed envelopes in equal to ede (-1)" ann gtgct il }. Note. The solution can be simplified using the exclusion in- clusion principle. 4. Division of objects into groups. We illustrate this method by examples. tPERMUTATIONS AND COMBINATIONS 41 Example 9. A fruit-seller sells 4 types of mangoes; neelam, malgoa, sendur and daseri. In how many ways is it possible to purchase 7 mangoes? Solution. This problem is not a problem of permutating with repetitions, for the order of the mangoes in any purchase is immaterial. This problem is closer to the combination type; and the combination may involve repeated elements. For convenience we will represent each purchase by-means of zeros. First write the number of units to denote the number of neelam mangoes. Then put a zero to separate neelam from malgoa. Then put the number of units to indicate the number of malgoas purchased. Again put a zero to seperate malgova from sendurs, and then write the number of units to denote the number of sendurs purchased. Again put a zero to separate sendur from daseri and finally put the number of units to denote the number of daseris purchased. For example, if we purchase 2 neelams, 3 malgoas, 1 sendurs and 1 daseri, the purchase will be denoted by 1101110101. If there is no unit between two zeros, it means that the particular variety of mango has not been purchased. For example, 00111011011 means no neelam, 3 malgoas, 2 sendurs and 2 daseris. So, the number of distinct purchases is equal to the number of permutations of 7 units and 3 zeroes, taken all at a time. That is, the required number is #91 = {29% = 120. Example 10. Find the number of ways in which (m+n +p) different things can be divided into three groups containing m,n and p things respectively. Solution. First select m things out of (m-+n-+p) things which can be done in m4nspCm ways, then select n things from the remaining (n + p) things in n4pCn ways and finally, p things42 NON-ROUTINE PROBLEMS IN MATHEMATICS and to be selected from p things in »C, ways. So the required number of ways is imentp)Om X ntpCn * pCp (m+n-+p)! i (n+p) elie (m+n+p)! (n+ ppl nip! minipl Caution. If m =n = p, then all the 3 groups have equal numiber of things say, m. So the required number of ways will be = 5. Applications to geometry. In combinatorial problems in- volving geometry the students should note that (1) Two points determine a straight line and two non-parallel straight lines de- termine a point called the point of intersection. (2) 3 points which do not lie on a line determine a triangle. (4) Four points in a plane, no three of which lie in a line determine a quadri- lateral. These facts facilitate in counting the required number of geometrical objects (points, line etc.) in specific problems as illustrated in the following example. Example 11. There are n points in a plane no three of which are in the same straight line with the exception of m(< n) points which are all in a straight line. Compute the number of (a) straight lines and (b) triangles which can be formed by joining the points. Solution. (a) As two points determine a straight line, the number of straight lines formed by ing n points is »Cp. But m of these n points lie on a straight line, so joining any two of these m points will determine the same line and no other line is formed. So to find the required number of lines we have to substract mC2— 1 from C2. That is, the required number of straight lines is »C2 = mC2 +1. (b) Arguing as in (a) we can conclude that the number of