## Category Archives: Cnennai Math Institute Entrance Exam

### Set Theory Primer : Some basic thinking and problem solving

Reference: AMS, Student Mathematical Library: Basic Set Theory by A. Shen, et al. Chapter 1. Section 1.

Problem 1:

Consider the oldest mathematician amongst chess players and the oldest chess player amongst mathematicians. Could they be two different people?

Problem 2:

The same question for the best mathematician amongst chess players and the best chess player amongst mathematicians.

Problem 3:

One tenth of mathematicians are chess players, and one sixth of chess players are mathematicians. Which group (mathematicians or chess players) is bigger? What is the ratio of sizes of these two groups?

Problem 4:

Do there exist sets A, B and C such that $A \bigcap B \neq \phi$, $A \bigcap C = \phi$ and $(A\bigcap B)-C = \phi$ ?

Problem 5:

Which of the following formulas are true for arbitrary sets A, B and C:

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

ii) $(A \bigcup B) \bigcap C = (A \bigcap C) \bigcup (B \bigcap C)$

iii) $(A \bigcup B) - C = (A-C)\bigcup B$

iv) $(A \bigcap B) - C = (A - C) \bigcap B$

v) $A - (B \bigcup C) = (A-B) \bigcap (A-C)$

vi) $A - (B \bigcap C) = (A-B) \bigcup (A-C)$

Problem 6:

Give formal proofs of all valid formulas from the preceding problem. (Your proof should go like this : “We have to prove that the left hand side equals the right hand side. Let x be any element of the left hand side set. Then, ….Therefore, x belongs to the right hand side set. On the other hand, let…”)

Please give counterexamples to the formulas which are not true.

Problem 7:

Prove that the symmetric difference is associative:

$A \triangle (B \triangle C) = (A \triangle B) \triangle C$ for any sets A, B and C. Hint: Addition modulo two is associative.

Problem 8:

Prove that:

$(A_{1}\bigcap A_{2}\bigcap \ldots A_{n}) \triangle (B_{1} \bigcap B_{2} \bigcap \ldots B_{n}) = (A_{1} \triangle B_{1}) \bigcup (A_{2} \triangle B_{2}) \ldots (A_{n} \triangle B_{n})$ for arbitrary sets $A_{1}, A_{2}, \ldots, A_{n}, B_{1}, B_{2}, \ldots, B_{n}$.

Problem 9:

Consider an inequality whose left hand side and right hand side contain set variables and operations $\bigcap, \bigcup$ and -. Prove that if this equality is false for some sets, then it is false for some sets that contain at most one element.

Problem 10:

How many different expressions can be formed from set variables A and B by using union, intersection and set difference? (Variables and operations can be used more than once. Two expressions are considered identical if they assume the same value for each set of values of the variables involved.) Solve the same problem for three sets and for n sets. (Answer: In the general case, $2^{2^{n}-1}$)

Problem 11:

Solve the same problem if only $\bigcup$ and $\bigcap$ are allowed. For n=2 and n-3, this problem is easy to solve; however, no general formula for any n is known. This problem is also called “counting monotone Boolean functions in n variables”.)

Problem 12:

How many subsets does an n-element subset have?

Problem 13:

Assume that A consists of n elements and $B \subset A$ consists of k elements. Find the number of different sets C such that $B \subset C \subset A$.

Problem 14:

A set U contains 2n elements. We select k subsets of A in such a way that none of them is a subset of another one. What is the maximum possible value of k? (Hint: Maximal k is achieved when all subsets have n elements. Indeed, imagine the following process: We start with an empty set and add random elements one by one until we get U. At most one selected set can appear in this process. On the other hand, the expected number of selected sets that appear during this process can be computed using the linearity of expectation. Take into account that the probability to come across some set $Z \subset U$ is minimal when Z contains n elements, since all the sets of a given size are equiprobable.)

Regards,

Nalin Pithwa.

Purva building, 5A
Flat 06
Mumbai, Maharastra 400101
India.

### best explanation of epsilon delta definition

Refer any edition of (i) Calculus and Analytic Geometry by Thomas and Finney (ii) recent editions which go by the title “Thomas’ Calculus”. If you need, you will have to go through the previous stuff (given in the text) on “preliminaries” and/or functions also. For Sets, Functions and Relations, I have also presented a long series of articles on this blog.

Ref:

https://www.amazon.in/Thomas-Calculus-George-B/dp/9353060419/ref=sr_1_1?crid=3F1XO0L9KBT1F&keywords=thomas+calculus&qid=1581323971&s=books&sprefix=Thomas+%2Caps%2C265&sr=1-1

### Set theory, relations, functions: preliminaries: Part V

Types of functions: (please plot as many functions as possible from the list below; as suggested in an earlier blog, please use a TI graphing calculator or GeoGebra freeware graphing software):

1. Constant function: A function $f:\Re \longrightarrow \Re$ given by $f(x)=k$, where $k \in \Re$ is a constant. It is a horizontal line on the XY-plane.
2. Identity function: A function $f: \Re \longrightarrow \Re$ given by $f(x)=x$. It maps a real value x back to itself. It is a straight line passing through origin at an angle 45 degrees to the positive X axis.
3. One-one or injective function: If different inputs give rise to different outputs, the function is said to be injective or one-one. That is, if $f: A \longrightarrow B$, where set A is domain and set B is co-domain, if further, $x_{1}, x_{2} \in A$ such that $x_{1} \neq x_{2}$, then it follows that $f(x_{1}) \neq f(x_{2})$. Sometimes, to prove that a function is injective, we can prove the conrapositive statement of the definition also; that is, $y_{1}=y_{2}$ where $y_{1}, y_{2} \in codomain \hspace{0.1in} range$, then it follows that $x_{1}=x_{2}$. It might be easier to prove the contrapositive. It would be illuminating to construct your own pictorial examples of such a function.
4. Onto or surjective: If a function is given by $f: X \longrightarrow Y$ such that $f(X)=Y$, that is, the images of all the elements of the domain is full of set Y. In other words, in such a case, the range is equal to co-domain. it would be illuminating to construct your own pictorial examples of  such a function.
5. Bijective function or one-one onto correspondence: A function which is both one-one and onto is called a bijective function. (It is both injective and surjective). Only a bijective function will have a well-defined inverse function. Think why! This is the reason why inverse circular functions (that is, inverse trigonometric functions have their domains restricted to so-called principal values).
6. Polynomial function: A function of the form $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots + a_{n}x^{n}$, where n is zero or positive integer only and $a_{i} \in \Re$ is called a polynomial with real coefficients. Example. $f(x)=ax^{2}=bx+c$, where $a \neq 0$, $a, b, c \in \Re$ is called a quadratic function in x. (this is a general parabola).
7. Rational function: The function of the type $\frac{f(x)}{g(x)}$, where $g(x) \neq 0$, where $f(x)$ and $g(x)$ are polynomial functions of x, defined in a domain, is called a rational function. Such a function can have asymptotes, a term we define later. Example, $y=f(x)=\frac{1}{x}$, which is a hyperbola with asymptotes X and Y axes.
8. Absolute value function: Let $f: \Re \longrightarrow \Re$ be given by $f(x)=|x|=x$ when $x \geq 0$ and $f(x)=-x$, when $x<0$ for any $x \in \Re$. Note that $|x|=\sqrt{x^{2}}$ since the radical sign indicates positive root of a quantity by convention.
9. Signum function: Let $f: \Re \longrightarrow \Re$ where $f(x)=1$, when $x>0$ and $f(x)=0$ when $x=0$ and $f(x)=-1$ when $x<0$. Such a function is called the signum function. (If you can, discuss the continuity and differentiability of the signum function). Clearly, the domain of this function  is full $\Re$ whereas the range is $\{ -1,0,1\}$.
10. In part III of the blog series, we have already defined the floor function and the ceiling function. Further properties of these functions are summarized (and some with proofs in the following wikipedia links): (once again, if you can, discuss the continuity and differentiablity of the floor and ceiling functions): https://en.wikipedia.org/wiki/Floor_and_ceiling_functions
11. Exponential function: A function $f: \Re \longrightarrow \Re^{+}$ given by $f(x)=a^{x}$ where $a>0$ is called an exponential function. An exponential function is bijective and its inverse is the natural logarithmic function. (the logarithmic function is difficult to define, though; we will consider the details later). PS: Quiz: Which function has a faster growth rate — exponential or a power function ? Consider various parameters.
12. Logarithmic function: Let a be a positive real number with $a \neq 1$. If $a^{y}=x$, where $x \in \Re$, then y is called the logarithm of x with base a and we write it as $y=\ln{x}$. (By the way, the logarithmic function is used in the very much loved mp3 music :-))

Regards,

Nalin Pithwa

### You and your research ( You and your studies) : By Richard Hamming, AT and T, Bell Labs mathematician;

Although the title is grand (and quite aptly so)…the reality is that it can be applied to serious studies for IITJEE entrance, CMI entrance, highly competitive math olympiads, and also competitive coding contests…in fact, to various aspects of student life and various professional lifes…

https://www.cs.virginia.edu/~robins/YouAndYourResearch.html

### The animals went in which way

The animals may have gone into Noah’s Ark two by two, but in which order did they go in? Given the following sentence (yes, sentence! — I make no apologies for the punctuation), what was the order in which the animals entered the Ark?

The monkeys went in before the sheep, swans, chickens, peacocks, geese, penguins and spiders, but went in after the horses, badgers, squirrels and tigers, the latter of which went in before the horses, the penguins, the rabbits, the pigs, the donkeys, the snakes and the mice, but the mice went before the leopards, the leopards before the squirrels, the squirrels before the chickens, the chickens before the penguins, spiders, sheep, geese and the peacocks, the peacocks before the geese and the penguins, the penguins before the spiders and after the geese and the horses, the horses before the donkeys, the chickens and the leopards, the leopards after the foxes and the ducks, the ducks before the goats, swans, doves, foxes and badgers before the chickens, horses, squirrels and swans and after the lions, tigers, foxes, squirrels and ducks, the ducks after the lions, elephants, rabbits and otters, the otters before the elephants, tigers, chickens and beavers, the beavers after the elephants, the elephants before the lions, the lions before the tigers, the sheep before the peacocks, the swans before the chickens, the pigs before the snakes, the snakes before the foxes, the pigs after the rabbits, goats, tigers and doves, the doves before the chickens, horses, goats, donkeys and snakes, the snakes after the goats, and the donkeys before the mice and the squirrels.

🙂 🙂 🙂

Nalin Pithwa.

### Announcement: Scholarships for RMO Training

Mathematics Hothouse.

### Can anyone have fun with infinite series?

Below is list of finitely many puzzles on infinite series to keep you a bit busy !! 🙂 Note that these puzzles do have an academic flavour, especially concepts of convergence and divergence of an infinite series.

Puzzle 1: A grandmother’s vrat (fast) requires her to keep odd number of lamps of finite capacity lit in a temple at any time during 6pm to 6am the next morning. Each oil-filled lamp lasts 1 hour and it burns oil at a constant rate. She is not allowed to light any lamp after 6pm but she can light any number of lamps before 6pm and transfer oil from some to the others throughout the night while keeping odd number of lamps lit all the time. How many fully-filled oil lamps does she need to complete her vrat?

Puzzle 2: Two number theorists, bored in a chemistry lab, played a game with a large flask containing 2 liters of a colourful chemical solution and an ultra-accurate pipette. The game was that they would take turns to recall a prime number p such that $p+2$ is also a prime number. Then, the first number theorist would pipette out $\frac{1}{p}$ litres of chemical and the second $\frac{1}{(p+2)}$ litres. How many times do they have to play this game to empty the flask completely?

Puzzle 3: How farthest from the edge of a table can a deck of playing cards be stably overhung if the cards are stacked on top of one another? And, how many of them will be overhanging completely away from the edge of the table?

Puzzle 4: Imagine a tank that can be filled with infinite taps and can be emptied with infinite drains. The taps, turned on alone, can fill the empty tank to its full capacity in 1 hour, 3 hours, 5 hours, 7 hours and so on. Likewise, the drains opened alone, can drain a full tank in 2 hours, 4 hours, 6 hours, and so on. Assume that the taps and drains are sequentially arranged in the ascending order of their filling and emptying durations.

Now, starting with an empty tank, plumber A alternately turns on a tap for 1 hour and opens the drain for 1 hour, all operations done one at a time in a sequence. His sequence, by using $t_{i}$ for $i^{th}$ tap and $d_{j}$ for $j^{th}$ drain, can be written as follows: $\{ t_{1}, d_{1}, t_{2}, d_{2}, \ldots\}_{A}$.

When he finishes his operation, mathematically, after using all the infinite taps and drains, he notes that the tank is filled to a certain fraction, say, $n_{A}<1$.

Then, plumber B turns one tap on for 1 hour and then opens two drains for 1 hour each and repeats his sequence: $\{ (t_{1},d_{1},d_{2}), (t_{2},d_{3},d_{4}), (t_{3},d_{4},d_{5}) \ldots \}_{B}$.

At the end of his (B’s) operation, he finds that the tank is filled to a fraction that is exactly half of what plumber A had filled, that is, $0.5n_{A}$.

How is this possible even though both have turned on all taps for 1 hour and opened all drains for 1 hour, although in different sequences?

I hope u do have fun!!

-Nalin Pithwa.