Test of Mathematics Solution Subjective 42- Polynomial with Integer Coefficients

This is a Test of Mathematics Solution of Subjective 42 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also Visit: I.S.I & CMI Entrance Course of Cheenta

Problem

Let f(x) be a polynomial with integer coefficients. Suppose that there exist distinct integers $ a_1 , a_2 , a_3 , a_4 $ , such that $ f( a_1 ) = f( a_2 ) = f( a_3 ) = f( a_4 ) = 3 $ . Show that there does not exist any integer b with f(b) = 14.

Solution:

Consider the auxiliary polynomial g(x) = f(x) - 3. Clearly, according to the problem, g(x) has four distinct integer roots $ a_1 , a_2 , a_3 , a_4 $. Hence we may write $ g(x) = (x - a_1)(x- a_2)(x- a_3)(x- a_4) Q(x)$ where Q(x) is an integer coefficient polynomial. (Since by factor theorem if 't' is a root of a polynomial f(x) then (x-t) is it's factor).

Suppose there exists an integer b such that f(b) = 14; then g(b) = 14-3 =11. Hence $ g(b) = 11 = (b- a_1 )(b- a_2 )(b- a_3 )(b- a_4 ) Q(b)$. $ a_1 , a_2 , a_3 , a_4 $ are distinct so are $ (b- a_1 ) , (b- a_2 ) , (b- a_3 ) , (b- a_4 ) $. Therefore the equation $ g(b) = 11 = (b- a_1 ) (b- a_2 )(b- a_3 )(b- a_4 ) Q(b)$ indicates that 11 can be written as the product of at least 4 different integers which is impossible (as 11 is a prime). Indeed even if we consider -1, 1 and 11 , we have only three integers whose product is 11.

Thus we have a contradiction and proving that there does not exist an integer b such that f(b) 14.

Key Idea: Factor Theorem

Test of Mathematics Solution Subjective 46 - Number of Onto Functions

This is a Test of Mathematics Solution Subjective 46 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem

A function $f$ from set $A$ into set $B$ is a rule which assigns each element $x$ in $A$, a unique (one and only one) element (denoted by $f(x)$ in $B$. A function of set from $A$ into $B$ is called an onto function, if for each element $y$ in $B$ there is some element $x$ in $A$, such that $f(x)=y$. Now suppose that $A =$ {$1,2,\cdots,n$} and $B=${$1,2,3$}. Determine the total number of onto functions of $A$ into $B$.

Sequential Hints

(How to use this discussion: Do not read the entire solution at one go. First, read more on the Key Idea, then give the problem a try. Next, look into Step 1 and give it another try and so on.)

Key Idea

This is the generic use case of Inclusion-Exclusion Principle. Read on this from Wikipedia

Step 1

1 may map to 1, 2, or 3 (3 choices). For each of these three choices, 2 may map to 1, 2, or 3 (again three choices. Hence 3 choices again. How many functions are possible in total? Can you delete the functions which are not onto from the total number of functions?

Try the problem with this hint before looking into step 2. Remember, no one learnt mathematics by looking at solutions.

The total number of functions is $ 3^n $ since there are 3 output choices for each of the n input choices. Now let us count the functions which are not onto.

How many functions are there such that $ 1 \in B $ has no preimage? (that is nothing is going to 1). There are $ 2^n $ such functions as each of the n elements of A has 2 choices. Similarly, count the cases where nothing goes to 2 ($2^n $ more cases) and nothing goes to 3 ($ 2^n $ more cases).

Delete these 'not onto' cases ( $ 3 \times 2^n $) from total number of cases ( $ 3^n $ ).

But we have double deleted the case where nothing goes to 1 'and' nothing goes to 2. This is the case where everything goes to 3. Only one such function is there: f(x) = 3.

Similarly, we have double deleted the case where nothing goes to 2 'and' nothing goes to 3. This is the case where everything goes to 1. Only one such function is there: f(x) = 1.

Similarly, we have double deleted the case where nothing goes to 1 'and' nothing goes to 3.

This is the case where everything goes to 2. Only one such function is there: f(x) = 2. Since we do not want to double delete something, we add back these three cases.

Thus the final answer is: $ 3^n - 3 \times 2^n + 3 $

Sum of polynomials | Tomato subjective 173

Try this beautiful problem from TOMATO Subjective Problem no. 173 based on the Sum of Polynomials.

Problem : Sum of polynomials

Let [latex] {{P_1},{P_2},...{P_n}}[/latex] be polynomials in [latex] {x}[/latex], each having all integer coefficients, such that [latex] {{P_1}={{P_1}^{2}+{P_2}^{2}+...+{P_n}^{2}}}[/latex]. Assume that [latex] {P_1}[/latex] is not the zero polynomial. Show that [latex] {{P_1}=1}[/latex] and [latex] {{P_2}={P_3}=...={P_n}=0}[/latex]

Solution :

As [latex] {P_1},{P_2},...{P_n}[/latex] are integer coefficient polynomials so gives integer values at integer points.

Now as [latex] {P_1}[/latex] is not zero polynomial

[latex] {\displaystyle{P_1}(x)>0}[/latex] for some [latex] \displaystyle{x \in Z}[/latex]

Then [latex] {\displaystyle{P_1}(x)\ge{1}}[/latex] or [latex] P_1(x) \le -1 [/latex] as [latex] {\displaystyle{P_1}(x)}[/latex]=integer

[latex] \Rightarrow (P_1(x))^2 \ge P_1(x)[/latex] or [latex] 0 \ge P_1(x) -(P_1(x))^2 [/latex]

But it is given that [latex] {{P_1}={{P_1}^{2}+{P_2}^{2}+...+{P_n}^{2}}}[/latex]

This implies [latex] (P_2 (x))^2+...+(P_n (x) )^2 \le 0 [/latex]. This is only possible if [latex] (P_1(x))^2 = ... = (P_n(x))^2 = 0[/latex]

Hence the values of x for which [latex] P_1 (x) [/latex] is non-zero, [latex] P_2(x) , ... , P_n(x) [/latex] are all zero. The values of x for which [latex] P_1(x) = 0 [/latex], we have [latex] 0=0+(P_2 (x))^{2}+...+(P_n(x))^2[/latex] implying each is zero.

Therefore [latex] P_2(x) = ... = P_n(x) = 0 [/latex].

Finally [latex] P_1(x) = (P_1(x))^2 [/latex] implies [latex] P_1(x) = 0 \text{or} P_1(x) = 1 [/latex]. Since [latex] P_1(x) \neq 0 [/latex] hence it is 1.

(Proved)

Chatushpathi

Topic: Theory of Equations
Central idea: Sum of square quantities zero implies each of the quantities is zero.
Course: I.S.I. & C.M.I. Entrance Program
Video: Primes and Polynomials

Round robin tournament | Tomato subjective 172

This problem is from the Test of Mathematics, TOMATO Subjective Problem no. 172 based on the Round Robin tournament.

Problem : Suppose there are [latex] {k}[/latex] teams playing a round robin tournament; that is, each team plays against all the other teams and no game ends in a draw.Suppose the [latex] {i^{th}}[/latex] team loses [latex] {l_{i}}[/latex] games and wins [latex] {w_{i}}[/latex] games. Show that

[latex] {{\displaystyle}{\sum_{i=1}^{k}{l_i^{2}}}}[/latex] = [latex] {{\displaystyle}{\sum_{i=1}^{k}{w_i^{2}}}}[/latex]

Solution : Each team plays exactly one match against each other team.

Consider the expression [latex] \displaystyle{\sum_{i=1}^{k} l_i^{2} - {w_i^2} = \sum_{i=1}^{k}(l_i + w_i)(l_i - w_i) } [/latex]

Since each team plays exactly k-1 matches and no match ends in a draw, hence number of wins plus numbers of loses of a particular team is k-1 (that is the number of matches it has played). In other words [latex] l_i + w_i = k-1 [/latex] for all i (from 1 to k).

Hence

[latex] \displaystyle{\sum_{i=1}^{k} l_i^{2} - {w_i^2} } [/latex]
[latex] \displaystyle{= \sum_{i=1}^{k}(l_i + w_i)(l_i - w_i) } [/latex]
[latex] \displaystyle{= \sum_{i=1}^{k}(k-1)(l_i - w_i) } [/latex]
[latex] \displaystyle{= (k-1)\left( \sum_{i=1}^{k} l_i - \sum_{i=1}^{k} w_i\right) } [/latex]

But [latex] \displaystyle{ \sum_{i=1}^{k} l_i = \sum_{i=1}^{k} w_i } [/latex] (as total number of loses = total number of matches = total number of wins; as each match results in a win or lose of some one)

Hence [latex] \displaystyle{= (k-1)\left( \sum_{i=1}^{k} l_i - \sum_{i=1}^{k} w_i\right) = (k-1) \times 0 = 0 } [/latex]

Therefore [latex] \displaystyle{\sum_{i=1}^{k} l_i^{2} - {w_i^2} = 0 } [/latex] implying [latex] {{\displaystyle}{\sum_{i=1}^{k}{l_i^{2}}}}[/latex] = [latex] {{\displaystyle}{\sum_{i=1}^{k}{w_i^{2}}}}[/latex]

Proved.

Test of Mathematics Solution Subjective 87 - Complex Roots of a Real Polynomial

This is a Test of Mathematics Solution Subjective 87 (from ISI Entrance). The book, Test of Mathematics at 10+2 Level is Published by East West Press. This problem book is indispensable for the preparation of I.S.I. B.Stat and B.Math Entrance.

Also visit: I.S.I. & C.M.I. Entrance Course of Cheenta

Problem:

Let $P(z) = az^2+ bz+c$, where $a,b,c$ are complex numbers.

$(a)$ If $P(z)$ is real for all real $z$, show that $a,b,c$ are real numbers.

$(b)$ In addition to $(a)$ above, assume that $P(z)$ is not real whenever $z$ is not real. Show that $a=0$.

Solution:

$(a)$ As $P(z)$ is real for all real $z$, we have $P(0)=c$ $=> c$ is real.

$P(1) = a+b+c$ is real.

$P(-1) = a-b+c$ is real.

$P(1) + P(-1) = 2a+2c$ is real.

As $c$ is real $=> a$ is also real.

Similarly as $(a+b+c)$ is real $=> (a+b+c)-(a+c)$ is also real.

Implying $b$ is also real.

Thus all $a,b,c$ are real.

$(b)$Let us assume that $a\neq 0$.

Thus the equation can be written as $P'(z)=z^2 + \frac{b}{a} z + \frac{c}{a} = 0$

Let $\alpha$ be a root of the equation. If $\alpha$ is imaginary that means $P'(\alpha)$ is imaginary. But $P'(\alpha)=0$, thus $\alpha$ is real. Similarly $\beta$, the other root of the equation, is also real.

Therefore $\alpha + \beta = -\frac{b}{a}$. $\cdots (i)$

Take $x=\frac{\alpha + \beta}{2} + i$

Then $P'(x) = \frac{(\alpha + \beta)^2}{4} + (\alpha + \beta)i -1 + \frac{b}{a}(\frac{\alpha + \beta}{2} + i) + \frac{c}{a}$

$=> P'(x) = \frac{(\alpha + \beta)^2}{4} + (\alpha + \beta)i -1 + \frac{b}{a} \frac{\alpha + \beta}{2} +\frac{b}{a} i + \frac{c}{a}$

Using $(i)$, we get,

$=> P'(x) = \frac{(\alpha + \beta)^2}{4} - \frac{b}{a} i -1 + \frac{b}{a} \frac{\alpha + \beta}{2} +\frac{b}{a} i + \frac{c}{a}$

$=> P'(x) = \frac{(\alpha + \beta)^2}{4} -1 + \frac{b}{a} \frac{\alpha + \beta}{2} + \frac{c}{a}$

Thus $P'(x)$ is real even when $x$ is imaginary. Thus our assumption that $ a \neq 0$ is wrong.

Hence Proved $a=0$.

Some Direct Inequalities | TOMATO Subjective 80

This is a beautiful problem based on Some Direct Inequalities from Test of Mathematics Subjective Problem no. 80.

Problem: Some Direct Inequalities

If $a,b,c$ are positive numbers, then show that

$\frac{b^2+c^2}{b+c}+\frac{c^2+a^2}{c+a}+\frac{a^2+b^2}{a+b}\geq a+b+c$

Solution: This problem can be solved using a direct application of the Titu's Lemma but we will instead prove the lemma first using the Cauchy-Schwarz inequality.

According to the Cauchy-Schwarz inequality we have,

$\left(a_1^2+a_2^2+\cdots+a_n^2\right)\left(b_1^2+b_2^2+\cdots+b_n^2\right)\ge \left(a_1b_1+a_2b_2+\cdots+a_nb_n\right)^2 $

Replacing $a_i\to \dfrac{a_i}{\sqrt{b_i}}$ and $b_i\to \sqrt{b_i}$ we get,

$\left(\dfrac{a_1^2}{b_1}+\dfrac{a_2^2}{b_2}+\cdots +\dfrac{a_n^2}{b_n}\right)\left(b_1+b_2+\cdots+b_n\right)\ge \left(a_1+a_2+\cdots+a_n\right)^2,$

which is equivalent to

$\dfrac{a_1^2}{b_1}+\dfrac{a_2^2}{b_2}+\cdots+\dfrac{a_n^2}{b_n}\geq \dfrac{\left(a_1+a_2+\cdots+a_n\right)^2}{b_1+b_2+\cdots+b_n}$

Now this inequality is referred to as the Titu's Lemma.

This brings us to the problem which can be observed to be a simple application of the lemma. We just need to make the following substitutions.

$a_1=b, a_2=c$ and $b_1=b_2=b+c$

Then we have,

$\dfrac{b^2}{b+c}+\dfrac{c^2}{b+c}\geq \dfrac{(b+c)^2}{2(b+c)}$

$=>\dfrac{b^2+c^2}{b+c}\geq \dfrac{b+c}{2}$

Thus similarly we have,

$=>\dfrac{c^2+a^2}{c+a}\geq \dfrac{c+a}{2}$ and $=>\dfrac{a^2+b^2}{a+b}\geq \dfrac{a+b}{2}$

Adding the three inequalities we get,

$=>\dfrac{b^2+c^2}{b+c}+\dfrac{c^2+a^2}{c+a}+\dfrac{a^2+b^2}{a+b}\geq \dfrac{b+c}{2}+\dfrac{c+a}{2}+\dfrac{a+b}{2}$

$=>\dfrac{b^2+c^2}{b+c}+\dfrac{c^2+a^2}{c+a}+\dfrac{a^2+b^2}{a+b}\geq \dfrac{2(a+b+c)}{2}$

$=>\dfrac{b^2+c^2}{b+c}+\dfrac{c^2+a^2}{c+a}+\dfrac{a^2+b^2}{a+b}\geq {a+b+c}$

Hence Proved.

Some Useful Links:

Irrational root | Tomato subjective Problem 28

PROBLEM: Given $f:$ and $g:$ are two quadratic polynomials with rational coefficients.
Suppose $f(x)=0$ and $g(x)=0$ have a common irrational solution.
Prove that $f(x)=rg(x)$ for all $x$ where $r$ is a rational number.

SOLUTION: Suppose the common irrational root of (\ f(x)) and (\ g(x)) be (\sqrt{a}+b).

Then by properties of irrational roots we can say that the other root of both of them will be (\sqrt{a}-b).

so we can write (\ f(x)=\lambda(x-\sqrt{a}-b)(x-\sqrt{a}+b)) and (\ g(x)=\mu(x-\sqrt{a}-b)(x-\sqrt{a}+b))

so (\frac{g(x)}{f(x)}=\frac{\mu}{\lambda})

therefore,$$\ g(x)=f(x)\frac{\mu}{\lambda}=rf(x)$$.

Theorem:In an equation with real coefficients irrational roots occurs in conjugate pairs.

Remembering Cauchy-Schwarz | Tomato subjective 33

Problem: Let ( \ k) be a fixed odd positive integer.Find the minimum value of ( \ x^2+y^2),where ( \ x,y) are non-negative integers and ( \ x+y=k).

Solution: According to Cauchy Schwarz's inequality,

we can write, ( \ (x^2+y^2)\times(1^2+1^2) \ge)(\ (x\times1+y\times1)^2)

=>( \ 2(x^2+y^2)\ge)(\ (x+y)^2)

=>( \ x^2+y^2\ge) (\frac{k^2}{2})

Therefore,the minimum value of ( \ x^2+y^2) is (\frac{k^2}{2}).

But it is given that (\ k) is a odd positive integer and (\ x,y \ge 0) so minimum value of ( \ x^2+y^2) must be (\frac{k^2+1}{2}).

Concepts used:-Cauchy Schwarz's inequality.

Sine Rule and Triangle | Tomato Subjective 120

Sine rule is an important rule relating to the sides and angles of any triangle. Here is a Subjective problem no. 120 from TOMATO. Try it.

Problem: Sine Rule and Triangle

(i) If $ A + B +C = n \pi $ and $ s=2 $, show that $ \sin 2A + \sin 2B + \sin 2C = (-1)^{n-1} 4 \sin A \sin B \sin C $and $ s=2 $
(ii) Let triangles ABC and DEF be inscribed in the same circle. If the triangles are of equal perimeter, then prove that $ \sin A + \sin B + \sin C = \sin D + \sin E + \sin F $ and $ s=2 $
(iii) State and prove the converse of (ii) above

Discussion:

(i) We know transformation formula from trigonometry $ \sin x + \sin y = 2 \sin \dfrac{x+y}{2} \cos \dfrac {x-y}{2} $ and $ s=2$

Hence $ \sin 2A + \sin 2B + \sin 2C = 2 \sin \dfrac{2A+2B}{2} \cos \dfrac {2A-2B}{2} + sin 2C = 2 \sin (A+B) \cos (A-B) + \sin 2C $ and $ s=2 $

Now we know that $ A + B = n \pi - C \Rightarrow \sin (A+B) = \sin (n \pi - C) = (-1)^{n-1} \sin C $ and $ s=2 $

So $ 2\sin (A+B) \cos (A-B) + \sin 2C = 2(-1)^{n-1} \sin C \cos (A-B) + 2 \sin C \cos C = 2(-1)^{n-1} \sin C \cos (A-B) + 2 \sin C \cos (n\pi -(A+B)) $ and $ s=2 $

$ = 2(-1)^{n-1} \sin C \cos (A-B) + 2 (-1)^n \sin C \cos (A+B) $ and $ s=2 $

$ = 2(-1)^{n-1} \sin C (\cos (A-B) - \cos (A+B)) $ and $ s=2 $

$ = 4(-1)^{n-1} \sin C \sin A \sin B $ and $ s=2 $

(ii)

Since the two triangles are inscribed in the same circle, they must have the same circumradius. Let the common circumradius be R. If a, b, c, d, e, f be the sides opposite to the sides BC, CA, AB, EF, DF, DE respectively, then using the rule of sines we can say,

$ \dfrac{\sin A}{a} = \dfrac { \sin B }{ b} = \dfrac {\sin C }{c} = \dfrac {1} {2R} $ and $ s=2 $ and

$ \dfrac{\sin D}{d} = \dfrac { \sin E }{ e} = \dfrac {\sin F }{f} = \dfrac {1} {2R} $ and $ s=2 $

Hence $ \sin A = \dfrac {a}{2R}, sin B = \dfrac{b}{2R}, \sin C = \dfrac {c}{2R} \Rightarrow \sin A + \sin B + \sin C = \dfrac {a+b+c}{2R} $ and $ s=2 $

Similarly $ \sin D + \sin E + \sin F = \dfrac {d + e + f}{2R} $ and $ s=2 $

As the perimeter of the triangle are equal, hence a+b+c = d+e+f. This implies $ \sin A + \sin B + \sin C = \sin D + \sin E + \sin F $ and $ s=2 $

(iii)

We apply the sine rule in reverse order to get the converse.

Chatuspathi:

What is this topic: Property of triangles
What are some of the associated concept: Rule of sines
Where can learn these topics: Cheenta I.S.I. & C.M.I. course, discusses these topics in the ‘Trigonometry Module’ module.
Book Suggestions: Trigonometry by S.L. Loney

Graphing integer value function | Tomato Subjective 117

This is a subjective problem from TOMATO based on Graphing integer value function.

Problem: Graphing integer value function

Let [x] denote the largest integer (positive, negative or zero) less than or equal to x. Let $ y= f(x) = [x] + \sqrt{x - [x]} $ and $ s=2 $ be defined for all real numbers x.

(i) Sketch on plain paper, the graph of the function f(x) in the range $ -5 \le x \le 5 $ and $ s=2$
(ii) Show that, any given real number $ y_0 $ and $ s=2 $, there is a real number $ x_0 4 $ and $ s=2 $ such that $ y_0 = f(x_0) $ and $ s=2 $

Discussion:

First note that $ \sqrt{x - [x]} $ and $ s=2 $ is same as $ \sqrt{t} , 0\le t \le 1 $ and $ s=2 $.

It's graph between 0 to 1 looks like:

Clearly [x] part only increments (or decrements) it by integer quantity as [x] is constant between any two integers. That for any integer k for all ( x in ($k, k+1$) ).
$ f(x) = k +\sqrt{t} $ and $ s=2 $ , $ t\in(0,1) $ and $ s=2 $. Hence graph of f(x) is as follows:

Finally consider and arbitrary value $ y_0 $ and $ s=2 $. We take $ x_0 = [y_0] + (y - [y_0])^2 $ and $ s=2$. Then $ f(x_0) = [x_0] + \sqrt(x - [x_0] = [y_0] + \sqrt{(y - [y_0])^2} = y_0 $ and $ s=2 $ (since $ 0 \le (y - [y_0]) < 1 \Rightarrow 0 \le (y - [y_0])^2 < 1 $ and $ s=2 $ )

Chatuspathi:

What is this topic: Graphing of functions
What are some of the associated concept: Greatest Integer Function
Where can learn these topics: Cheenta I.S.I. & C.M.I. course, discusses these topics in the ‘Calculus’ module.
Book Suggestions: Play with Graphs, Arihant Publication