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:

Solving equations | Tomato objective 20

This is a beautiful problem based on Solving Equations from Test of Mathematics Subjective Problem no. 20.

Problem : Solving equations

If $\ a,b,c,d$ satisfy the equations

$$a+7b+3c+5d=0,$$

$$8a+7b+6c+2d=-16,$$

$$2a+6b+4c+8d=16,$$

$$5a+3b+7c+d=-16,$$

then $\ (a+d)(b+c)$ equals

$\ (A)16 \quad (B)-16\quad (C)0 \quad$ (D)none of the foregoing numbers

Solution:

$$a+7b+3c+5d=0\dots(1),$$

$$8a+7b+6c+2d=-16\dots(2),$$

$$2a+6b+4c+8d=16\dots(3),$$

$$5a+3b+7c+d=-16\dots(4),$$

$\ (1)-(3)$, and $\ (2)-(4)$, we get

$$-a+b-c-3d=-16\dots(5),$$

$$3a+b-c+d=0\dots(6),$$

$\ (6)-(5)$, we get

$$a+d=4\dots(7),$$

$\ (2)+(3)$,we get

$$a+b+c+d=0\dots(8),$$

$\ (8)-(7)$,we get

$$b+c=-4\dots(9),$$

$\ (7)\times(9)$,we get

Therefore,$$(a+d)(b+c)=-16$$

Thus,$\ (B)$ is the correct option.

Some Useful Links:

A Cauchy Schwarz Problem

Cauchy Schwarz Problem: Let $P(x)$ be a polynomial with non-negative coefficients.Prove that if $P(x)\cdot P(\frac{1}{x})\ge1$ for $x=1$ ,then the same inequality holds for each $\mathbb{R^+} x$ .

Discussion: Cauchy Schwarz's Inequality: Suppose for real numbers (\ a_{i},b_{i}), where (\ i\in{1,2,\dots,n}) we can say that $${\sum_{i=1}^{n}a_{i}^2}{\sum_{i=1}^{n}b_{i}^2}=\sum_{i=1}^{n}{a_{i}b_{i}}^2$$.

Titu's Lemma: Let (\ a_{i},b_{i}\in{\mathbb{R}}) and let (\ a_{i},b_{i}>0) for (\ i\in{1,2,\dots,n})

$$\sum_{i=1}^{n}\frac{a_{i}^2}{b_{i}}\ge\frac{{\sum_{i=1}^{n}a_{i}}^2}{\sum_{i=1}^{n}b_{i}}$$

Proof of Cauchy Schwarz's Inequality: We can write (\sum_{i=1}{n}a_{i}^2=\sum_{i=1}^{n}\frac{a_{i}^2 b_{i}^2}{b_{i}^2}\ge\frac{{\sum_{i=1}^{n}a_{i}b_{i}}^2}{\sum_{i=1}^{n}b_{i}^2}) (using Titu's lemma)

(=>{\sum_{i=1}^{n}a_{i}^2}{\sum_{i=1}^{n}b_{i}^2}\ge {\sum_{i=1}^{n}{a_{i}b_{i}}^2)

Solution: Let $P(x)=a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ ,then $P(\frac{1}{x})=a_{n}\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+\dots+a_{1}\frac{1}{x}+a_{0}$

now $P(x)\cdot P(\frac{1}{x})=\{a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}\}\{a_{n}\frac{1}{x^n}+a_{n-1}\frac{1}{x^{n-1}}+\dots+a_{1}\frac{1}{x}+a_{0}\}=\{\{\sqrt{a_{n}x^n}\}^2+\{\sqrt{a_{n-1}x^{n-1}}\}^2+\dots+\{\sqrt{a_{1}x}\}^2+\{\sqrt{a_{0}}\}^2\} \{\{\sqrt{a_{n}\frac{1}{x^n}}\}^2+\{\sqrt{a_{n-1}\frac{1}{x^{n-1}}}\}^2+\dots+\{\sqrt{a_{1}\frac{1}{x}}\}^2+\{\sqrt{a_{0}}\}^2\} \ge\{a_{n}+a_{n-1}+\dots+a_{1}+a_{0}\}^2$
(Cauchy Schwarz's Inequality)

now it is given that $P(x)\cdot P(\frac{1}{x})\ge1$ for $x=1$ ,so $P(1)^2\ge 1=>\{a_{n}+a_{n-1}+\dots+a_{1}+a_{0}\}^2\ge1$

therefore, $P(x)\cdot P(\frac{1}{x})\ge1$ $\forall x\in{\mathbb{R^+}}$

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.

Abstract Algebra | Starters handbook for College Math

Hello, this is a discussion page for the college students who are in various prestigious colleges throughout India, and are keen to pursue Mathematics. Abstract Algebra plays a pivotal role in college mathematics, and it mainly focuses on three things
GROUPS, RINGS, and FIELDS.
Though Field is not in the course of some colleges, eventually it will be very helpful.
Now this discussion will be on some of the popular topics from Groups, Rings and Fields(to some extent).

AT A GLANCE WHAT IS IMPORTANT IN GROUPS
I am going to discuss chapterwise so in this post I give the first chapter of Group (Taking Herstein as reference)

Topics to study, and Problems that helps to build concepts (Chapter 2)

Definition of a group (Abelian, Cyclic imp) I.N. Herstein (Sec 2.3 prob 4,8,11 are imp for starters)

Hint of the problems
4) (Sol hint) Just take three consecutive integers like k, k+1, k+2 and try to change
[ab = a^kab/a^k], from where you will actually get [ba^k=a^kb]
Similarly try to find the same relation using k+2. you will get it.

8) (Sol hint) The group is finite this is your hint and use the closure property of the group. to give you a little more hint closure always doesn't happen like ab it is also a.a and a.a.a.a like this. Try to use that.

11) (Sol hint)
This problems tests you on the "uniqueness of the inverse", property of a group. Remember the group is of even order containing identity as an element. So without it there are odd no of elements in that group and all the elements has a unique inverse. So what now!! DO IT YOURSELF!!

SOME IMPORTANT THEOREMS IN THIS CHAPTER (I am taking Herstein as my reference Chap 2)

Uniqueness and existence of inverse and identity in a group (With proof). (Always watch the operation closely)
Very carefully understand the left and right multiplication. (One of the reasons why group theory become more absurd sometimes)

If you become comfortable then try problems like 14, 18, 19 (Chap 2)

14) (Sol hint) You are already given that your operation is product, the finite set you have abides associativity and closure property of a group.
Now use the cancellation property to establish the identity and inverse property.
First try using the fact that the group is finite then use the closure property to show the existence of identity. (Problem 8 will be helpful) From there using cancellation you can get the inverse property also.

18) (Sol Hint) Don't use the given hint, you now know something about groups and matrices too, so why not put the noncommutative criteria of matrices under multiplication in good use??

19) You now can solve it can't you?? Go on then. Good Luck.

As you are all starting as reference you can use books like:
1) Contemporary Abstract Algebra (J. Gallian Cengage)
2) Abstract Algebra (Dummit Foote)
3) Topics in Algebra (I.N. Herstein)
4)Higher Algebra by S.K.Mapa (This is a very basic book if you are not comfortable with the previous mentioned books then build your basic from this one)

A Common but deadly question in Group theory

Let's discuss a Common but deadly question in Group theory.

Question: Is it possible to get an infinite group which has elements of finite order?

Discussion To pursue this discussion which is basically a very good concept for the students who are new in group theory, they must know first about the QUOTIENT GROUPS.

Particularly for this problem I am going to take two very fundamental groups
1) (Q , +) (Rationals under addition)
2) (Z , +) (Integers under addition)
Now can you prove that (2) is a normal subgroup of (1). (Hint: Use the definition of normal subgroups)
So Q/Z under the binary operation will be a quotient group.

Now a little of topic discussion, if you know what will be the elements then you sure know the identity element of Q/Z. DON'T MAKE MISTAKE THAT '0' IS THE IDENTITY OF Q/Z. THE IDENTITY IS Z ITSELF AS THE ELEMENTS OF Q/Z ARE ALL IN FORM OF SETS.

For an example let p/q our usual rational number. Then the elements of Q/Z will be of the form (p/q) + Z
So as I have told you before that the identity is Z so for fun add (p/q) + Z two times
It gives (2p/q) + Z isn't so. Then what will happen if you add it q times? It will be p + Z. Now p is an integer itself. Then p + Z is Z itself. So you get an arbitrary element in Q/Z which has finite order q.(As q is the smallest integer to do so because gcd (p,q) is 1). Hope all of new comers in group theory will understand this.

This kind of question is very important for JAM, TIFR mainly.

Parity of the terms of a sequence | Tomato Problem 7

Try this problem from TOMATO Problem 7 based on the Parity of the terms of a sequence.

Problem: Parity of the terms of a sequence

If $ a_0 = 1 , a_1 = 1 $ and $ a_n = a_{n - 1} a_{n - 2} + 1 $ for $ n > 1 $, then:

(A) $a_{465} $ is odd and $a_{466} $ is even;
(B) $a_{465} $ is odd and $a_{466} $ is odd;
(C) $a_{465} $ is even and $a_{466} $ is even;
(A) $a_{465} $ is even and $a_{466} $ is odd;

Discussion:

First we note a pattern and then we prove that the pattern actually holds.

Note that:

$ a_0 = 1 $ is odd
$ a_1 = 1 $ is odd
$ a_2 = a_0 a_1 + 1 = 1\times 1 + 1 = 2 $ is even
$ a_3 = a_1 a_2 + 1 = 1 \times 2 + 1 = 3 $ is odd
$ a_4 = a_2 a_3 + 1 = 2 \times 3 + 1 = 7 $ is odd
$ a_5 = a_3 a_4 + 1 = 3 \times 7 + 1 = 22 $ is even

So the pattern that we observe is the following order: odd, odd, even, odd, odd, even...

We show this by strong form of induction. Suppose this pattern holds true for all n upto n = 3k+2

(that is $ a_{3k+2} = even , a_{3k+1} = odd, a_{3k}= odd $ ).

Our computations show that this is true for k =1 (so for initial value it is true).

Let us show for the next three values:

$ a_{3k+3} = a_{3k+2} \times a_{3k+1} + 1 = even \times odd + 1 = odd $
$ a_{3k+4} = a_{3k+3} \times a_{3k+2} + 1 = odd \times even + 1 = odd $
$ a_{3k+5} = a_{3k+4} \times a_{3k+3} + 1 = odd \times odd + 1 = even $

Thus we showed that whenever the index is of the form 3j+2, the number is even, otherwise if the index is of the form 3j or 3j+1, the term is odd.

Since 465 and 466 are respectively of the form 3j and 3j+1, hence
$ a_{465} $ and $ a_{466} $ both are odd.

Chatuspathi:

What is this topic: Induction
What are some of the associated concepts: Strong form of induction
Where can learn these topics: Cheenta I.S.I. & C.M.I. course, Math Olympiad Program discusses these topics in the ‘Induction’ module.
Book Suggestions: Elementary number theory by David Burton

Paper folding Geometry - Video