You and your research or you and your studies for competitive math exams

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

Cyclic expressions, fractions: Pre RMO, PRMO, IITJEE foundation 2019

In order to solve the following tutorial sheet, it helps to solve/understand and then apply the following beautiful cyclic relations or identities:

(Note if these look new to you, then you need to check the truth of all them; if all are v v familiar to you, just go ahead and crack the tutorial sheet below):

Core Identities in Cyclic Expressions:
1) (b-c)+(c-a)+(a-b)=0
2) a(b-c)+b(c-a)+c(a-b)=0
3) a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)=-(a-b)(b-c)(c-a)
4) bc(b-c)+ca(c-a)+ab(a-b)=-(a-b)(b-c)(c-a)
5) a(b^{2}-c^{2})+b(c^{2}-a^{2})+c(a^{2}-b^{2})=(a-b)(b-c)(c-a)

Solve or simplify the following:

1) \frac{a}{(a-b)(a-c)} + \frac{b}{(b-c)(b-a)} + \frac{c}{(c-a)(c-b)}
2) \frac{bc}{(a-b)(a-c)} + \frac{ca}{(b-c)(b-a)} + \frac{ab}{(c-a)(c-b)}
3) \frac{a^{2}}{(a-b)(a-c)} + \frac{b^{2}}{(b-c)(b-a)} + \frac{c^{2}}{(c-a)(c-b)}
4) \frac{a^{3}}{(a-b)(a-c)} + \frac{b^{3}}{(b-c)(b-a)} + \frac{c^{3}}{(c-a)(c-b)}
5) \frac{a(b+c)}{(a-b)(c-a)} + \frac{b(a+c)}{(a-b)(b-c)} + \frac{a(a+b)}{(c-a)(b-c)}
6) \frac{1}{a(a-b)(a-c)} + \frac{1}{b(b-c)(b-a)} + \frac{1}{c(c-a)(c-b)}
7) \frac{bc}{a(a^{2}-b^{2})(a^{2}-c^{2})} + \frac{ca}{b(b^{2}-c^{2})(b^{2}-a^{2})} + \frac{ab}{c(c^{2}-a^{2})(c^{2}-b^{2})}
8) \frac{(x-b)(x-c)}{(a-b)(a-c)} + \frac{(x-c)(x-a)}{(b-c)(b-a)} + \frac{(x-a)(x-b)}{(c-a)(c-b)}
9) \frac{bc(a+d)}{(a-b)(a-c)} + \frac{ca(b+d)}{(b-c)(b-a)} + \frac{ab(c+d)}{(c-a)(c-b)}
10) \frac{1}{(a-b)(a-c)(x-a)} + \frac{1}{(b-c)(b-a)(x-b)} + \frac{1}{(c-a)(c-b)(x-c)}
11) \frac{a^{2}}{(a-b)(a-c)(x+a)} + \frac{b^{2}}{(b-c)(b-a)(x+b)} + \frac{c^{2}}{(c-a)(c-b)(x+c)}
12) a^{2}\frac{(a+b)(a+c)}{(a-b)(a-c)} + b^{2}\frac{(b+c)(b+a)}{(b-c)(b-a)} + c^{2}\frac{(c+a)(c+b)}{(c-a)(c-b)}
13) \frac{a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)}{(b-c)^{3}+(c-a)^{3}+(a-b)^{3}}
14) \frac{a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)+2(c-a)(a-b)(b-c)}{(b-c)^{3}+(c-a)^{3}+(a-b)^{3}}
15) \frac{a^{3}(b-c)+b^{3}(c-a)+c^{3}(a-b)}{a^{2}(b-c)+b^{2}(c-a)+c^{2}(a-b)}
16) \frac{a^{2}(b-c)^{3}+b^{2}(c-a)^{3}+c^{2}(a-b)^{3}}{(a-b)(b-c)(c-a)}
17) \frac{\frac{b-c}{a} + \frac{c-a}{b} + \frac{a-b}{c}}{\frac{1}{a}(\frac{1}{b^{2}}-\frac{1}{c^{2}})+\frac{1}{b}(\frac{1}{c^{2}}-\frac{1}{a^{2}})+\frac{1}{c}(\frac{1}{a^{2}}-\frac{1}{b^{2}})}^
18) \frac{a^{2}(\frac{1}{a^{2}}-\frac{1}{b^{2}})+b^{2}(\frac{1}{a^{2}}-\frac{1}{c^{2}})+c^{2}(\frac{1}{b^{2}}-\frac{1}{a^{2}})}{\frac{1}{bc}(\frac{1}{c}-\frac{1}{b})+\frac{1}{ca}(\frac{1}{a}-\frac{1}{c})+\frac{1}{ab}(\frac{1}{b}-\frac{1}{c})}
19) \frac{a}{(a-b)(a-c)(x-a)} + \frac{b}{(b-c)(b-a)(x-b)} + \frac{c}{(c-a)(c-b)(x-c)}

More later,
Nalin Pithwa

A Primer: Generating Functions: Part II: for RMO/INMO 2019

We shall now complicate the situation a little bit. Let us ask for the combinations of the symbols \alpha_{1}, \alpha_{2}, \ldots, \alpha_{n} with repetitions of each symbol allowed once more in the combinations. For example, let there be only two symbols \alpha_{1}, \alpha_{2}. Let us look for combinations of the form:

\alpha_{1}, \alpha_{2}, \alpha_{1}\alpha_{2}, \alpha_{1}\alpha_{1}, \alpha_{2}\alpha_{2}, \alpha_{1}\alpha_{1}\alpha_{2}, \alpha_{1}\alpha_{2}\alpha_{2}, \alpha_{1}\alpha_{1}\alpha_{2}\alpha_{2}

where, in each combination, each symbol may occur once, twice, or not at all. The OGF for this can be constructed by reasoning as follows: the choices for \alpha_{1} are not-\alpha_{1}, \alpha_{1} once, \alpha_{1} twice. This is represented by the factor (1+\alpha_{1}t+\alpha_{1}^{2}t^{2}). Similarly, the possible choices for \alpha_{2} correspond to the factor (1+\alpha_{2}t+\alpha_{2}^{2}t^{2}). So, the required OGF is (1+\alpha_{1}t+\alpha_{1}^{2}t)(1+\alpha_{2}t+\alpha_{2}^{2}t^{2})

On expansion, this gives : 1+(\alpha_{1}+\alpha_{2})t+(\alpha_{1}\alpha_{2}+\alpha_{1}^{2}+\alpha_{2}^{2})t^{2}+(\alpha_{1}^{2}\alpha_{2}+\alpha_{1}\alpha_{2}^{2})t^{3}+(\alpha_{1}^{2}\alpha_{2}^{2})t^{4}

Note that if we omit the term 1 (which corresponds to not choosing any \alpha), the other 8 terms correspond to the 8 different combinations listed in (*). Also, observe that the exponent r of the t^{r} tells us that the coefficient of t^{r} has the list or inventory of the r-combinations (under the required specification — in this case, with the restriction on repetitions of symbols) in it:

\bf{Illustration}

In the light of the foregoing discussion, let us now take up the following question again: in how many ways, can a total of 16 be obtained by rolling 4 dice once?; the contribution of each die to the total is either a “1” or a “2” or a “3” or a “4” or a “5” or a “6”. The contributions from each of the 4 dice have to be added to get the total — in this case, 16. So, if we write: t^{1}+t^{2}+t^{3}+t^{4}+t^{5}+t^{6}

as the factor corresponding to the first die, the factors corresponding to the other three dice are exactly the same. The product of these factors would be:

(*) (t+t^{2}+t^{3}+t^{4}+t^{5}+t^{6})^{4}

Each term in the expansion of this would be a power of t, and the exponent k of such a term t^{k} is nothing but the total of the four contributions which went into it. The number of times a term t^{k} can be obtained is exactly the number of times k can be obtained as a total on a throw of the four dice. So, if \alpha_{k} is the coefficient of t^{k} in the expansion, \alpha_{16} is the answer for the above question. Further, since (*) simplifies to (\frac{t(1-t^{6})}{1-t})^{4}, it follows that the answer for the above question tallies with the coefficient specified in the following next question: calculate the coefficient of t^{12} in (\frac{(1-t^{6})}{(1-t)})^{4}.6

Now, consider the following problem: Express the number N(n,p) of ways of obtaining a total of n by rolling p dice, as a certain coefficient in a suitable product of binomial expansions in powers of t. [ this in turn, is related to the observation that the number of ways a total of 16 can be obtained by rolling 4 dice once is the same as the coefficient of t^{12} in (\frac{1-t^{6}}{1-t})^{4}]:

So, we get that N(n,p)= coefficient of t^{n-p} in (\frac{1-t^{6}}{1-t})^{p}

Let us take an example from a graphical enumeration:

A \it {graph} G=G(V,F) is a set V of vertices a, b, c, …, together with a set E=V \times V of \it {edges} (a,b), (a,a), (b,a), (c,b), \ldots If (x,y) is considered the same as (y,x), we say the graph is \it{undirected}. Otherwise, the graph is said to be \it{directed}, and we say ‘(a,b) has a direction from a to b’. The edge (x,x) is called a loop. The graph is said to be of order |V|.

If the edge-set E is allowed to be a multiset, that is, if an edge (a,b) is allowed to occur more than once, (and, this may be called a ‘multiple edge’), we refer to the graph as a general graph.

If \phi_{5}(n) and \psi_{5}(n) denote the numbers of undirected (respectively, directed) loopless graphs of order 5, with n edges, none of them a multiple edge, find the series \sum \phi_{5}(n)t^{n} and \sum \psi_{5}(n)t^{n}.

Applying our recently developed techniques to the above question, a graph of 5 specified vertices is uniquely determined once you specify which pairs of vertices are ‘joined’. Suppose we are required to consider only graphs with 4 edges. This would need four pairs of vertices to be selected out of the total of 5 \choose 2 equal to 10 pairs that are available. So selection of pairs of vertices could be made in 10 \choose 4 ways. Each such selection corresponds to one unique graph, with the selected pairs being considered as edges. More informally, having selected a certain pairs of vertices, imagine that the vertices are represented by dots in a diagram and join the vertices of each selected pair by a running line. Then, the “graph” becomes a “visible” object. Note that the number of graphs is just the number of selections of pairs of vertices. Hence, \phi_{5}(4)=10 \choose 4.

Or, one could approach this problem in a different way. Imagine that you have a complete graph on 5 vertices — the “completeness” here means that every possible pair of vertices has been joined by an edge. From the complete graph which has 10 edges, one has to choose 4 edges — any four, for that matter — in order to get a graph as required by the problem.

On the same lines for a directed graph, one has a universe of 10 by 2, that is, 29 edges to choose from, for, each pair x,y gives rise to two possible edges (x,y) and (y,x). Hence,

\psi_{5}(4)=20 \choose 4.

Thus, the counting series for labelled graphs on 5 vertices is 1 + \sum_{p=1}^{10} {10 \choose p}t^{p}
and the counting series for directed labelled graphs on 5 vertices is
1+ \sum_{p=1}^{20}{20 \choose p}t^{p}.

Finally, the OGF for increasing words on an alphabet {a,b,c,d,e} with a<b<c<d<e is

(1+at+a^{2}t^{2}+\ldots)(1+bt+b^{2}t^{2}+\ldots)(1+ct+c^{2}t^{2}+\ldots)\times (1+dt+d^{2}t^{2}+\ldots)(1+et+e^{2}t^{2}+\ldots)

The corresponding OE is (1+t+t^{2}+t^{3}+\ldots)^{5} which is nothing but (1-t)^{-5} (this explains the following problem: Verify that the number of increasing words of length 10 out of the alphabet \{a,b,c,d,e \} with a<b<c<d<e is the coefficient of t^{10} in (1-t)^{-5} ).

We will continue this detailed discussion/exploration in the next article.

Until then aufwiedersehen,
Nalin Pithwa

Prof. Tim Gowers’ on recognising countable sets

https://gowers.wordpress.com/2008/07/30/recognising-countable-sets/

Thanks Dr. Gowers’. These are invaluable insights into basics. Thanks for giving so much of your time.

Functions — “s’wat” Math is about !! :-)

Reference: Nordic Mathematical Contest 1987, R. Todev:

Question:

Let f be a function, defined for natural numbers, that is strictly increasing, such that values of the function are also natural numbers and which satisfies the conditions f(2)=a>2 and f(mn)=f(m)f(n) for all natural numbers m and n. Define the smallest possible value of a.

Solution:

Since, f(n)=n^{2} is a function satisfying the conditions of the problem, the smallest possible a is at most 4. Assume that a=3. It is easy to prove by induction that f(n^{k})={f(n)}^{k} for all k \geq 1. So, taking into account that f is strictly increasing, we get

{f(3)}^{4}=f(3^{4})=f(81)>f(64)=f(2^{6})={f(2)}^{6}=3^{6}=27^{2}>25^{2}=5^{4}

as well as {f(3)}^{8}=f(3^{8})=f(6561)<f(8192)=f(2^{13})={f(2)}^{13}=3^{13}<6^{8}.

So, we arrive at 5<f(3)<6. But, this is not possible, since f(3) is an integer. So, a=4.

Cheers,

Nalin Pithwa.

Algebra : max and min: RMO/INMO problem solving practice

Question 1:

If x^{2}+y^{2}=c^{2}, find the least value of \frac{1}{x^{2}} + \frac{1}{y^{2}}.

Solution 1:

Let z^{'}=\frac{1}{x^{2}} + \frac{1}{y^{2}} = \frac{y^{2}+x^{2}}{x^{2}y^{2}} = \frac{c^{2}}{x^{2}y^{2}}

z^{'} will be minimum when \frac{x^{2}y^{2}}{c^{2}} will be minimum.

Now, let z=\frac{x^{2}y^{2}}{c^{2}}=\frac{1}{c^{2}}(x^{2})(y^{2})….call this equation I.

Hence, z will be maximum when x^{2}y^{2} is maximum but (x^{2})(y^{2}) is the product of two factors whose sum is x^{2}+y^{2}=c^{2}.

Hence, x^{2}y^{2} will be maximum when both these factors are equal, that is, when

\frac{x^{2}}{1}=\frac{y^{2}}{1}=\frac{x^{2}+y^{2}}{1}=\frac{c^{2}}{1}. From equation I, maximum value of z=\frac{c^{2}}{4}. Hence, the least value of \frac{1}{x^{2}} + \frac{1}{y^{2}}=\frac{4}{c^{2}}.

Some basics related to maximum and minimum:

Basic 1:

Let a and b be two positive quantities, S their sum and P their product; then, from the identity:

4ab=(a+b)^{2}-(a-b)^{2}, we have

4P=S^{2}-(a-b)^{2} and S^{2}=4P+(a-b)^{2}.

Hence, if S is given, P is greatest when a=b; and if P is given, S is least when a=b. That is, if the sum of two positive quantities is given, their product is greatest when they are equal; and, if the product of two positive quantities is given, their sum is least when they are equal.

Basic 2:

To find the greatest value of a product the sum of whose factors is constant.

Solution 2:

Let there be n factors a,b,c,\ldots, k, and suppose that their sum is constant and equal to s.

Consider the product abc\ldots k, and suppose that a and b are any two unequal factors. If we replace the two unequal factors a and b by the two equal factors \frac{a+b}{2}, \frac{a+b}{2}, the product is increased, while the sum remains unaltered; hence, so long as the product contains two unequal factors it can be increased without altering the sum of the factors; therefore, the product is greatest when all the factors are equal. In this case, the value of each of the n factors is \frac{s}{m}, and the greatest value of the product is (\frac{s}{n})^{n}, or (\frac{a+b+c+\ldots+k}{n})^{n}.

Corollary to Basic 2:

If a, b, c, \ldots k are unequal, (\frac{a+b+c+\ldots+k}{n})^{2}>abc\ldots k;

that is, \frac{a+b+c+\ldots +k}{n} > (\frac{a+b+c+\ldots + k}{n})^{\frac{1}{n}}.

By an extension of the meaning of the terms arithmetic mean and geometric mean, this result is usually stated as follows: the arithmetic mean of any number of positive quantities is greater than the geometric mean.

Basic 3:

To find the greatest value of a^{m}b^{n}c^{p}\ldots when a+b+c+\ldots is constant; m,n, p, ….being positive integers.

Solution to Basic 3:

Since m,n,p, …are constants, the expression a^{m}b^{n}c^{p}\ldots will be greatest when (\frac{a}{m})^{m}(\frac{b}{n})^{n}(\frac{c}{p})^{p}\ldots is greatest. But, this last expression is the product of m+n+p+\ldots factors whose sum is m(\frac{a}{m})+n(\frac{b}{n})+p(\frac{c}{p})+\ldots, or a+b+c+\ldots, and therefor constant. Hence, a^{m}b^{n}c^{p}\ldots will be greatest when the factors \frac{a}{m}, \frac{b}{n}, \frac{c}{p}, ldots are all equal, that is, when

\frac{a}{m} = \frac{b}{n} = \frac{c}{p} = \ldots = \frac{a+b+c+\ldots}{m+n+p+\ldots}

Thus, the greatest value is m^{m}n^{n}p^{p}\ldots (\frac{a+b+c+\ldots}{m+n+p+\ldots})^{m+n+p+\ldots}.

Some examples using the above techniques:

Example 1:

Show that (1^{r}+2^{r}+3^{r}+\ldots+n^{r})>n^{n}(n!)^{r} where r is any real number.

Solution 1:

Since \frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n}>(1^{r}.2^{r}.3^{r}\ldots n^{r})^{\frac{1}{n}}

Hence, (\frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n})^{n}>1^{r}.2^{r}.3^{r} \ldots n^{r}

that is, >(n!)^{r}, which is the desired result.

Example 2:

Find the greatest value of (a+x)^{3}(a-x)^{4} for any real value of x numerically less than a.

Solution 2:

The given expression is greatest when (\frac{a+x}{3})^{3}(\frac{a-x}{4})^{4} is greatest; but, the sum of the factors of this expression is 3(\frac{a+x}{3})+4(\frac{a-x}{4}), that is, 2a; hence, (a+x)^{3}(a-x)^{4} is greatest when \frac{a+x}{3}=\frac{a-x}{4}, that is, x=-\frac{a}{7}. Thus, the greatest value is \frac{6^{3}8^{4}}{7^{7}}a^{r}.

Some remarks/observations:

The determination of maximum and minimum values may often be more simply effected by the solution of a quadratic equation than by the foregoing methods. For example:

Question:

Divide an odd integer into two integral parts whose product is a maximum.

Answer:

Let an odd integer be represented as 2n+1; the two parts by x and 2n+1-x; and the product by y; then (2n+1)x-x^{2}=y; hence,

2x=(2n+1)\pm \sqrt{(2n+1)^{2}-4y}

but the quantity under the radical sign must be positive, and therefore y cannot be greater than \frac{1}{4}(2n+1)^{2}, or, n^{2}+n+\frac{1}{4}; and since y is integral its greatest value must be n^{2}+n; in which case x=n+1, or n; thus, the two parts are n and n+1.

Sometimes we may use the following method:

Find the minimum value of \frac{(a+x)(b+x)}{c+x}.

Solution:

Put c+x=y; then the expression =\frac{(a-c+y)(b-c+y)}{y}=\frac{(a-c)(b-c)}{y}+y+a-c+b-c

which in turn equals

(\frac{\sqrt{(a-c)(b-c)}}{\sqrt{y}}-\sqrt{y})^{2}+a-c+b-c+2\sqrt{(a-c)(b-c)}.

Hence, the expression is a a minimum when the square term is zero; that is when y=\sqrt{(a-c)(b-c)}.

Thus, the minimum value is a-c+b-c+2\sqrt{(a-c)(b-c)}, and the corresponding value of x is \sqrt{(a-c)(b-c)}-c.

Problems for Practice:

  1. Find the greatest value of x in order that 7x^{2}+11 may be greater than x^{3}+17x.
  2. Find the minimum value of x^{2}-12x+40, and the maximum value of 24x-8-9x^{2}.
  3. Show that (n!)^{2}>n^{n} and 2.4.6.\ldots 2n<(n+1)^{n}.
  4. Find the maximum value of (7-x)^{4}(2+x)^{5} when x lies between 7 and -2.
  5. Find the minimum value of \frac{(5+x)(2+x)}{1+x}.

More later,

Nalin Pithwa.

Algebra question: RMO/INMO problem-solving practice

Question:

If \alpha, \beta, \gamma be the roots of the cubic equation ax^{3}+3bx^{2}+3cx+d=0. Prove that the equation in y whose roots are \frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha} + \frac{\gamma\alpha-\beta^{2}}{\gamma+\\alpha-2\beta} + \frac{\alpha\beta-\gamma^{2}}{\alpha+\beta-2\gamma} is obtained by the transformation axy+b(x+y)+c=0. Hence, form the equation with above roots.

Solution:

Given that \alpha, \beta, \gamma are the roots of the equation:

ax^{3}+3bx^{2}+3cx+d=0…call this equation I.

By relationships between roots and co-efficients, (Viete’s relations), we get

\alpha+\beta+\gamma=-\frac{3b}{a} and \alpha\beta+\beta\gamma+\gamma\alpha=\frac{3c}{a}, and \alpha\beta\gamma=-\frac{d}{a}

Now, \gamma=\frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha}=\frac{\frac{\alpha\beta\gamma}{\alpha}-\alpha^{2}}{(\alpha+\beta+\gamma)-3\alpha}=\frac{-\frac{d}{a\alpha}-\alpha^{2}}{-\frac{3b}{a}-3\alpha}=\frac{d+a\alpha^{3}}{3\alpha(b+a\alpha)}, that is,

3xy(b+ax)=d+ax^{3}, or ax^{3}-3ayx^{2}-3byx+d=0…call this equation II.

Subtracting Equation II from Equation I, we get

3(b+ay)x^{2}+3(c+by)x=0

(b+ay)x+c+by=0 since x \neq 0

axy+b(x+y)+c=0 which is the required transformation.

Now, (ay+b)x=-(by+c), that is, x=-\frac{by+c}{ay+b}

Putting this value of x in Equation I, we get

-a(\frac{by+c}{ay+b})^{3}+3b(\frac{by+c}{ay+b})^{2}-3c(\frac{by+c}{ay+b})+d=0, that is,

a(by+c)^{3}-3b(by+c)^{2}(ay+b)+3c(by+c)(ay+b)^{2}-d(ay+b)^{3}=0, which is the required equation.

Cheers,

Nalin Pithwa.