A primer for preRMO and RMO plane geometry with basic exercises

Plane geometry is axiomatic deductive logic. I present a quick mention/review of “proofs” which can be “derived” in sequence….building up the elementary theorems …so for example, if there is a question like: prove that the three medians of a triangle are concurrent, please do not use black magic complicated machinery like Ceva’s theorem,etc; or even if say, the question asks you to prove Ceva’s theorem only, you have to prove it using elementary theorems like the ones presented below:

For the present purposes, I am skipping axioms and basic definitions and hypothetical constructions. I am using straight away the reference (v v v old text) : A School Geometry, Metric Edition by Hall and Stevens. (available almost everywhere in India):

Theorem 1:

The adjacent angles which one straight line makes with another straight line on one side of it are together equal to two right angles.

Corollary 1 of Theorem 1:

if two straight lines cut another, the four angles so formed are together equal to four right angles.

Corollary 2 of Theorem 1:

When any number of straight lines meet at a point, the sum of the consecutive angles so formed is equal to four right angles.

Corollary 3 of Theorem 1:

(a) Supplements of the same angle are equal. (ii) Complements of the same angle are equal.

Theorem 2 (converse of theorem 1):

If, at a point in a straight line, two other straight lines, on opposite sides of it, make the adjacent angles together equal to two right angles, then these two straight lines are in one and the same straight line.

Remark: this theorem can be used to prove stuff like three points are in a straight line.

Theorem 3:

If two straight lines cut one another, the vertically opposite angles are equal.

Theorem 4: SAS Test of Congruence of Two Triangles:

If two triangles have two sides of the one equal to two sides of the other, each to each, and the angles included by those sides equal, then the triangles are equal in all respects.

Theorem 5:

The angles at the base of an isosceles triangle are equal.

Corollary 1 of Theorem 5:

If the equal sides AB, AC of an isosceles triangle are produced, the exterior angles EBC, FCB are equal, for they are the supplements of the equal angles at the base.

Corollary 2 of Theorem 5:

If a triangle is equilateral, it is also equiangular.

Theorem 6:

If two angles of a triangle are equal to one another, then the sides which are opposite to the equal angles are equal to one another.

Corollary of Theorem 6:

Hence, if a triangle is equiangular, it is also equilateral.

Theorem 7 (SSS Test of Congruence of Two Triangles):

If two triangles have the three sides of the one equal to the three sides of the others, each to each, they are equal in all respects.

Theorem 8: 

If one side of a triangle is produced then the exterior angle is greater than either of the interior opposite angles.

Corollary 1 to Theorem 8:

Any two angles of a triangle are together less than two right angles.

Corollary 2 to Theorem 8:

Every triangle must have at least two acute angles.

Corollary 3 to Theorem 8:

Only one perpendicular can be drawn to a straight line from a given point outside it.

Theorem 9 :

If one side of a triangle is greater than another, then the angle opposite of the greater side is greater than the angle opposite to the less.

Theorem 10:

If one angle of a triangle is greater than another, then the side opposite to the greater angle is greater than the side opposite to the less.

Theorem 11: Triangle Inequality:

Any two sides of a triangle are together greater than the third side.

Theorem 12: Another inequality sort of theorem:

Of all straight lines drawn from a given point to a given straight line the perpendicular is the least.

Corollary 1 to Theorem 12:

Hence, conversely, since there can be only one perpendicular and one shortest line from O to AB: if OC is the shortest straight line from O to AB, then OC is perpendicular to AB.

Corollary 2 to Theorem 12:

Two obliques OP, OQ which cut AB at equal distance from C, the foot of the perpendicular are equal.

Corollary 3 to Theorem 12:

Of two obliques OQ, OR, if OR cuts AB at the greater distance from C. the foot of the perpendicular, then OR is greater than OQ.

Theorem 13 :

If a straight line cuts two other straight lines so as to make: (i) the alternate angles equal or (ii) an exterior angle equal to the interior opposite angle on the same side of the cutting line or (iii) the interior angles on the same side equal to two right angles, then in each case, the two straight lines are parallel.

Theorem 14:

If a straight line cuts two parallel lines, it makes : (i) the alternate angles equal to one another; (ii) the exterior angle equal to the interior opposite angle on the same side of the cutting line (iii) the two interior angles on the same side together equal to two right angles.

Theorem 15:

Straight lines which are parallel to the same straight line are parallel to one another.

Theorem 16:

Sum of three interior angles of a triangle is 180 degrees.

Also, if a side of a triangle is produced the exterior angle is equal to the sum of the two interior opposite angles.

Corollary 1:

All the interior angles of one rectilinear figure, together with four right angles are equal to twice as many right angles as the figure has sides.

Corollary 2:

If the sides of a rectilinear figure, which has no reflex angle, are produced in order, then all the exterior angles so formed are together equal to four right angles.

Theorem 17: AAS test of congruence of two triangles:

If two triangles have two angles of one equal to two angles of the other, each to each, and any side of the first equal to the corresponding side of the other, the triangles are equal in all respects.

Theorem 18:

Two right angled triangles which have their hypotenuses equal, and one side of one equal to one side of the other are equal in all respects.

Theorem 19:

If two triangles have two sides of the one equal to two sides of the other, each to each, but the angle included by the two sides of one greater than the angle included by the two corresponding sides of the other, then the base of that which has the greater angle is greater than the base of the other.

Conversely, 

if two triangles have two sides of the one equal to two sides of the other, each to each, but the base of one greater than the base of the other, then the angle contained by the sides of that which has the greater base is greater than the angle contained by the corresponding sides of the other.

Theorem 20:

The straight lines which join the extremities of two equal and parallel straight lines towards the same parts are themselves equal and parallel.

Theorem 21:

The opposite sides and angles of a parallelogram are equal to one another, and each diagonal bisects the parallelogram.

Corollary 1 to Theorem 21:

If one angle of a parallelogram to a right angle, all its angles are equal.

Corollary 2 to Theorem 21:

All the sides of a square are equal and all its angles are right angles.

Corollary 3 to Theorem 21:

The diagonals of a parallelogram bisect each other.

Theorem 22:

If there are three or more parallel straight lines, and the intercepts made by them on any transversal are equal, then the corresponding intercepts on any other transversal are also equal.

Tutorial exercises based on the above:

Problem 1: In the triangle ABC, the angles ABC, ACB are given equal. If the side BC is produced both ways, show that the exterior angles so formed are equal.

Problem 2: In the triangle ABC, the angles ABC, ACB are given equal. If AB and AC are produced beyond the base, show that the exterior angles so formed are equal.

Problem 3: Prove that the bisectors of the adjacent angles which one straight line makes with another contain a right angle. That is to say, the internal and external bisectors of an angle are at right angles to one another.

Problem 4: If from O a point in AB two straight lines OC, OD are drawn on opposite sides of AB so as to make the angle COB equal to the angle AOD, show that OC and OD are in the same straight line.

Problem 5: Two straight lines AB, CD cross at O. If OX is the bisector of the angle BOD, prove that XO produced bisects the angle AOC.

Problem 6: Two straight lines AB, CD cross at O. If the angle BOD is bisected by OX, and AOC by OY, prove that OX, OY are in the same straight line.

Problem 7: Show that the bisector of the vertical angle of an isosceles triangle (i) bisects the base (ii) is perpendicular to the base.

Problem 8: Let O be the middle point of a straight line AB, and let OC be perpendicular to it. Then, if P is any point in OC, prove that PA=PB.

Problem 9: Assuming that the four sides of a square are equal, and that its angles are all right angles, prove that in the square ABCD, the diagonals AC, BD are equal.

Problem 10: Let ABC be an isosceles triangle: from the equal sides AB, AC two equal parts AX, AY are cut off, and BY and CX are joined. Prove that BY=CX.

Problem 11: ABCD is a four-sided figure whose sides are all equal, and the diagonal BD is drawn : show that (i) the angle ABD = the angle ADB (ii) the angle CBD = the angle CDB (iii) the angle ABC = the angle ADC.

Problem 12: ABC, DBC are two isosceles triangles drawn on the same base BC, but on opposite sides of it: prove that the angle ABD = the angle ACD.

Problem 13: ABC, DBC are two isosceles triangles drawn on the same base BC, but on the same side of it: prove that the angle ABD = the angle ACD.

Problem 14: AB, AC are the equal sides of an isosceles triangle ABC, and L, M, N are the middle points of AB, BC and CA respectively; prove that (i) LM = NM (ii) BN = CL (iii) the angle ALM = the angle ANM.

Problem 15: Show that the straight line which joins the vertex of an isosceles triangle to the middle points of the base (i) bisects the vertical angle (ii) is perpendicular to the base.

Problem 16: If ABCD is a rhombus, that is, an equilateral four sided figure, show by drawing the diagonal AC that (i) the angle ABC = the angle ADC (ii) AC bisects each of the angles BAD and BCD.

Problem 17: If in a quadrilateral ABCD the opposite sides are equal, namely, AB = CD and AD=CB, prove that the angle ADC = the angle ABC.

Problem 18: If ABC and DBC are two isosceles triangles drawn on the same base BC, prove that the angle ABD = the angle ACD, taking (i) the case where the triangles are on the same side of BC (ii) the case where they are on the opposite sides of BC.

Problem 19: If ABC, DBC are two isosceles triangles drawn on opposite sides of the same base BC, and if AD be joined, prove that each of the angles BAC, BDC will be divided into two equal parts.

Problem 20: Show that the straight lines which join the extremities of the base of an isosceles triangle to the middle points of the opposite sides are equal to one another.

Problem 21: Two given points in the base of an isosceles triangle are equidistant from the extremities of the base: show that they are also equidistant from the vertex.

Problem 22: Show that the triangle formed by joining the middle points of the sides of an equilateral triangle is also equilateral.

Problem 23: ABC is an isosceles triangle having AB equal to AC, and the angles at B and C are bisected by BC and CO: prove that (i) BO = CO (ii) AO bisects the angle BAC.

Problem 24: Show that the diagonals of a rhombus bisect one another at right angles.

Problem 25: The equal sides BA, CA of an isosceles triangle BAC are produced beyond the vertex A to the points E and F, so that AE is equal to AF and FB, EC are joined: prove that FB is equal to EC.

Problem 26: ABC is a triangle and D any point within it. If BD and CD are joined, the angle BDC is greater than the angle BAC. Prove this (i) by producing BD to meet AC (ii) by joining AD, and producing it towards the base.

Problem 27: If any side of a triangle is produced both ways, the exterior angles so formed are together greater than two right angles.

Problem 28: To a given straight line, there cannot be drawn from a point outside it more than two straight lines of the same given length.

Problem 29: If the equal sides of an isosceles triangle are produced, the exterior angles must be obtuse.

Note: The problems 30 to 43 are based on triangle inequalities:

Problem 30: The hypotenuse is the greatest side of a right angled triangle.

Problem 31: The greatest side of any triangle makes acute angles with each of the other sides.

Problem 32: If from the ends of a side of a triangle, two straight lines are drawn to a point within the triangle, then those straight lines are together less than the other two sides of the triangle.

Problem 33: BC, the base of an isosceles triangle ABC is produced to any point D; prove that AD is greater than either of the equal sides.

Problem 34: If in a quadrilateral the greatest and least sides are opposite to one another, then each of the angles adjacent to the least side is greater than its opposite angle.

Problem 35: In a triangle, in which OB, OC bisect the angles ABC, ACB respectively: prove that if AB is greater than AC, then OB is greater than OC.

Problem 36: The difference of any two sides of a triangle is less than the third side.

Problem 37: The sum of the distances of any point from the three angular points of a triangle is greater than half its perimeter.

Problem 38: The perimeter of a quadrilateral is greater than the sum of its diagonals.

Problem 39: ABC is a triangle, and the vertical angle BAC is bisected by a line which meets BC in X, show that BA is greater than BX, and CA greater than CX. Obtain a proof of the following theorem : Any two sides of a triangle are together greater than the third side.

Problem 40: The sum of the distance of any point within a triangle from its angular points is less than the perimeter of the triangle.

Problem 41: The sum of the diagonals of a quadrilateral is less than the sum of the four straight lines drawn from the angular points to any given point. Prove this, and point out the exceptional case.

Problem 42: In a triangle any two sides are together greater than twice the median which bisects the remaining side.

Problem 43: In any triangle, the sum of the medians is less than the perimeter.

Problem 44: Straight lines which are perpendicular to the same straight line are parallel to one another.

Problem 45: If a straight line meets two or more parallel straight lines, and is perpendicular to one of them, it is also perpendicular to all the others.

Problem 46: Angles of which the arms are parallel each to each are either equal or supplementary.

Problem 47: Two straight lines AB, CD bisect one another at O. Show that the straight line joining AC and BD are parallel.

Problem 48: Any straight line drawn parallel to the base of an isosceles trianlge makes equal angles with the sides.

More later. Get cracking. This perhaps the simplest introduction, step by step, to axiomatic deductive logic…discovered by Euclid about 2500 years before ! Hail Euclid !

Cheers,

Nalin Pithwa

Solutions to “next number in sequence”: preRMO, pRMO and RMO

What is the next number in sequence?

A) 15, 20, 20, 6, 6, 19, 19, 5, 14, 20, 5, ?

Solution to A:

Ans is 20. The sequence is the position in the letter of the alphabet of the first letter in the numbers 1 to 12, when given in full. e.g. ONE: O=15.

B) 1, 8, 11, 18, 80, ?

Ans is 81. The sequence comprises whole numbers beginning with a vowel.

C) 1, 2, 4, 14, 21, 22, 24, 31, ?

Ans is 32, The sequence comprises whole numbers containing the letter O.

D) 4, 1, 3, 1, 2, 4, 3, ?

Ans. is 2. The sequence is as follows: there is one number between the two I’s, two numbers between the two 2’s, three numbers between the two 3’s and four numbers between the two 4’s.

E) 1, 2, 4, 7, 28, 33, 198, ?

Ans is 205. 1 + 1 \times 2 + 3 \times 4 + 5 \times 6 + 7

F) 17, 8, 16, 23, 28, 38, 49, 62, ?

Answer is 70. Sum of digits in all previous numbers in the sequence.

G) 27, 216, 279, 300, ?

Ans is 307. Difference divided by 3 and added to the last number.

H) 9,7,17,79,545, ?

Answer is 4895. Each number is multiplied by its rank in the sequence, and the next number is subtracted.

9 \times 1 - 2 = 7 \times 3 -4 = 17 \times 5 - 6 = 79 \times 7 - 8 = 545 \times 9 - 10 = 4895

I) 2,3,10,12,13, 20,?

Answer is 21. They all begin with the letter T.

J) 34, 58, 56, 60, 42, ?

Answer is 52. The numbers are the totals of the letters in the words ONE, TWO, THREE, FOUR, FIVE, SIX when A=1, B=2, C=3, etc.

Regards,

Nalin Pithwa.

Miscellaneous Questions: part I: solution to chess problem by my student RI

Some blogs away I had posted several interesting, non-trivial, yet do-able-with-some-effort problems for preRMO and RMO.

A student of mine, RI has submitted the following beautiful solution to the chess problem. I am reproducing the question for convenience of the readers:

Question:

The sixty four squares of a chess board are filled with positive integers one on each in such a way that each integer is the average of the integers on the neighbouring squares. (Two squares are neighbours if they share a common edge on vertex. Thus, a square can have 8, 5 or 3 neighbours depending on its position.) Show that all the sixty four entries are in fact equal.

Answer (by RI):

Let us denote the set of all integers on the chess board by S (assume they are distinct). [Now, we can use the Well-ordering principle: every non-empty set of non-negative integers contains a least element. That is, every non-empty set S of non-negative integers contains an element a in S such that a \leq b for all elements b of S}. So, also let “a” be the least element of set S here. As it is the average of the neighbouring elements, it can’t be less than each of them. But it can’t be greater than all of them also. So, all the elements of S are equal.

QED.

Three cheers for RI 🙂 🙂 🙂

Regards,

Nalin Pithwa

Miscellaneous questions: part II: solutions to tutorial practice for preRMO and RMO

Refer the blog questions a few days before:

Question 1:

Let a_{1}, a_{2}, \ldots, a_{10} be ten real numbers such that each is greater than 1 and less than 55. Prove that there are three among the given numbers which form the lengths of the sides of a triangle.

Answer 1:

Without loss of generality, we may take 1<a_{1}\leq a_{2}\leq \ldots \leq a_{10}<55…..call this relation (i).

Let, if possible, no three of the given numbers be the lengths of the sides of a triangle. (That is, no three satisfy the triangle inequality. Note that when we say three numbers a, b and c satisfy the triangle inequality —- it means all the following three inequalities have to hold simultaneously: a+b>c, a+c>b and b+c>a). We will consider triplets a_{i}, a_{i+1}, a_{i+2} and 1 \leq i \leq 8. As these numbers do not form the lengths of the sides of a triangle, the sum of the smallest two numbers should not exceed the largest number, that is, a_{i}+a_{i+1} \leq a_{i+2}. Hence, we get the following set of inequalities:

i=1 gives a_{1}+a_{2} \leq a_{3} giving 2 < a_{3}.

i=2 gives a_{2}+a_{3} \leq a_{4} giving 3 < a_{4}

i=3 gives a_{3}+a_{4} \leq a_{5} giving 5 < a_{5}

i=4 gives a_{4}+a_{5} \leq a_{6} giving 8 < a_{6}

i=5 gives a_{5}+a_{6} \leq a_{7} giving 13 < a_{7}

i=6 gives a_{6}+a_{7} \leq a_{8} giving 21 < a_{8}

i=7 gives a_{7}+a_{8} \leq a_{9} giving 34 < a_{9}

i=8 gives a_{8}+a_{9} \leq a_{10} giving 55<a_{10}

contradicting the basic hypothesis. Hence, there exists three numbers among the given numbers which form the lengths of the sides of a triangle.

Question 2:

In a collection of 1234 persons, any two persons are mutual friends or enemies. Each person has at most 3 enemies. Prove that it is possible to divide the collection into two parts such that each person has at most 1 enemy in his sub-collection.

Answer 2:

Let C denote the collection of given 1234 persons. Let \{ C_{1}, C_{2}\} be a partition of C. Let e(C_{1}) denote the total number of enemy pairs in C_{1}. Let e(C_{2}) denote the total number of enemy pairs in C_{2}.

Let e(C_{1}, C_{2})= e(C_{1})+e(C_{2}) denote the total number of enemy pairs corresponding to the partition \{ C_{1}, C_{2}\} of C. Note e(C_{1}, C_{2}) is an integer greater than or equal to zero. Hence, by Well-Ordering Principle, there exists a partition having the least value of e(C_{1}, C_{2}).

Claim: This is “the” required partition.

Proof: If not, without loss of generality, suppose there is a person P in C_{1} having at least 2 enemies in C_{1}. Construct a new partition \{D_{1}, D_{2}\} of C as follows: D_{1}=C_{1}-\{ P \} and D_{2}=C_{2}- \{P\}. Now, e(D_{1}, D_{2})=e(D_{1})+e(D_{2}) \leq \{ e(C_{1})-2\} + \{ e(C_{2})+1\}=e(C_{1}, C_{2})-1. Hence, e(D_{1}, D_{2})<e(C_{1}, C_{2}) contradicting the minimality of e(C_{1}, C_{2}). QED.

Problem 3:

A barrel contains 2n balls, numbered 1 to 2n. Choose three balls at random, one after the other, and with the balls replaced after each draw.

What is the probability that the three element sequence obtained has the properties that the smallest element is odd and that only the smallest element, if any is repeated?

Answer 3:

The total number of possible outcomes is N=2n \times 2n \times 2n=8n^{3}. To find the total number of favourable outcomes we proceed as follows:

Let a be any odd integer such that 1 \leq a \leq 2n-1 and let us count the sequences having a as least element.

(i) There is only one sequence (a,a,a) with a repeated thrice.

(ii) There are 2n-a sequences of the form (a,a,b) with a<b \leq 2n. For each such sequence there are three distinct permutations possible. Hence, there are in all 3(2n-a) sequences with a repeated twice.

iii) When n>1, for values of a satisfying 1 \leq a \leq (2n-3), sequences of the form (a,b,c,) with a<b<c \leq 2n are possible and the number of such sequences is r=1+2+3+\ldots+(2n+a-1)=\frac{1}{2}(2n-a)(2n-a-1). For each such sequence, there are six distinct permutations possible. Hence, there are 6r=3(2n-a)(2n-a-1) sequences in this case.

Hence, for odd values of a between 1 and 2n-1, the total counts of possibilities S_{1}, S_{2}, S_{3} in the above cases are respectively.

S_{1}=1+1+1+\ldots+1=n

S_{2}=3(1+3+5+\ldots+(2n-1))=3n^{2}

3(2 \times 3 + 4 \times 5 + \ldots+ (2n-2)(2n-1))=n(n-1)(4n+1).

Hence, the total number A of favourable outcomes is A=S_{1}+S_{2}+S_{3}=n+3n^{2}+n(n-1)(4n+1)=4n^{3}. Hence, the required probability is \frac{A}{N} = \frac{4n^{3}}{8n^{3}} = \frac{1}{2}. QED>

Cheers,

Nalin Pithwa

 

 

 

 

 

 

Miscellaneous questions: Part I: tutorial practice for preRMO and RMO

Problem 1:

The sixty four squares of a chess board are filled with positive integers one on each in such a way that each integer is the average of the of the integers on the neighbouring squares. (Two squares are neighbours if they share a common edge or vertex. Thus, a square can have 8,5 or 3 neighbours depending on its position). Show that all sixty four entries are in fact equal.

Problem 2:

Let T be the set of all triples (a,b,c) of integers such that 1 \leq a < b < c \leq 6. For each triple (a,b,c) in T, take the product abc. Add all these products corresponding to all triples in I. Prove that the sum is divisible by 7.

Problem 3:

In a class of 25 students, there are 17 cyclists, 13 swimmers, and 8 weight lifters and no one in all the three. In a certain mathematics examination, 6 students got grades D or E. If the cyclists, swimmers and weight lifters all got grade B or C, determine the number of students who got grade A. Also, find the number of cyclists, who are swimmers.

Problem 4:

Five men A, B, C, D, E are wearing caps of black or white colour without each knowing the colour of his cap. It is known that a man wearing a black cap always speaks the truth while a man wearing a white cap always lies. If they make the following statements, find the colour of the cap worn by each of them:

A: I see three black and one white cap.
B: I see four white caps.
C: I see one black and three white caps.
D: I see four black caps.

Problem 5:

Let f be a bijective (one-one and onto) function from the set A=\{ 1,2,3,\ldots,n\} to itself. Show that there is a positive integer M>1 such that f^{M}(i)=f(i) for each i \in A. Note that f^{M} denotes the composite function f \circ f \circ f \ldots \circ f repeated M times.

Problem 6:

Show that there exists a convex hexagon in the plane such that:
a) all its interior angles are equal
b) its sides are 1,2,3,4,5,6 in some order.

Problem 7:

There are ten objects with total weights 20, each of the weights being a positive integer. Given that none of the weights exceed 10, prove that the ten objects can be divided into two groups that balance each other when placed on the pans of a balance.

Problem 8:

In each of the eight corners of a cube, write +1 or -1 arbitrarily. Then, on each of the six faces of the cube write the product of the numbers written at the four corners of that face. Add all the fourteen numbers so writtein down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that this final sum is zero?

Problem 9:

Given the seven element set A = \{ a,b,c,d,e,f,g\} find a collection T of 3-element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.

Try these !!

Regards,
Nalin Pithwa

Towards Baby Analysis: Part I: INMO, IMO and CMI Entrance

\bf{Reference: \hspace{0.1in}Introductory \hspace{0.1in} Real Analysis: \hspace{0.1in} Kolmogorov \hspace{0.1in} and \hspace{0.1in} Fomin; \hspace{0.1in}Dover \hspace{0.1in }Publications}

\bf{Equivalence \hspace{0.1in} of \hspace{0.1in} Sets \hspace{0.1in} The \hspace{0.1in}Power \hspace{0.1in }of \hspace{0.1in }a \hspace{0.1in}Set}

\bf{Section 1}:

\bf{Finite \hspace{0.1in} and \hspace{0.1in} infinite \hspace{0.1in} sets}

The set of all vertices of a given polyhedron, the set of all prime numbers less than a given number, and the set of all residents of NYC (at a given time) have a certain property in common, namely, each set has a definite number of elements which can be found in principle, if not in practice. Accordingly, these sets are all said to be \it{finite}.\it{Clearly \hspace{0.1in} we \hspace{0.1in}can \hspace{0.1in} be \hspace{0.1in} sure \hspace{0.1in} that \hspace{0.1in} a \hspace{0.1in} set \hspace{0.1in}is \hspace{0.1in}finite \hspace{0.1in} without \hspace{0.1in} knowing \hspace{0.1in} the \hspace{0.1in} number \hspace{0.1in} of elements \hspace{0.1in}in \hspace{0.1in}it.}

On the other hand, the set of all positive integers, the set of all points on the line, the set of all circles in the plane, and the set of all polynomials with rational coefficients have a different property in common, namely, \it{if \hspace{0.1in } we \hspace{0.1in}remove \hspace{0.1in} one \hspace{0.1in} element \hspace{0.1in}from \hspace{0.1in}each \hspace{0.1in}set, \hspace{0.1in}then \hspace{0.1in}remove \hspace{0.1in}two \hspace{0.1in}elements, \hspace{0.1in}three \hspace{0.1in}elements, \hspace{0.1in}and \hspace{0.1in}so \hspace{0.1in}on, \hspace{0.1in}there \hspace{0.1in}will \hspace{0.1in}still \hspace{0.1in}be \hspace{0.1in}elements \hspace{0.1in}left \hspace{0.1in}in \hspace{0.1in}the \hspace{0.1in}set \hspace{0.1in}in \hspace{0.1in}each \hspace{0.1in}stage}. Accordingly, sets of these kind are called \it{infinite} sets.

Given two finite sets, we can always decide whether or not they have the same number of elements, and if not, we can always determine which set has more elements than the other. It is natural to ask whether the same is true of infinite sets. In other words, does it make sense to ask, for example, whether there are more circles in the plane than rational points on the line, or more functions defined in the interval [0,1] than lines in space? As will soon be apparent, questions of this kind can indeed be answered.

To compare two finite sets A and B, we can count the number of elements in each set and then compare the two numbers, but alternatively, we can try to establish a \it{one-\hspace{0.1in}to-\hspace{0.1in}one \hspace{0.1in}correspondence} between the elements of set A and set B, that is, a correspondence such that each element in A corresponds to one and only element in B, and vice-versa. It is clear that a one-to-one correspondence between two finite sets can be set up if and only if the two sets have the same number of elements. For example, to ascertain if or not the number of students in an assembly is the same as the number of seats in the auditorium, there is no need to count the number of students and the number of seats. We need merely observe whether or not there are empty seats or students with no place to sit down. If the students can all be seated with no empty seats left, that is, if there is a one-to-one correspondence between the set of students and the set of seats, then these two sets obviously have the same number of elements. The important point here is that the first method(counting elements) works only for finite sets, while the second method(setting up a one-to-one correspondence) works for infinite sets as well as for finite sets.

\bf{Section 2}:

\bf{Countable \hspace{0.1in} Sets}.

The simplest infinite set is the set \mathscr{Z^{+}} of all positive integers. An infinite set is called \bf{countable} if its elements can be put into one-to-one correspondence with those of \mathscr{Z^{+}}. In other words, a countable set is a set whose elements can be numbered a_{1}, a_{2}, a_{3}, \ldots a_{n}, \ldots. By an \bf{uncountable} set we mean, of course, an infinite set which is not countable.

We now give some examples of countable sets:

\bf{Example 1}:

The set \mathscr{Z} of all integers, positive, negative, or zero is countable. In fact, we can set up the following one-to-one correspondence between \mathscr{Z} and \mathscr{Z^{+}} of all positive integers: (0,1), (-1,2), (1,3), (-2,4), (2,5), and so on. More explicitly, we associate the non-negative integer $n \geq 0$ with the odd number 2n+1, and the negative integer n<0 with the even number 2|n|, that is,

n \leftrightarrow (2n+1), if n \geq 0, and n \in \mathscr{Z}
n \leftrightarrow 2|n|, if n<0, and n \in \mathscr{Z}

\bf{Example 2}:

The set of all positive even numbers is countable, as shown by the obvious correspondence n \leftrightarrow 2n.

\bf{Example 3}:

The set 2,4,8,\ldots 2^{n} is countable as shown by the obvious correspondence n \leftrightarrow 2^{n}.

\bf{Example 4}:    The set latex \mathscr{Q}$ of rational numbers is countable. To see this, we first note that every rational number \alpha can be written as a fraction \frac{p}{q}, with q>0 with a positive denominator. (Of course, p and q are integers). Call the sum |p|+q as the “height” of the rational number \alpha. For example,

\frac{0}{1}=0 is the only rational number of height zero,

\frac{-1}{1}, \frac{1}{1} are the only rational numbers of height 2,

\frac{-2}{1}, \frac{-1}{2}, \frac{1}{2}, \frac{2}{1} are the only rational numbers of height 3, and so on.

We can now arrange all rational numbers in order of increasing “height” (with the numerators increasing in each set of rational numbers of the same height). In other words, we first count the rational numbers of height 1, then those of height 2 (suitably arranged), then those of height 3(suitably arranged), and so on. In this way, we assign every rational number a unique positive integer, that is, we set up a one-to-one correspondence between the set Q of all rational numbers and the set \mathscr{Z^{+}} of all positive integers.

\it{Next \hspace{0.1in}we \hspace{0.1in} prove \hspace{0.1in}some \hspace{0.1in}elementary \hspace{0.1in}theorems \hspace{0.1in}involving \hspace{0.1in}countable \hspace{0.1in}sets}

\bf{Theorem1}.

\bf{Every \hspace{0.1in} subset \hspace{0.1in}of \hspace{0.1in}a \hspace{0.1in}countable \hspace{0.1in}set \hspace{0.1in}is \hspace{0.1in}countable}.

\bf{Proof}

Let set A be countable, with elements a_{1}, a_{2}, a_{3}, \ldots, and let set B be a subset of A. Among the elements a_{1}, a_{2}, a_{3}, \ldots, let a_{n_{1}}, a_{n_{2}}, a_{n_{3}}, \ldots be those in the set B. If the set of numbers n_{1}, n_{2}, n_{3}, \ldots has a largest number, then B is finite. Otherwise, B is countable (consider the one-to-one correspondence i \leftrightarrow a_{n_{i}}). \bf{QED.}

\bf{Theorem2}

\bf{The \hspace{0.1in}union \hspace{0.1in}of \hspace{0.1in}a \hspace{0.1in}finite \hspace{0.1in}or \hspace{0.1in}countable \hspace{0.1in}number \hspace{0.1in}of \hspace{0.1in}countable \hspace{0.1in}sets \hspace{0.1in}A_{1}, A_{2}, A_{3}, \ldots \hspace{0.1in}is \hspace{0.1in}itself \hspace{0.1in}countable.}

\bf{Proof}

We can assume that no two of the sets A_{1}, A_{2}, A_{3}, \ldots have any elements in common, since otherwise we could consider the sets A_{1}, A_{2}-A_{1}, A_{3}-(A_{1}\bigcup A_{2}), \ldots, instead, which are countable by Theorem 1, and have the same union as the original sets. Suppose we write the elements of A_{1}, A_{2}, A_{3}, \ldots in the form of an infinite table

\begin{array}{ccccc} a_{11} & a_{12} & a_{13} & a_{14} &\ldots \\ a_{21} &a_{22} & a_{23} & a_{24} & \ldots \\ a_{31} & a_{32} & a_{33} & a_{34} & \ldots \\ a_{41} & a_{42} & a_{43} & a_{44} & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots \end{array}

where the elements of the set A_{1} appear in the first row, the elements of the set A_{2} appear in the second row, and so on. We now count all the elements in the above array “diagonally”; that is, first we choose a_{11}, then a_{12}, then move downwards, diagonally to “left”, picking a_{21}, then move down vertically picking up a_{31}, then move across towards right picking up a_{22}, next pick up a_{13} and so on (a_{14}, a_{23}, a_{32}, a_{41})as per the pattern shown:

\begin{array}{cccccccc}   a_{11} & \rightarrow & a_{12} &\hspace{0.1in} & a_{13} & \rightarrow a_{14} & \ldots \\     \hspace{0.1in} & \swarrow & \hspace{0.1in} & \nearrow & \hspace{0.01in} & \swarrow & \hspace{0.1in} & \hspace{0.1in}\\     a_{21} & \hspace{0.1in} & a_{22} & \hspace{0.1in} & a_{23} \hspace{0.1in} & a_{24} & \ldots \\     \downarrow & \nearrow & \hspace{0.1in} & \swarrow & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in}\\     a_{31} & \hspace{0.1in} & a_{32} & \hspace{0.1in} & a_{33} & \hspace{0.1in} & a_{34} & \ldots \\     \hspace{0.1in} & \swarrow & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in} & \hspace{0.1in}\\    a_{41} & \hspace{0.1in} & a_{42} &\hspace{0.1in} & a_{43} &\hspace{0.1in} &a_{44} &\ldots\\     \ldots & \hspace{0.1in} & \ldots & \hspace{0.1in} & \ldots & \hspace{0.1in} & \ldots & \hspace{0.1in} \end{array}

It is clear that this procedure associates a unique number to each element in each of the sets A_{1}, A_{2}, \ldots thereby establishing a one-to-one correspondence between the union of the sets A_{1}, A_{2}, \ldots and the set \mathscr{Z^{+}} of all positive integers. \bf{QED.}

\bf{Theorem3}

\bf{Every \hspace{0.1in}infinite \hspace{0.1in}subset \hspace{0.1in}has \hspace{0.1in}a \hspace{0.1in}countable \hspace{0.1in}subset.}

\bf{Proof}

Let M be an infinite set and a_{1} any element of M. Being infinite, M contains an element a_{2} distinct from a_{1}, an element a_{3} distinct from both a_{2} and a_{1}, and so on. Continuing this process, (which can never terminate due to “shortage” of elements, since M is infinite), we get a countable subset A= \{ a_{1}, a_{2}, a_{3}, \ldots, a_{n}, \ldots\} of the set M. \bf{QED.}

\bf{Remark}

Theorem 3 shows that countable sets are the “smallest” infinite sets. The question of whether there exist uncountable (infinite) sets will be considered below.

\bf{Section3}

\bf{Equivalence \hspace{0.1in} of \hspace{0.1in} sets}

We arrived at the notion of a countable set M by considering one-to-one correspondences between set M and the set \mathscr{Z^{+}} of all positive integers. More generally, we can consider one-to-one correspondences between any two sets M and N.

\bf{Definition}

Two sets M and N are said to be \bf{equivalent} (written M \sim N) if there is a one-to-one correspondence between the elements of M and the elements of N.

The concept of equivalence is applicable both to finite and infinite sets. Two finite sets are equivalent if and only if they have the same number of elements. We can now define a countable set as a set equivalent to the set \mathscr{Z^{+}} of all positive integers. It is clear that two sets are equivalent to a third set are equivalent to each other, and in particular that any two countable sets are equivalent.

\bf{Example1}

The sets of points in any two closed intervals $[a,b]$ and $[c,d]$ are equivalent; you can “see’ a one-to-one correspondence by drawing the following diagram: Step 1: draw cd as a base of a triangle. Let the third vertex of the triangle be O. Draw a line segment “ab” above the base of the triangle; where “a” lies on one side of the triangle and “b” lies on the third side of the third triangle. Note that two points p and q correspond to each other if and only if they lie on the same ray emanating from the point O in which the extensions of the line segments ac and bd intersect.

\bf{Example2}

The set of all points z in the complex plane is equivalent to the set of all points z on a sphere. In fact, a one-to-one correspondence z \leftrightarrow \alpha can be established by using stereographic projection. The origin is the North Pole of the sphere.

\bf{Example3}

The set of all points x in the open unit interval (0,1) is equivalent to the set of all points y on the whole real line. For example, the formula y=\frac{1}{\pi}\arctan{x}+\frac{1}{2} establishes a one-to-one correspondence between these two sets. \bf{QED}.

The last example and the examples in Section 2 show that an infinite set is sometimes equivalent to one of its proper subsets. For example, there are “as many” positive integers as integers of arbitrary sign, there are “as many” points in the interval (0,1) as on the whole real line, and so on. This fact is characteristic of all infinite sets (and can be used to define such sets) as shown by:

\bf{Theorem4}

\bf{Every \hspace{0.1in} infinite \hspace{0.1in} set \hspace{0.1in}is \hspace{0.1in} equivalent \hspace{0.1in} to \hspace{0.1in}one \hspace{0.1in}of \hspace{0.1in}its \hspace{0.1in}proper \hspace{0.1in}subsets.}

\bf{Proof}

According to Theorem 3, every infinite set M contains a countable subset. Let this subset be A=\{a_{1}, a_{2}, a_{3}, \ldots, a_{n}, \ldots \} and partition A into two countable subsets A_{1}=\{a_{1}, a_{3}, a_{5}, \ldots \} and A_{2}=\{a_{2}, a_{4}, a_{6}, \ldots \}.

Obviously, we can establish a one-to-one correspondence between the countable subsets A and A_{1} (merely let a_{n} \leftrightarrow a_{2n-1}). This correspondence can be extended to a one-to-one correspondence between the sets A \bigcup (M-A)=M and A_{1} \bigcup (M-A)=M-A_{2} by simply assigning x itself to each element x \in M-A. But M-A_{2} is a proper subset of M. \bf{QED}.

More later, to be continued,

Regards,
Nalin Pithwa

A fifth degree equation in two variables: a clever solution

Question:

Verify the identity: (2xy+(x^{2}-2y^{2}))^{5}+(2xy-(x^{2}-2y^{2}))^{5}=(2xy+(x^{2}+2y^{2})i)^{5}+(2xy-(x^{2}+2y^{2})i)^{5}

let us observe first that each of the fifth degree expression is just a quadratic in two variables x and y. Let us say the above identity to be verified is:

P_{1}+P_{2}=P_{3}+P_{4}

Method I:

Use binomial expansion. It is a very longish tedious method.

Method II:

Factorize each of the quadratic expressions P_{1}, P_{2}, P_{3}, P_{4} using quadratic formula method (what is known in India as Sridhar Acharya’s method):

Now fill in the above details.

You will conclude very happily that :

The above identity is transformed to :

P_{1}=(x+y+\sqrt{3}y)^{5}(x+y-\sqrt{3}y)^{5}

P_{2}=(-1)^{5}(x-y-\sqrt{3}y)^{5}(x-y+\sqrt{3}y)^{5}

P_{3}=(i^{2}(x-y-\sqrt{3}y)(x-y+\sqrt{3}y))^{5}

P_{4}=((-i^{2})(x+y+\sqrt{3}y)(x-y-\sqrt{3}y))^{5}

You will find that P_{1}=P_{4} and P_{2}=P_{4}

Hence, it is verified that the given identity P_{1}+P_{2}=P_{3}+P_{4}. QED.

Regards,
Nalin Pithwa.

Set Theory, Relations, Functions: preliminaries: part 10: more tutorial problems for practice

Problem 1:

Prove that a function f is 1-1 iff f^{-1}(f(A))=A for all A \subset X. Given that f: X \longrightarrow Y.

Problem 2:

Prove that a function if is onto iff f(f^{-1}(C))=C for all C \subset Y. Given that f: X \longrightarrow Y.

Problem 3:

(a) How many functions are there from a non-empty set S into \phi\?

(b) How many functions are there from \phi into an arbitrary set S?

(c) Show that the notation \{ X_{i} \}_{i \in I} implicitly involves the notion of a function.

Problem 4:

Let f: X \longrightarrow Y be a function, let A \subset X, B \subset X, C \subset Y and D \subset Y. Prove that

i) f(A \bigcap B) \subset f(A) \bigcap f(B)

ii) f^{-1}(f(A)) \supset A

iii) f(f^{-1}(C)) \subset C

Problem 5:

Let I be a non-empty set and for each i \in I, let X_{i} be a set. Prove that

(a) for any set B, we have B \bigcap \bigcup_{i \in I}X_{i}=\bigcup_{i \in I}(B \bigcap X_{i})

(b) if each X_{i} is a subset of a given set S, then (\bigcup_{i \in I}X_{i})^{'}=\bigcap_{i \in I}(X_{i})^{'} where the prime indicates complement.

Problem 6:

Let A, B, C be subsets of a set S. Prove the following statements:

(i) A- (B-C)=(A-B)\bigcup(A \bigcap B \bigcap C)

(ii) (A-B) \times C=(A \times C)-(B \times C)

🙂 🙂 🙂

Nalin Pithwa

Set Theory, Relations, Functions: Preliminaries: Part IX: (tutorial problems)

Reference: Introductory Real Analysis, Kolmogorov and Fomin, Dover Publications.

Problem 1:

Prove that if A \bigcup B=A and A \bigcap B=A, then A=B.

Problem 2:

Show that in general (A-B)\bigcup B \neq A.

Problem 3:

Let A = \{ 2,4, \ldots, 2n, \ldots\} and B= \{ 3,6,\ldots, 3n, \ldots\}. Find A \bigcap B and A - B.

Problem 4:

Prove that (a) (A-B)\bigcap (C)=(A \bigcap C)-(B \bigcap C)

Prove that (b) A \Delta B = (A \bigcup B)-(A \bigcap B)

Problem 5:

Prove that \bigcup_{a}A_{\alpha}-\bigcup_{a}B_{\alpha}=\bigcup_{\alpha}(A_{\alpha}-B_{\alpha})

Problem 6:

Let A_{n} be the set of all positive integers divisible by n. Find the sets (i) \bigcup_{n=2}^{\infty}A_{n} (ii) \bigcap_{n=2}^{\infty}A_{n}.

Problem 7:

Find (i) \bigcup_{n=1}^{\infty}[n+\frac{1}{n}, n - \frac{1}{n}] (ii) \bigcap_{n=1}^{\infty}(a-\frac{1}{n},b+\frac{1}{n})

Problem 8:

Let A_{\alpha} be the set of points lying on the curve y=\frac{1}{x^{\alpha}} where (0<x<\infty). What is \bigcap_{\alpha \geq 1}A_{\alpha}?

Problem 9:

Let y=f(x) = <x> for all real x, where <x> is the fractional part of x. Prove that every closed interval of length 1 has the same image under f. What is the image? Is f one-to-one? What is the pre-image of the interval \frac{1}{4} \leq y \leq \frac{3}{4}? Partition the real line into classes of points with the same image.

Problem 10:

Given a set M, let \mathscr{R} be the set of all ordered pairs on the form (a,a) with a \in M, and let aRb if and only if (a,b) \in \mathscr{R}. Interpret the relation R.

Problem 11:

Give an example of a binary relation which is:

  • Reflexive and symmetric, but not transitive.
  • Reflexive, but neither symmetric nor transitive.
  • Symmetric, but neither reflexive nor transitive.
  • Transitive, but neither reflexive nor symmetric.

We will continue later, 🙂 🙂 🙂

PS: The above problem set, in my opinion, will be very useful to candidates appearing for the Chennai Mathematical Institute Entrance Exam also.

Nalin Pithwa

 

 

Set Theory, Relations, Functions: Preliminaries: part VIIIA

(We continue from part VII of the same blog article series with same reference text).

Theorem 4:

A set M can be partitioned into classes by a relation R (acting as a criterion for assigning two elements to the same class) if and only R is an equivalence relation on M.

Proof of Theorem 4:

Every partition of M determines a binary relation on M, where aRb means that “a belongs to the same class as b.” It is then obvious that R must be reflexive, symmetric and transitive, that is, R is an equivalence relation on M.

Conversely, let R be an equivalence relation on M, and let K_{a} be the set of all elements x \in M such that xRa (clearly, a \in K_{a}, since R is reflexive). Then, two classes K_{a} and K_{b} are either identical or disjoint. In fact, suppose that an element c belongs to both K_{a} and K_{b}, so that cRa and cRb. But by symmetry of R, being an equivalence relation, we can infer that aRc also and, further by transitivity, we say that aRb. If now, x \in K_{a} then we have xRa and hence, xRb (since we already have aRb and using transitivity).

Similarly, we can prove that x \in K_{b} implies that x \in K_{a}.

Therefore, K_{a}=K_{b} if K_{a} and K_{b} have an element in common. Therefore, the distinct sets K_{a} form a partition of M into classes.

QED.

Remark:

Because of theorem 4, one often talks about the decomposition of a set M into equivalence classes.

There is an intimate connection between mappings and partitions into classes, as illustrated by the following examples:

Example 1:

Let f be a mapping of a set A into a set B and partition A into sets, each consisting of all elements with the same image b=f(a) \in B. This gives a partition of A into classes. For example, suppose f projects the xy-plane onto the x-axis by mapping the point (x,y) into the point (x,0). Then, the preimages of the points of the x-axis are vertical lines, and the representation of the plane as the union of these lines is the decomposition into classes corresponding to f.

Example 2:

Given any partition of a set A into classes, let B be the set of these classes and associate each element a \in A with the class (that is, element of B) to which it belongs. This gives a mapping of A into B. For example, suppose we partition three-dimensional space into classes by assigning to the same class all points which are equidistant from the origin of coordinates. Then, every class is a sphere of a certain radius. The set of all these classes can be identified with the set of points on the half-line [0, \infty) each point corresponding to a possible value of the radius. In this sense, the decomposition of 3-dimensional space into concentric spheres corresponds to the mapping of space into the half-line [0,\infty).

Example 3:

Suppose that we assign all real numbers with the same fractional part to the same class. Then, the mapping corresponding to this partition has the effect of “winding” the real line onto a circle of unit circumference. (Note: The largest integer \leq x is called the integral part of x, denoted by [x], and the quantity x -[x] is called the fractional part of x).

In the next blog article, let us consider a tutorial problem set based on last two blogs of this series.

🙂 🙂 🙂

Nalin Pithwa