# Science Lives: Laslo Lovasz: Discrete Maths, Combinatorics and Computer Science

Thanks to Simon Foundation : a youtube video.

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

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

Cheers,

Nalin Pithwa.

# RMO (Regional Mathematics Olympiad) — Plane Geometry Basics

Let us get started on plane geometry, some how or the other, now. Rather than starting with a lecture, let me start in a un-conventional format. A little challenging problem for you. Try to prove the following (Morley’s theorem):

In any arbitrary triangle, draw the trisectors of all the angles. Prove that the triangle formed by the points of intersection of adjacent trisectors (of different angles), taken in pair, is always equilateral.

Important Note: Please do not take look at any solution from the internet or any other source. You can use the basic theorems only presented in the Geometry toolkit, like as in, Problem Primer for the Olympiad, B J Venkatachala and/or in the lecture.

Have fun!

Nalin Pithwa.

# A cute number theory question for Math Olympiads and IITJEE Mathematics

Prove that the equation $x^{3}+y^{3}+z^{3}=2$ has an infinity of solutions in Z, the set of integers.

Proof:

Solution by Andrei Stefanescu

For any $k \in Z$ we will consider the numbers $x_{k}=1+6^{3k+1}$, $y_{k}=1-6^{3k+1}$ and $z_{k}=-6^{2k+1}$.

Note that the triplet $(x_{k},y_{},z_{k})$ is a solution of the equation, as $(1+6^{3k+1})^{3}+(1-6^{3k+1})^{3}+(-6^{2k+1})^{3}$ $= 1 + 3.6^{3k+1}+3.6^{6k+2}+6^{9k+3}+1-3.6^{6k+2}-6^{9k+3}-6^{6k+3}$ $= 2+ 6^{6k+3}-6^{6k+3}=2$.

Since we can define this triplet for all k’s, there will be an infinity of solutions.

QED.

More later,

Nalin Pithwa

# A geometry and algebra problem — RMO training

Several Olympiad problems deal with functions defined on certain sets of points. These problems are interesting in that they combine both geometrical and algebraic ideas.

Problem.

Let $n>2$ be an integer and $f:P \rightarrow \Re$ a function defined on the set of points in the plane, with the property that for any regular n-gon $A_{1}A_{2} \ldots A_{n}$ $f(A_{1})+f(A_{2})+ \ldots + f(A_{n})=0$.

Prove that f is the zero function.

Proof:

Core Concept:

In Euclidean geometry, the only motions permissible are rigid motions — translations, rotations, and reflections.

Solution:

Let A be an arbitrary point. Consider a regular n-gon $AA_{1}A_{2}\ldots A_{n-1}$. Let k be an integer, $0 \leq k \leq n-1$. A rotation with center A of angle $\frac{2\pi k }{n}$ sends the polygon $AA_{1}A_{2}\ldots A_{n-1}$ to $A_{k0}A_{k1} \ldots A_{k,n-1}$, where $A_{k0}=A$ and $A_{ki}$ is the image of $A_{i}$ for all $I=1, 2, \ldots, n-1$

From the condition of the statement, we have $\sum_{k=0}^{n-1} \sum_{i=0}^{n-1}f(A_{ki})=0$.

Observe that in the sum the number $f(A)$ appears n times, therefore, $nf(A)+ \sum_{k=0}^{n-1} \sum_{i=1}^{n-1}f(A_{kl})=0$

On the other hand, we have $\sum_{k=0}^{n-1} \sum_{i=1}^{n-1}f(A_{ki})=\sum_{i=1}^{n-1} \sum_{k=0}^{n-1}f(A_{ki})=0$

since the polygons $A_{0i}A_{1i} \ldots A_{n-1,i}$ are all regular n-gons. From the two equalities above we deduce $f(A)=0$, hence, f is the zero function.

More later,

Nalin Pithwa

(Russia 2001).

Let a and b be distinct positive integers such that $ab(a+b)$ is divisible by $a^{2}+ab+b^{2}$. Prove that $|a-b|> \sqrt{ab}$.

Proof.

Let $g=gcd(a,b)$ and write $a=xg$ and $b=yg$ with $gcd(x,y)=1$. Then, $\frac{ab(a+b)}{a^{2}+ab+b^{2}}=\frac{xy(x+y)g}{x^{2}+xy+y^{2}}$

is an integer. N^ote that $gcd(x^{2}+xy+y^{2}, x)=gcd(y^{2},x)=1$. Similarly, $gcd(x^{2}+xy+y^{2},y)=1$.

Because $gcd(x+y,y)=1$, we have $gcd(x^{2}+xy+y^{2},x+y)=gcd(y^{2}, x+y)=1$

Now, we apply the following lemma: Let a and b be two coprime numbers. If c is an integer such that $a|c$, then $ab|c$.

Hence, we get, $x^{2}+xy+y^{2}|g$ implying that $g \geq x^{2}+xy+y^{2}$. Therefore, $|a-b|^{3}=|g(x-y)|^{3}=g^{2}|x-y|^{3}.g \geq g^{2}.1.(x^{2}+xy+y^{2})>g^{2}xy=ab$.

It follows that $|a-b|>\sqrt{ab}$. QED.

Note that the key step $x^{2}+xy+y^{2}$ divides g can also be obtained by clever algebraic manipulations such as $a^{3}=(a^{2}+ab+b^{2})a-ab(a+b)$.

Nalin Pithwa

# Pigeon hole principle — an example for RMO preparation

Problem:

A student has 6 weeks (that is, 42 days) to prepare for her examination and she has decided that during this period she will put in a total of 70 hours towards her preparation for the examination. She decides to study in full hours every day, studying at least one hour each day. We have to prove that no matter how she schedules her studying pattern, she will study for exactly 13 hours during some consecutive days.

Solution:

If $a_{i}$ denotes the number of hours she studies on the ith day, then we are given that each $a_{i}$ is a positive integer and the sum $a_{1}+a_{2}+ \ldots + a_{42}=70$. To get the required succession of days, we must find some m and j such that $m \leq j$ and $a_{m}+ \ldots + a_{j}=13$. Trying out all the possibilities, is close to impossible as well as dumb. Let $b_{i}$ denote the partial sum $a_{1}+ \ldots + a_{i}$ which is the number of hours she studies upto the ith day. Our given data then translates into $1 \leq b_{1} < b_{2} < \ldots < b_{41} < b_{42}=70$

and we have to find some $i such that $b_{i}+13=b_{j}$, that is, $b_{j}-b_{i}=a_{i+1}+ \ldots + a_{j}=13$ (clearly, then $i. Hence, besides the 42 numbers in $B= \{ b_{1}, b_{2}, \ldots , b_{42}\}$ we also look at 42 more numbers in $B^{'}= \{ b_{1}+13, b_{2}+13, \ldots, b_{42}+13\}$ which are also 42 different numbers and the largest among them is $b_{42}+13=70+13=83$. Hence, the $2 \times 42$ are actually among the positive integers from 1 to 83 and hence, by the pigeonhole principle, we see that two numbers in $B \bigcup B^{'}$ must be equal. As we already saw the numbers in B are all distinct and so are the numbers in $B^{'}$. Hence, we must have for some i and j, $b_{i}=b_{j}+13$ giving the required succession of days when she studied exactly for 13 hours a day.

More on pigeonhole principle,

Later,

Till then,

Nalin Pithwa

# Training yourself for any Math Olympiad — RMO, INMO, IMO

Although you might have an expert coach or branded institution coaching you for the math or physics olympiads, the best thing is to be your own guru. What are the attitudes and/or regimen (of mind) needed to soar up your performance in Math or Physics Olympiads? I think the same applies for IIT JEE too, but perhaps, to a lesser degree. The following are some tips, which I like and I have compiled them from the net (especially American Math Olympiad websites) (especially, Prof. Kiran Kedlaya, MIT, Boston):

The term “olympiad” is used generically to refer to a math contest in which students are asked not to compute numerical answers, but to give proofs of specified statements. (Example: “Prove that 2003 is not the sum of two squares of integers.”) The most famous example is the International Mathematical Olympiad; most countries that participate at the IMO have national olympiads as part of their team selection process. Some areas have additional olympiads at the regional or local level.

The jump from short answers to olympiads is a tough one. Here are some tips for students making this transition.

• Practice, practice, practice. The only way to learn math is by doing.
• Proofs are essays. The better written a proof is, the more likely it is to be understood. Even such mundane things as grammar, spelling and handwriting are worth a bit of attention.
• Define your terms. If you’re going to use a word in a way that might not be commonly understood, define it precisely. Then stick to your definition!
• Read the masters. No one ever learned how to do good mathematics in a vacuum. When you do practice problems, read the solutions even of the problems you solved.
• There’s more than one road. Different solutions can be equally valid; even when solutions agree in substance, differences in perspective can be significant and valuable.
• It’s not over when it’s over. Don’t hesitate to continue thinking about the problems on a contest after the time ends, or to discuss the problems with others.
• Learn from your peers. They’re smarter than you might have expected.
• Learn from the past. Try to relate new problems to old ones; you may learn something from the similarities, or from the differences.
• Patience. No one said this was easy!

If you like this, please do send a thank you note to Prof. Kiran Kedlaya (kedlaya ‘at’ mathdotmitdotedu) :-))

More later,

Nalin Pithwa