Meaning of function or mapping or transformation in brief words

DEFINITION:

Given two sets X and Y, a transformation (also called a function or mapping) $f: X \rightarrow Y$ of X into Y is a triple $(X,Y,G)$ where G itself is a collection of ordered pairs $(x,y)$, the first element of each pair being an element of X, and the second an element of Y, with the condition that each element of X appears as the first element of exactly one pair of G.

If each element of Y appears as the second element of some pair in G, then the transformation is said to be onto.

If each element of Y which appears at all, appears as the second element of exactly one pair in G, then f is said to be one-to-one. Note that a transformation can be onto without being one-to-one and conversely.

As an aid in understanding the above definition, consider the equation $y=x^{2}$ where x is a real number. We may take X to be the set of all real numbers and then the collection G is the set of pairs of $(x,x^{2})$. Taking Y to be just the set of nonnegative reals will cause f to be onto. But if Y is all real numbers, or all reals greater than -7, or any other set containing the nonnegative reals as a proper subset, the transformation is not onto. With each new choice of Y, we change the triple and hence the transformation.

Continuing with the same example, we could assume that X is the set of nonnegative reals also. Then the transformation is one-to-one, as is easily seen. Depending upon the the choice of Y, the transformation may or may not be onto, of course. Thus, we see that we have stated explicitly the conditions usually left implicit in defining a function in analysis. The reader will find that the seemingly pedantic distinctions made here are really quite necessary.

If $f: X \rightarrow Y$ is a transformation of X into Y, and x is an element of the set X, then we let $f(x)$ denote the second element of the pair in G whose first element is x. That is, $f(x)$ is the “functional value” in Y of the point x. Similarly, if Z is a subset of X, then $f(Z)$ denotes that subset of Y composed of all points $f(z)$, where z is a point in Z. If y is a point of Y, then by $f^{-1}(y)$ is meant the set of all points in X for which $f(x)=y$; and if W is a subset of Y, then $f^{-1}(W)$ is the set theoretic union of the sets $f^{-1}(w)$, where w is in W. Note that $f^{-1}$ can be used as a symbol to denote the triple $(X,Y,G^{'})$ wjere $G^{'}$ consists of all pairs $(y,x)$ that are reversals of pairs in G. But $f^{-1}$ is a transformation only if f is both one-to-one and onto. If A is a subset of X and if $f: X \rightarrow Y$, then f may be restricted to A to yield a transformation denoted by $f|A: A \rightarrow Y$, and called the restriction of f to A.

Cheers,

Nalin Pithwa

Reference: Combinatorial Problems and Exercises, Second Edition, Laszlo Lovasz, AMS Chelsea Publishing, Indian Edition, available Amazon India.

There is no rule which says that enumeration problems even the simplest ones, must have solutions expressible as closed formulas/formulae. Some have, of course, and one important thing to be learnt here is how to recognize such problems. Another approach, avoiding the difficulty of trying to produce a closed formula, is to look for “substitute” solutions in other forms such as formulas involving summations, recurrence relations or generating functions. A typical (but not unique or universal) technique for solving an enumeration problem, in one or more parameters, is to find a recurrence relation, deduce a formula for the generating function (the recurrence relation is usually equivalent to a differential equation involving this function) and finally, where possible, to obtain the coefficients in the Taylor expansion of the generating function.

However, it should be pointed out that, in many cases, elementary transformations of the problems may lead to another problem already solved. For example, it may be possible by such transformations to represent each element to be counted as the result of a n consecutive decisions such that there are $a_{i}$ possible choices at the ith step. The answer would then be $a_{1}a_{2} \ldots a_{n}$. This is particularly useful when each decision is independent of all the previous decisions. Finding such a situation equivalent to the given problem is usually difficult and a matter of luck combined with expressions.

Cheers
Nalin Pithwa

In correct praise of Newtonian Mechanics : A P French

Reference: Newtonian Mechanics by A P French, M.I.T. Introductory Physics Series. (Available Amazon India).

Prologue:

One of the most important prominent features of the universe is motion. Galaxies have motions with respect to other galaxies, all stars have motions, the planets have distinctive motions against the background of the stars, the events that capture our attention most quickly in everyday life are those involving motion, and even the apparently inert book that you are now reading is made up of atoms in rapid motion about their equilibrium positions “Give me matter and motion” said the seventeenth century French philosopher Rene Descartes, “and I will construct the universe.” There can be no doubt that motion is a phenomenon we must learn to deal with at all levels if we are to understand the world around us.

Isaac Newton developed a precise and powerful theory regarding motion, according to which the changes of motion of any object are the result of forces acting on it. In so doing he created the subject with which this book is concerned and which is called classical or Newtonian mechanics. It was a landmark in the history of science, because it replaced a merely descriptive account of phenomena with a rational and marvelously successful scheme of cause and effect. Indeed, the strict causal nature of Newtonian mechanics had an impressive influence in the development of Western thought and civilization generally, provoking fundamental questions about the interrelationships of science, philosophy, and religion, with repercussions in social ideas and other areas of human endeavour.

Classical mechanics is a subject with a fascinating dual character. For it starts out from the kinds of everyday experiences that are as old as mankind, yet it brings us face to face with some of the most profound questions about the universe in which we find ourselves. Is it not remarkable that the flight of a thrown pebble, or the fall of an apple, should contain the clue to the mechanics of the heavens and should ultimately involve some of the most basic questions that we are able to formulate about the nature of space and time? Sometimes mechanics is presented as though it consisted merely of the routine application of self-evident or revealed truths. Nothing could be further from the case; it is a superb example of a physical theory, slowly evolved and refined through the continuing interplay between the observation and hypothesis.

The richness of our first hand acquaintance with mechanics is impressive, and through partnership of mind and eye and hand we solve, by direct action, innumerable dynamical problems without benefit of mathematical analysis. Like Moliere’s famous character, Monsieur Jourdain, who learned that he had been speaking prose all his life without realizing it, every human being is an expert in the consequences of the laws of mechanics, whether or not he has ever seen these laws written down. The skilled sportsman or athlete has an almost incredible degree of judgement and control of the amount and direction of muscular effort needed to achieve a desired result. It has been estimated, for example, that the World Series baseball championship would have changed hands in 1962 if one crucial swing at the ball had been a mere millimeter lower. But experiencing and controlling the motions of objects in this very personal sense is a far cry from analyzing them in terms of physical laws and equations. It is the task of classical mechanics to discover and formulate the essential principles, so that they can be applied to any situation, particularly to inanimate objects interacting with one another. Our intimate familiarity with our own muscular actions and their consequences, although it represents a kind of understanding (and an important kind, too) does not help us much here.

The greatest triumph of classical mechanics was Newton’s own success in analyzing the workings of the solar system — a feat immortalized in the famous couplet of his contemporary and admirer, the poet Alexander Pope:

Nature and Nature’s Laws lay hid in night

God said “Let Newton be” and “all was light.”

Men had observed the motions of the heavenly bodies since time immemorial. They had noticed various regularities and had learned to predict such things as conjunctions of the planets and eclipses of the sun and moon. Then, in the sixteenth century, the Danish astronomer Tycho Brahe amassed meticulous records, of unprecedented accuracy, of the planetary motions. His assistant, Johannes Kepler, after wrestling with this enormous body of information for years, found that all the observations could be summarized as follows:

1. The planets move in ellipses having the sun at one focus.
2. The line joining the sun to a given planet sweeps out equal areas in equal times.
3. The square of a planet’s year, divided by the cube of its mean distance from the sun, is the same for all planets.

This represented a magnificent advance in man’s knowledge of the mechanics of the heavens, but it was still a description rather than theory. Why? was the question that still looked for an answer. Then came Newton, with his concept of force as the cause of changes of motion, and with his postulate of a particular law of force — the inverse square law of gravitation. Using these he demonstrated how Kepler’s laws were just one consequence of a scheme of things that also included the falling apple and other terrestrial motions. (Later in this book, we shall go into the details of this great achievement of Newton’s).

If universal gravitation had done no more than to relate planetary periods and distances, it would still have been a splendid theory. But, like any other good theory in physics, it had predictive value; that is, it could be applied to situations besides the ones from which it was deduced. Investigating the predictions of a theory may involve looking for hitherto unsuspected phenomena, or it may involve recognizing that an already familiar phenomenon must fit into the new framework. In either case the theory is subjected to searching tests, by which it must stand or fall. With Newton’s theory of gravitation, the initial tests resided almost entirely in the analysis of known effects — but what a list !! Here are some of the phenomena for which Newton proceeded to give quantitative explanations:

1. The bulging of the earth and Jupiter because of their rotation.
2. The variation of the acceleration of gravity with latitude over the earth’s surface.
3. The generation of the tides by the combined action of sun and moon.
4. The paths of the comets through the solar system.
5. The slow steady change in direction of the earth’s axis of rotation produced by gravitational torques from the sun and moon. (A complete cycle of this variation takes about 25000 years, and the so-called “precession of the equinoxes” is a manifestation of it.)

This marvellous illumination of the workings of nature represented the last part of Newton’s program, as he described it in our opening quotation “…and then from these forces to demonstrate the other phenomena.” This modest phrase conceals not only the immensity of the achievement but also the magnitude of the role played by mathematics in this development. Newton had, in theory of universal gravitation, created what would be called today a mathematical model of the solar system. And having once made the model, he followed out a host of its other implications. The working out was purely mathematical, but the final step — the test of the conclusions — involved a return to the world of physical experience, in the detailed checking of his predictions against the quantitative data of astronomy.

Although Newton’s mechanical picture of the universe was simply confirmed in his own time, he did not live to see some of its greatest triumphs. Perhaps the most impressive of these was the use of his laws to identify previously unrecognized members of the solar system. By a painstaking and lengthy analysis of the motions of the known planets, it was inferred that disturbing influences due to other planets must be at work. Thus it was that Neptune was discovered in 1846, and Pluto in 1930. In each case it was a matter of deducing where a telescope should be pointed to reveal a new planet, identifiable through its changing position with respect to the general background of the stars. What more striking and convincing evidence could there be that the theory works?

Probably everyone who reads this book/blog article has some prior acquaintance with classical mechanics and with its expression in mathematically precise statements. And this may make it hard to realize that, as with any other physical theory, its development was not just a matter of mathematical logic applied undiscriminately to a mass of data. Was Newton inexorably driven to the inverse square law? By no means. It was the result of guesswork, intuition and imagination. In Newton’s own words: “I began to think of gravity extending to the orbit of the Moon, and …from Kepler’s Rule of the periodic times of the planets…I deduced that the forces which keep the planets in their orbits must be reciprocally as the squares of their distances from the centres about the which they revolve; and thereby compared the force requisite to keep the Moon in her orbit with the force of gravity at the surface of the Earth, and found them to answer pretty nearly.” An intellectual leap of this sort — although seldom as great as Newton’s — is involved in the creation of any theory or model. It is a process of induction, and it goes beyond the facts immediately at hand. Some facts may even be temporarily brushed aside or ignored in the interests of pursuing the main idea, for a partially correct theory is often better than no theory at all. And at all stages there is a constant interplay between experiment and theory, in the process of which fresh observations are continually suggesting themselves and modification of the theory is an ever-present possibility. The following diagram, the relevance of which goes beyond the realm of classical mechanics, suggests this pattern of man’s investigation of matter and motion:

1. Laws of motion —> 2) Laws of force —>3) Mathematical models —> 4) Predictions (process of deduction) —-> Observations and experiments —-> (1) Laws of motion (by induction)

The enormous success of classical mechanics made it seem, at one stage, that nothing more was needed to account for the whole world of physical phenomena. This belief reached a pinnacle towards the end of the nineteenth century, when some optimistic physicists felt that physics was, in principle, complete. They could hardly have chosen a more unfortunate time at which to form such a conclusion, for within the next few decades physics underwent its greatest upheaval since Newton. The discovery of radioactivity, of the electron and the nucleus, and the subtleties of electromagnetism, called for fundamentally new ideas. Thus, we know today that Newtonian mechanics, like every physical theory, has its fundamental limitations. The analysis of motions at extremely high speeds requires the use of modified descriptions of space and time, as spelled out by Albert Einstein’s special theory of relativity. In the analysis of phenomena on the atomic or subatomic scale, the still more drastic modifications described by quantum theory are required. And Newton’s particular version of gravitational theory, for all its success, has had to admit modifications embodied in Einstein’s general theory of relativity. But this does not alter the fact that in an enormous range and variety of situations, Newtonian mechanics provides us with the means to analyze and predict the motions of physical objects, from electrons to galaxies.

In developing the subject of classical mechanics in this book, we shall try to indicate how the horizons of its application to the physical world, and the horizons of one’s own view, can be gradually broadened. Mechanics, as we shall try to present it, is not at all a cut-and-dried subject that would justify its description as “applied mathematics,” in which the rules of the game are given at the outset and in which one’s only concern is with applying the rules to a variety of situations. We wish to offer a different approach, in which at every stage one can be conscious of working with partial or limited data and of making use of assumptions that cannot be rigorously justified. But this is the essence of doing physics. Newton himself said as much. At the beginning of the book III of the Principia he propounds four “Rules of Reasoning in Philosophy,” of which the last runs as follows:

“In experimental philosophy we are to look upon propositions inferred by general induction from phenomena as accurately or very nearly true, notwithstanding any contrary hypotheses that may be imagined, till such time as other phenomena occur, by which they may either be made more accurate, or liable to exceptions.” The person who waits for complete information is on the way to dooming himself never to finish an experiment or to construct a useful theory. Lest this should be taken, however, as an encouragement to slipshod or superficial thinking, we shall end this introduction with a little fable due to George Polya. He writes as a mathematician, but the moral for physicists (and others) is so clear:

The Logician, the Mathematician, the Physicist, and the Engineer

“Look at this mathematician,” said the logician. “He observes that the first 99 numbers are less than 100 an infers, hence, by what he calls induction, that all numbers are less than a hundred.” “A physicist believes,” said the mathematician, “that 60 is divisible by 1, 2, 3, 4, 5, and 6. He examines a few more cases such as 10, 20 and 30, taken at random (as he says). Since 60 is also divisible by these, he considers the experimental evidence sufficient.” “Yes, but look at the engineers,” said the physicist, “An engineer suspected that all odd are prime numbers. At any rate, 1 can be considered as a prime number, he argued. Then there comes 3, 5 and 7 all indubitably primes. Then there comes 9, an awkward case; it does not seem to be a prime number. Yes 11 and 13 are certainly primes. “Coming back to 9,” he said,” I conclude that 9 must be an experimental error.” But having done his teasing, Polya adds his remarks:

“It is only too obvious that induction can lead to error. Yet it is remarkable that induction sometimes leads to truth, since the chances of error seem so overwhelming. Should we begin with the study of obvious cases in which induction fails, or with the study of those remarkable cases in which induction succeeds? The study of precious stones is understandably more attractive than that of ordinary pebbles and, moreover, it was much more the precious stones than the pebbles that led the mineralogist to the wonderful science of crystallography.”

With that encouragement, we approach Classical Mechanics, which is one of the most perfect and polished gems in the physicist’s treasury.

Cheers, cheers, cheers,

Nalin Pithwa

Pre RMO Practice Sheet 2

Question 1:

A man walks a certain distance and rides back in 3.75 hours, he could ride both ways in 2.5 hours. How many hours would it take him to walk both ways?

Let the man walk distance x km in time t hours. His walking speed is $\frac{x}{t}$ kmph.

Let him ride distance x km in time T hours. His riding speed is $\frac{x}{T}$ kmph.

First journey: $\frac{x}{t} + \frac{x}{T} = 3.75$

Second journey: $\frac{2x}{T} = 2.5$

Hence, $\frac{x}{T} = 1.25$

Using above in first equation: $\frac{x}{t} + 1.25 = 3.75$

Hence, $\frac{x}{t} = 2.50$ = his speed of walking. Hence, it would take him 5 hours to walk both ways.

Question 2:

Positive integers a and b are such that $a+b=\frac{a}{b} + \frac{b}{a}$. What is the value of $a^{2}+b^{2}$?

Given that a and b are positive integers.

Given also $\frac{a}{b} + \frac{b}{a} = a+b$.

Hence, $a^{2}(b-1)+b^{2}(a-1)=0$

As a and b are both positive integers, so $a-1$ and $b-1$ both are non-negative.

So, both the terms are non-negative and hence, sum is zero if both are zero or $a=1$ and $b=1$.

Hence, $a^{2}+b^{2}=2$

Question 3:

The equations $x^{2}-4x+k=0$ and $x^{2}+kx-4=0$ where k is a real number, have exactly one common root. What is the value of k? $x^{2}-4x+k=0$…equation I $x^{2}+kx-4=0$…equation II

Let $k \in \Re$ and let $\alpha$ is a common root.

Hence, $\alpha$ satisfies both the equations. So, by plugging in the value of $\alpha$ we get the following: $\alpha^{2} -4\alpha + k =0$ and $x^{2}+kx-4=0$ and so using these two equations, we get the following: $(k+4)(1-\alpha)=0$.

Case 1: $\alpha \neq 1$ then $k=-4$. But hold on, we havent’t checked thoroughly if this is the real answer. We got to check now if both equations with these values of alpha and k have only one common root.

Equation I now goes as : $x^{2}-4x-4=0$ so this equation has irrational roots. On further examination, we see that if $\alpha=1$, then k can be any value. So, what are the conditions on k? We get that from equation I: plug in the value of alpha: $1-4+k=0$ so $k-3=0$ and $k=3$.

So, we now recheck if both equations have only one common root when alpha is 1 and k is 3: $x^{2}-4x+3=0$ so the roots of first equation are 3 and 1. $x^{2}+3x-4=0$ so the roots of second equation are -4 and 1.

Clearly so $k=3$ is the final answer. 🙂

Cheers,

Nalin Pithwa

Pre RMO practice sheet

Question 1:

What is the smallest positive integer k such that $k(3^{3}+4^{3}+5^{3})=a^{n}$ for some positive integers a and n with $n>1$?

Solution 1:

We have $k \times 216= a^{n}$ so that $k \times 6^{3} = a^{n}$ giving k=1.

Question 2:

Let $S_{n} = \sum_{k=0}^{n}\frac{1}{\sqrt{k+1}+\sqrt{k}}$.

What is the value of $\sum_{n=1}^{99} \frac{1}{S_{n}+S_{n-1}}$

Given $S_{n} = \sum_{k=0}^{n} \frac{1}{\sqrt{k+1}+\sqrt{k}} \times \frac{\sqrt{k+1}-\sqrt{k}}{\sqrt{k+1}-\sqrt{k}}$ $S_{n} = \sum_{k=0}^{n} (\sqrt{k+1}-\sqrt{k}) = \sqrt{n+1}$

Similarly, $S_{n-1} = \sum_{k=0}^{n-1}(\sqrt{k+1}-\sqrt{k}) = \sqrt{n}$

Now, $\sum_{n=1}^{99} \frac{1}{S_{n}+S_{n-1}} = \sum_{n=1}^{99}\frac{1}{\sqrt{n+1}-\sqrt{n}} \times \frac{\sqrt{n+1}-\sqrt{n}}{\sqrt{n+1}-\sqrt{n}}$

which in turn is equal to $\sum_{n=1}^{99} (\sqrt{n+1}-\sqrt{n}) = (\sqrt{2}-\sqrt{1})+(\sqrt{3}-\sqrt{2})+ (\sqrt{4}-\sqrt{3}+ \ldots + (\sqrt{100}-\sqrt{99})) = \sqrt{100} -\sqrt{1}=10-1=9$

Question 3: Homework:

It is given that the equation $x^{2}+ax+20=0$ has integer roots. What is the sum of all possible values of a?

Cheers,

Nalin Pithwa

A series question : pre RMO, RMO, IITJEE

Question 1:

Let $x_{1}, x_{2}, \ldots, x_{2014}$ be real numbers different from 1, such that $x_{1}+x_{2}+\ldots+x_{2014}=1$ and $\frac{x_{1}}{1-x_{1}} + \frac{x_{2}}{1-x_{2}} + \ldots + \frac{x_{2014}}{1-x_{2014}} = 1$ also.

Then, what is the value of $\frac{x_{1}^{2}}{1-x_{1}} + \frac{x_{2}^{2}}{1-x_{2}} + \frac{x_{3}^{2}}{1-x_{3}} + \ldots + \frac{x_{2014}^{2}}{1-x_{2014}}$ ?

Solution 1:

Note that $\sum \frac{x_{i}^{2}}{1-x_{i}} = \sum \frac{x_{i} + (x_{i} - x_{i}^{2})}{1-x_{i}} = \sum (\frac{x_{i}}{1-x_{i}} - x_{i}) = \sum \frac{x_{i}}{1-x_{i}} -\sum x_{i} = 1 - 1 = 0$ which is required answer.

Note that the maximum index 2014 plays no significant role here.

Question 2:

Let f be a one-to-one function from the set of natural numbers to itself such that $f(mn) = f(m)f(n)$ for all natural numbers m and n.

What is the least possible value of $f(999)$ ?

From elementary number theory, we know that given f is a multiplicative function and hence, the required function is such that if p and q are prime, then $f(pq)=f(p)f(q)$

That is we need to decompose 999 into its unique prime factorization.

So, we have $999 = 3 \times 333 = 3^{2} \times 111 = 3^{3} \times 97$ where both 3 and 97 are prime.

We have $f(999) = f(3)^{3} \times f(97)$ and we want this to be least positive integer. Clearly, then f(3) cannot be greater than 97. Also, moreover, we need both f(3) and f(97) to be as least natural number as possible. So, $f(3)=2$ and $f(97)=3$ so that required answer is 24.

Question 3:

HW :

What is the number of ordered pairs (A,B) where A and B are subsets of $\{ 1,2,3,4,5\}$ such that neither $A \subset B$ nor $B \subset A$ ?

Cheers,

Nalin Pithwa

Basic algebra facts of HCF and LCM

1. If x and y are two natural numbers, HCF(x,y) x LCM (x,y) = xy
2. If a, b, c are three natural numbers, then the product abc=HCF(a,b,c) x LCM(ab,bc,ca) and also abc=HCF(ab, bc,ca) x LCM(a,b,c).