# An algebra question for RMO or Pre-RMO

Question:

If a, b, c are non-negative real numbers such that $(1+a)(1+b)(1+c)=8$, then prove that the product abc cannot exceed 1.

Solution will be posted after you attempt it…so that you can compare the two approaches.

Nalin Pithwa.

# RMO Training: taking help from Nordic mathematical contest: 1988

Problem:

Let $m_{n}$ be a smallest value of the function $f_{n}(x)=\sum_{k=0}^{2n}x^{k}$. Prove that $m_{n} \rightarrow \frac{1}{2}$ when $n \rightarrow \infty$.

Proof:

For $n>1$,

$f_{n}(x)=1+x+x^{2}+\ldots=1+x(1+x+x^{2}+x^{4}+\ldots)+x^{2}(1+x^{2}+x^{4}+\ldots)=1+x(1+x)\sum_{k=0}^{n-1}x^{2k}$.

From this, we see that $f_{n}(x)\geq 1$ for $x \leq -1$ and $x\geq 0$. Consequently, $f_{n}$ attains its maximum value in the interval $(-1,0)$. On this interval

$f_{n}(x)=\frac{1-x^{2n+1}}{1-x}>\frac{1}{1-x}>\frac{1}{2}$

So, $m_{n} \geq \frac{1}{2}$. But,

$m_{n} \leq f_{n}(-1+\frac{1}{\sqrt{n}})=\frac{1}{2-\frac{1}{\sqrt{n}}}+\frac{(1-\frac{1}{\sqrt{n}})^{2n+1}}{2-\frac{1}{\sqrt{n}}}$

As $n \rightarrow \infty$, the first term on the right hand side tends to the limit $\frac{1}{2}$. In the second term, the factor

$(1-\frac{1}{\sqrt{n}})^{2n}=((1-\frac{1}{\sqrt{n}})^{\sqrt{n}})^{2\sqrt{n}}$

of the numerator tends to zero because

$\lim_{k \rightarrow \infty}(1-\frac{1}{k})^{k}=e^{-1}<1$.

So, $\lim_{n \rightarrow \infty}m_{n}=\frac{1}{2}$

auf wiedersehen,

Nalin Pithwa.

Reference: Nordic Mathematical Contest, 1987-2009.

# An easy inequality from Nordic mathematical contests !?

Reference: Nordic Mathematical Contest, 1987-2009, R. Todev.

Question:

Let a, b, and c be real numbers different from 0  and $a \geq b \geq c$. Prove that inequality

$\frac{a^{3}-c^{3}}{3} \geq abc(\frac{a-b}{c} + \frac{b-c}{a})$

holds. When does the equality hold?

Proof:

We know that a, b and c are real, distinct and also non-zero and also that $a \geq b \geq c$.

Hence, $c-b \leq 0 \leq a-b$, we have $(a-b)^{3}\geq (c-b)^{3}$, or

$a^{3}-3a^{a}b+3ab^{2}-b^{3} \geq c^{3}-3bc^{2}+3b^{2}c-b^{3}$

On simplifying this, we immediately have

$\frac{1}{3}{(a^{3}-c^{3})} \geq a^{2}b-ab^{2}+b^{2}c-bc^{2}=abc(\frac{a-b}{c}+\frac{b-c}{a})$.

A sufficient condition for equality is $a=c$. If $a>c$, then $(a-b)^{3}>(c-b)^{3}$. which makes the proved inequality a strict one. So, $a=c$ is a necessary condition for equality too.

-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.

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.

# Some elegant applications of the Pigeonhole Principle

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

In many interesting applications of the pigeonhole principle, the objects to be placed in boxes must be chosen in a clever way. A few such applications will be described here.

Example 1:

During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

Solution 1:

Let $a_{j}$ be the number of games played on or before the jth day of the month. Then, $a_{1}, a_{2}, \ldots, a_{30}$ is an increasing sequence of distinct positive integers, with $1 \leq a_{j} \leq 45$. Moreover, $a_{1}+14, a_{2}+14, \ldots, a_{30}+14$ is also an increasing sequence of distinct positive integers, with $15 \leq a_{j} + 14 \leq 59$.

The 60 positive integers $a_{1}, a_{2}, \ldots, a_{30}, a_{1}+14, \ldots, a_{30}+14$ are all less than or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the integers $a_{j}$, $j=1, 2, \ldots, 30$ are all distinct, there must be indices i and j with $a_{i}=a_{j}+14$. This means that exactly 14 games were played from day $j+1$ to i.

Example 2:

Show that among any $n+1$ positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution 2:

Write each of the $n+1$ integers $a_{1}, a_{2}, \ldots, a_{n+1}$ as a power of 2 times an odd integer. In other words, let $a_{j} = 2^{k_{j}}q_{j}$ for $j=1, 2, 3 \ldots n+1$, where $k_{j}$ is a nonnegative integer and $q_{j}$ is odd. The integers $q_{1}, q_{2}, \ldots, q_{n+1}$ are all odd positive integers less than 2n. Because there are only n odd positive integers less than $2n$, it follows from the pigeonhole principle that two of the integers $q_{1}, q_{2}, \ldots, q_{n+1}$ must be equal. Therefore, there are integers i and j such that $q_{i} = q_{j}$. Let q be the common value of $q_{i}$ and $q_{j}$. Then, $a_{i}=2^{k_{i}}q$ and $a_{j}=2^{k_{j}}q$. It follows that if $k_{i} then $a_{i}$ divides $a_{j}$. QED.

A clever application of the pigeonhole principle shows the existence of an increasing or a decreasing subsequence of a certain length in a sequence of distinct integers. Some definitions will be reviewed before this application is presented. Suppose that $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$ is a sequence of real numbers. A subsequence of this sequence is a sequence of the form $a_{1_{1}}, a_{i_{2}}, \ldots, a_{i_{n}}$, where $1 \leq i_{1} < i_{2} < ldots < i_{n} \leq N$. Hence, a subsequence is a sequence obtained from the original sequence by including some of the original sequence in their original order, and perhaps, not including other terms. A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that precedes it.

Theorem:

Every sequence of $n^{2}+1$ distinct real numbers contains a subsequence of length $n+1$ that is either strictly increasing or strictly decreasing.

An example is presented below (before the proof) of the above:

Example:

The sequence $8, 11, 9, 1, 4, 6, 12, 10, 5, 7$ contains 10 terms. Note that $10=3^{2}+1$. There are four increasing subsequence of length four, namely, $1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; 1, 4, 5, 7$. There is also a decreasing subsequence of length four, namely, $11, 9, 6, 5$.

The proof of the theorem is presented below:

Let $a_{1}, a_{2}, \ldots, a_{n^{2}}+1$ be a sequence of $n^{2}+1$ distinct real numbers. Associate an ordered pair with each term of the sequence, namely, associate $(a_{k},d_{k})$ to the term $a_{k}$, where $i_{k}$ is the length of the longest increasing subsequence starting at $a_{k}$, and $d_{k}$ is the length of the longest decreasing subsequence starting at $a_{k}$.

Suppose that there are no increasing or decreasing subsequences of length $n+1$. Then, $i_{k}$ and $d_{k}$ are both positive integers less than or equal to n, for $k=1, 2, \ldots, n^{2}+1$. Hence, by the product rule there are $n^{2}$ possible ordered pairs for $(i_{k},d_{k})$. By the pigeonhole principle, two of these $n^{2}+1$ ordered pairs are equal. In other words, there exist terms $a_{s}$ and $a_{t}$, with $s such that $i_{s}=i_{t}$ and $d_{s}=d_{t}$. We will show that this  is impossible. Because the terms of the sequence are distinct, either $a_{s}>a_{t}$ or $a_{s}. If $a_{s}, then, because $i_{s}=i_{t}$, an increasing subsequence of length $i_{t}+1$, can be built starting at $a_{s}$, by taking $a_{s}$ followed by an increasing subsequence of length $i_{t}$ beginning at $a_{t}$. This is a contradiction. Similarly, if $a_{s}>a_{t}$, the same reasoning shows that $d_{s}$ must be greater than $d_{t}$, which is a contradiction. QED.

Quiz based on generalized pigeonhole principle:

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Note: This little quiz is a motivation for Ramsey theory. This theory deals with the distribution of of subsets of elements of sets.

More later,

Nalin Pithwa