Elementary problems in Ramsey number theory for RMO

Question 1:

Show that in any group of 6 people there will always be a subgroup of 3 people who are pairwise acquainted or a subgroup of 3 people who are pairwise strangers.

Solution 1:

Let \{ A, B, C, D, E, F\} be a group of 6 people. Suppose that the people known to A are seated in room Y and the people NOT known to A are seated in room Z; A is not in either room. Then, there are necessarily at least 3 people in either room Y or in room Z; (a) Suppose B, C, D to be in room Y. Either these 3 people are mutual strangers (and so the given theorem is true), or, at least two of them (say, B and C) know each other. In the latter case, A, B and C form a group of 3 mutual acquaintances — and again, the theorem is true. (b) In (a), replace room Y by Z and interchange the notion of ‘”acquaintances” and “strangers”‘.

Question 2:

Show that in any group of 10 people there is always (a) a subgroup of 3 mutual strangers or a subgroup of 4 mutual acquaintances, and (b) a subgroup of 3 mutual acquaintances or a subgroup of 4 mutual strangers.

Solution 2:

(a) Let A be one of the ten people; the remaining 9 people can be assigned to two rooms: those who are known to A are in room Y and those who are not known to A are in room Z. Either room Y has at least 6 people or room Z has at least 6 people. For, (i) suppose room Y has at least 6 people. Then, by previous problem number 1, there is either a subgroup of 3 mutual acquaintances or a subgroup of 3 mutual strangers (thus, the theorem is true) in this room. In the former case, A and these 3 people constitute 4 mutual acquaintances (ii) Suppose room Z has at least 4 people. Either these 4 people know one another or at least 2 of them, say B and C, do not know each other. In the former case, we have a subgroup of 4 mutual acquaintances. In the latter case A, B and C constitute 3 mutual strangers.

(b) In the previous scenario, let people who are strangers become acquaintances, and let people who are acquaintances pretend they are strangers. The situation is symmetric.

Question 3:

Show that in any subgroup of 20 people there will always be either a subgroup of 4 mutual acquaintances or a subgroup of 4 mutual strangers.

Solution 3:

Suppose A is one of these 20 people. People known to A are in room Y and people not known to A are room Z. Either room Y has at least 10 people or room Z has at least 10 people. (i) If Y has at least 10 people, then by part B of problem number 2 here, there is either a subgroup of 3 mutual acquaintances or a subgroup of 4 mutual strangers — as asserted — in this room. In the former case, A and these mutual acquaintances will form a subgroup of 4 mutual acquaintances. (ii) Switch ‘”acquaintances” and “strangers”‘ in (i).

Question 4:

Let p and q be 2 positive integers. A positive integer r is said to have the (p,q) – Ramsey property, if in any group of r people either there is a subgroup of p people known to one another or there is a subgroup of q people not known to one another. {By Ramsey’s theorem, all sufficiently large integers r have the (p,q)-Ramsey property.} The smallest r with the (p,q)-Ramsey property is called the Ramsey number R(p,q). Show that (a) R(p,q) = R (q,p). (b) R(p,1)=1, and (c) R(p,2)=p.

Solution 4:

(a) By parts (b) of the previous three questions, we have proved part a of the proof here.

(b) This is obvious.

(c) In any group of p people, if all of them are not known to one another, there will be at least 2 people who do not know each other.

Question 5:

Prove that R(3,3)=6.

Solution 5:

Question 1 and its proof in this blog article imply that R(3,3) \leq 6.

To prove that R(3,3)>5, it is sufficient to consider a seating arrangement of 5 people about a round table in which each person knows only the 2 people on either side. In such a situation, there is no set of 3 mutual acquaintances and no set of 3 people not known to one another.

Question 6:

Show that if m and n are integers both greater than 2, then

R(m,n) \leq R(m-1,n) + R(m,n-1).

(this recursive inequality gives a non-sharp upper bound for R(m,n)).

Solution 6:

Let p \equiv R(m-1,n), q=R(m,n-1) and r \equiv p + q. Consider a group \{ 1,2, 3, \ldots, r\} of r people. Let L be the set of people known to person 1 and M be the set of people NOT known to person 1. The two sets together have r-1 people, so either L has at least p people or M has at least q people. (a) If L has p \equiv R(m-1,n) people, then, by definition, it contains a subset of (m-1) people known to one another or it contains a subset of n people unknown to one another. In the former case, the (m-1) people and person 1 constitute m people known to one another.

Thus, in their case, a group of R(m-1,n) + R(m,n-1) people necessarily includes m mutual acquaintances or n mutual strangers. That is, R(m,n) \leq R(m-1,n) + R(m,n-1).

(b) By the usual symmetry argument, the same conclusion follows when M contains q people.

Question 7:

(Remark: A pretty property of Ramsey numbers related to combinatorics).

Show that if m and n are integers greater than 1, then R(m,n) \leq { {m+n-2} \choose {m-1}} — a non-recursive upper bound.

Solution 7:

When m=2, or n=2, (i) holds with equality (see problem 4 in this blog article). The proof is by induction on k=m+n. As we have just seen, the result is true when k=4. Assume the result true for k-1. Then,

R(m-1,n) \leq {{m+n-3} \choose {m-2}}  and R(m,n-1) \leq {{m+n-3} \choose {m-1}}

Now, Pascal’s identity gives:

{{m+n-3} \choose {m-2}} + {{m+n-3} \choose {m-1}} = {{m+n-2}} \choose {m-1} so that R(m-1,n) + R(m,n-1) \leq {{m+n-2}} \choose {m-1}

But, from the previous question and its solution, we get R(m,n) \leq R(m-1,n) + R(m, n-1)

PS: As Richard Feynman, used to say, you will have to “piddle” with smallish problems as particular cases of these questions in order to get a grip over theory or formal language of this introduction.

PS: Additionally, you can refer to any basic Combinatorics text like Brualdi, or Alan Tucker or even Schaum Series outline ( V K Balakrishnan).

Some number theory problems: tutorial set II: RMO and INMO

1. A simplified form of Fermat’s theorem: If x, y, z, n are natural numbers, and n \geq z, prove that the relation x^{n} + y^{n} = z^{n} does not hold.

2. Distribution of numbers: Find ten numbers x_{1}, x_{2}, \ldots, x_{10} such that (a) the number x_{1} is contained in the closed interval [0,1] (b) the numbers x_{1} and x_{2} lie in different halves of the closed interval [0,1] (c) the numbers x_{1}, x_{2}, x_{3} lie in different thirds of the closed interval [0,1] (d) the numbers x_{1}, x_{2}, x_{3} and x_{4} lie in different quarters of the closed interval [0,1],  etc., and finally, (e) the numbers x_{1}, x_{2}, x_{3}, \ldots, x_{10} lie in different tenths of the closed interval [0,1]

3. Is generalization of the above possible?

4. Proportions: Consider numbers A, B, C, p, q, r such that: A:B =p, B:C=q, C:A=r, write the proportion A:B:C = \Box : \Box : \Box in such a way that in the empty squares, there will appear expressions containing p, q, r only; these expressions being obtained by cyclic permutation of one another expressions.

5. Give an elementary proof of the fact that the positive root of x^{5} + x = 10 is irrational.

I will give you sufficient time to try these. Later, I will post the solutions.

Cheers,

Nalin Pithwa.

Some number theory training questions: RMO and INMO

Question 1:

Let us write an arbitrary natural number (for example, 2583), and then add the squares of its digits. (2^{2}+5^{2}+8^{2}+3^{2}=102). Next, we do the same thing to the number obtained. Namely, 1^{2}+0^{2}+2^{2}=5. Now proceed further in the same way:

5^{2}=25, 2^{2}+5^{2}=29, 2^{2}+9^{2}=85, \ldots.

Prove that unless this procedure leads to number 1 (in which case, the number 1 will, of course, recur indefinitely), it must lead to the number 145, and the following cycle will repeat again and again:

145, 42, 20, 4, 16, 37, 58, 89.

Question 2:

Prove that the number 5^{5k+1} + 4^{5k+2} + 3^{5k} is divisible by 11 for every natural k.

Question 3:

The number 3^{105} + 4^{105} is divisible by 13, 49, 181 and 379, and is not divisible by either 5 or by 11. How can this result be confirmed?

Cheers,

Nalin Pithwa.

Euler Series question and solution

Question:

Mengoli had posed the following series to be evaluated:

1+ \frac{1}{2^{2}} + \frac{1}{3^{2}} + \frac{1}{4^{2}} + \ldots.

Some great mathematicians, including Liebnitz, John Bernoulli and D’Alembert, failed to compute this infinite series. Euler established himself as the best mathematician of Europe (in fact, one of the greatest mathematicians in history) by evaluating this series initially by a not-so-rigorous method. Later on, he gave alternative and more rigorous ways of getting the same result.

Prove that the series converges and gets an upper limit. Then, try to evaluate the series.

Proof:

Due Nicolas Oresine:

Consider the following infinite series: \phi(s)=1 + \frac{1}{2^{s}} + \frac{1}{3^{s}} + \frac{1}{4^{s}} + ldots

We can re-write the preceding series as follows: \phi(s) = 1+ (\frac{1}{2^{s}}+\frac{1}{3^{s}}) + (\frac{1}{4^{s}} + \frac{1}{5^{s}} + \frac{1}{6^{s}} + \frac{1}{7^{s}}) + \ldots, which in turn is less than

1 + (\frac{2}{2^{s}}) + (\frac{4}{4^{s}}) + \ldots. Now, the RHS of this can be re-written as

1+(\frac{2}{2^{s}}) + (\frac{4}{4^{s}}) + \ldots=1 + \frac{1}{2^{(s-1)}}+ (\frac{1}{2^{(s-1)}})^{2} + \ldots, which is a geometric series and it is given by

\frac{1}{1-\frac{1}{2^{(s-1)}}}.

Now, we can say that \phi(s) will converge if \frac{1}{2^{(s-1)}}<1 \Longrightarrow s >1.

In order to prove what is asked, we start with \phi(s)=1 + \frac{1}{2^{s}}+ \frac{1}{3^{s}}+ \frac{1}{4^{s}}+\ldots

And, then multiply both sides by \frac{1}{2^{s}} and then subtract the resulting equation from the preceding equation to get

(1-\frac{1}{2^{2}})\phi(s)=1+\frac{1}{3^{s}}+\frac{1}{5^{s}}+\ldots

where all the terms containing the reciprocals of the sth power of even numbers vanished.

Repeating this procedure with \frac{1}{3^{s}} gives

(1-\frac{1}{2^{s}})(1-\frac{1}{3^{s}})\phi(s)=1+\frac{1}{5^{s}}+ \ldots

where all terms containing the reciprocals of the sth power of multiples of 3 vanished.

By continuing this with all prime numbers, we get

\prod_{p}(1-\frac{1}{p^{s}})\phi(s)=1, where p represents all prime numbers. Thus, we get

\phi(s)=1 + \frac{}{} + \frac{}{} + \frac{}{} + \ldots =\frac{1}{\prod_{p}(1-\frac{1}{p^{s}})}

This is a remarkable result because the LHS is concerned with only positive integers, whereas the RHS is concerned with only primes. This result is known as the “Golden Key of Euler”.

Riemann created his famous \zeta- function by extending the variable s to the entire complex plane, except s=1 with 

\zeta(s)=1+ \frac{1}{2^{s}} + \frac{1}{3^{s}} + \ldots .

This function is now very famous as the Riemann zeta function.

How can we apply the Golden Key of Euler to Mengoli’s question that we started with?

Ans. In the Golden Key of Euler, substitute s=2.

Hence, we get the upper limit of the given series is 2.

Euler’s proof (1775):

The proof ran as follows:

It is a little roundabout way of arriving at the correct answer from a known result. Consider McLaurin’s series expansion of sin x:

\sin{(x)}=x - \frac{x^{3}}{3!} + \frac{x^{5}}{5!} -\frac{x^{7}}{7!} + \frac{x^{9}}{9!} + \ldots

By dividing both sides by x and then substituting y=x^{2} on the right side, we get the following:

\frac{\sin{(x)}}{x} = 1-\frac{y}{3!} + \frac{y^{2}}{5!} - \frac{y^{3}}{7!} + \ldots

By taking a special value of x=n\pi (and, hence y=n^{2}\pi^{2}), we get the following:

\frac{\sin (n\pi)}{(n\pi)}=0=1-\frac{y}{3!} + \frac{y^{2}}{5!} - \frac{y^{3}}{5!}+ \ldots

Note  that preceding equation is not a polynomial, but an infinite series. But, Euler still treated it as a polynomial (that is why it was not accepted as a rigorous result) and observed that this “infinite” polynomial has roots equal to y_{n}=n^{2}x^{2}. Then, Euler had used the fact that the sum of the reciprocals of the roots is determined by the coefficient of the linear term (here, the y-term) when the constant is made unity. (check this as homework quiz, for a quadratic to be convinced). So, Euler had arrived at the following result:

1-\sum_{i=1}^{\infty}\frac{6}{y_{n}}=0 \Longrightarrow \sum_{i=1}^{\infty}\frac{1}{y_{n}}=\frac{1}{6}. With y_{n}=n^{2}(\pi)^{2}, we get the following:

\sum_{i=1}^{\infty}\frac{1}{n^{2}(\pi)^{2}}=\frac{1}{6} or, \sum_{1}^{n^{2}}\frac{1}{n^{2}}=\frac{(\pi)^{2}}{6}.

Another proof also attributed to Euler that uses the series expansion of sin (x) goes as follows below:

\sin {(x)} has roots given by 0, \pm \pi, \pm 2\pi, \pm 3\pi, …So does this polynomial that Euler reportedly constructed:

x(1-\frac{x^{2}}{(\pi)^{2}})(1-\frac{x^{2}}{(2\pi)^{2}})(1-\frac{x^{2}}{(3\pi)^{2}})\ldots=0

So, Euler considered the preceding equation to be equivalent to:

\sin{(x)}=x - \frac{x^{3}}{3!} + \frac{x^{5}}{5!} - \frac{x^{7}}{7!} + \ldots=0

Then, he had equated the coefficient of x^{3} in both to get the result:

\sum_{n=1}^{\infty}\frac{1}{n^{2}(\pi)^{2}} = \frac{1}{3!} = \frac{1}{6}.

Thus, \sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{(\pi)^{2}}{6}.

Later on, Euler had provided a few more alternate and rigorous proofs of this result.

Reference: Popular Problems and Puzzles in Mathematics by Asok Kumar Mallik, IISc Press, Foundation Books.

Amazon India link:

https://www.amazon.in/Popular-Problems-Puzzles-Mathematics-Mallik/dp/938299386X/ref=sr_1_1?s=books&ie=UTF8&qid=1520930311&sr=1-1&keywords=popular+problems+and+puzzles+in+mathematics.

Hope you all enjoyed it — learning to think like Euler !! By the way, it did take a long time for even analysis to become so rigorous as it is now….You might like this observation a lot. 🙂 🙂 🙂

Nalin Pithwa.

Huygens’ problem to Leibnitz: solution

In the Feb 23 2018 blog problem, we posed the following question:

Sum the following infinite series:

1+\frac{1}{3} + \frac{1}{6} + \frac{1}{10} + \frac{1}{15}+ \ldots.

Solution:

The sum can be written as:

S=\sum_{n=1}^{\infty}P_{n}, where P_{n}=\frac{2}{n(n+1)}=2(\frac{1}{n}-\frac{1}{n+1}).

Thus, 2(1-\frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \frac{1}{3} - \frac{1}{4} + \ldots)=2. This is the answer.

If you think deeper, this needs some discussion about rearrangements of infinite series also. For the time, we consider it outside our scope.

Cheers,

Nalin Pithwa.

Algebra question: RMO/INMO problem-solving practice

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,

3xy(b+ax)=d+ax^{3}, or ax^{3}-3ayx^{2}-3byx+d=0…call this equation II.

Subtracting Equation II from Equation I, we get

3(b+ay)x^{2}+3(c+by)x=0

(b+ay)x+c+by=0 since x \neq 0

axy+b(x+y)+c=0 which is the required transformation.

Now, (ay+b)x=-(by+c), that is, x=-\frac{by+c}{ay+b}

Putting this value of x in Equation I, we get

-a(\frac{by+c}{ay+b})^{3}+3b(\frac{by+c}{ay+b})^{2}-3c(\frac{by+c}{ay+b})+d=0, that is,

a(by+c)^{3}-3b(by+c)^{2}(ay+b)+3c(by+c)(ay+b)^{2}-d(ay+b)^{3}=0, which is the required equation.

Cheers,

Nalin Pithwa.