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

Posted by Nalin Pithwa

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

Posted by Nalin Pithwa

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 !! :-)

Posted by Nalin Pithwa

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

Posted by Nalin Pithwa

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:

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

More later,

Nalin Pithwa.

Algebra question: RMO/INMO problem-solving practice

Posted by Nalin Pithwa

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,