# Pick’s theorem: a geometry problem for RMO practice

Pick’s theorem:

Consider a square lattice of unit side. A simple polygon (with non-intersecting sides) of any shape is drawn with its vertices at the lattice points. The area of the polygon can be simply obtained as $B/2+I-1$ square units, where B is the number of lattice points on the boundary; I = number of lattice points in the interior region of the polygon. Prove this theorem.

Proof:

Refer Wikipedia 🙂 🙂 🙂

https://en.wikipedia.org/wiki/Pick%27s_theorem

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.

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.

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

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

# Is there a Fermat in you?? A solution possible

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

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

Fermat’s Problem:

Pierre de Fermat (1601-65), the great French mathematical genius, is described as the “Prince of Amateurs”, as he was not a professional mathematician and never published any work during his lifetime. As a civil servant, he served in the judiciary and spent his leisure with mathematics as his hobby. He corresponded with the best of mathematicians of his time. He teased the contemporary English mathematicians, Wallis and Digby, with the following problem, who had to admit defeat:

26 is a number that is sandwiched between a perfect square (25) and a perfect cube (27). Prove that there is no such number.

Solution:

We show that the equation $y^{3}=x^{2}+2$ has only one solution for positive integers x and y, viz., $x=5$ and $y=3$. First, we write $y^{3}=x^{2}+2=(x+i\sqrt{2})(x-i\sqrt{2})$. It can be shown that unique prime factorization occurs in the complex number system $a+ ib\sqrt{2}$. It can be also argued that since the product of the two complex numbers of that form is a cube, each factor must be a cube. So, we write:

$x+i\sqrt{2}=(a+ib\sqrt{2})^{3}=a^{3}-6ab^{2}+i(3a^{2}b-2b^{3})\sqrt{2}$.

Equating imaginary parts of both sides, we get

$3a^{2}b-2b^{3}=b(3a^{2}-2b^{2})=1$.

Thus, $b=\pm 1$ and $3a^{2}-2b^{2}=\pm 1$, both having the same sign. But, with $b=-1$, one gets $a^{2}=1/3$, which is not possible. So, we take $b=1$ when $a=\pm 1$. Finally, with $a=1$, $x=-5$ and with $a=-1, x=5$. The sign of x is irrelevant as only $x^{2}$ is involved in the original equation. With the solution $x=5$, we get $y=3$ as the only set of solution.

Cheers,

Nalin Pithwa.

# Is there a “Fermat” in you? ? :-)

Fermat’s problem:

Pierre de Fermat (1601-65), the great French mathematical genius, is described as the “Prince of Amateurs” as he was not a professional mathematician and never published any work during his lifetime. As a civil servant, he served in the judiciary and spent his leisure with mathematics as his hobby. He corresponded with the best of mathematicians of his time. He teased the contemporary English mathematicians, Wallis and Digby, with the following problem, who had to admit defeat.

Problem:

26 is a number that is sandwiched between a perfect square (25) and a perfect cube (27). Prove that there is no other such number.

Please do try and let me know your solutions. Even partial solutions are welcome.

Cheers,

Nalin Pithwa.

# Miscellaneous problems/solutions for RMO training: Homi Bhabha Science Foundation

Problem:

Let f be a bijective function from the set $A = \{ 1,2,3,\ldots,n\}$ to itself. Show that there is a positive integer $M>1$ such that $f^{M}(1)=f(1)$ for each $i \in A$. Here, $f^{M}$ denotes the composite function $f \circ f \circ f \circ \ldots \circ f$ repeated M times.

Proof:

The student should be familiar with the following properties of bijective functions:

a) If $f:A \rightarrow A$ is a bijective function then there is a unique bijective function $g: A \rightarrow A$ such that $f \circ g = g \circ f=I_{A}$, the identity function on A. The function g is called the inverse of f and is denoted by $f^{-1}$. Thus, $f \circ f^{-1}=I_{A}=f^{-1}\circ f$

b) $f \circ I_{A}=I_{A} \circ f$

c) If f and g are bijections from A to B, then so are $g\circ f$ and $f \circ g$.

d) If f, g, h are bijective functions from A to B and $f \circ g = f \circ h$, then $g=h$.

Apply $f^{-1}$ at left to both sides to obtain $g=h$.

Coming to the problem, since A has n elements, we see that there are only finitely many (in fact, n!) bijective functions from A to A as each bijective function f gives a permutation of $\{ 1,2,3,\ldots,n\}$ by taking $\{ f(1), f(2), \ldots, f(n)\}$. Since f is a bijective function from A to A, so is each of the functions in the sequence: $f \circ f = f^{2}$, $f \circ f \circ f=f^{3}$, $\ldots$, $f^{n}$, \ldots

All these cannot be distinct since there are only finitely many bijective functions from A to A. Hence, for some two distinct positive integers $m >n$, say, we must have $f^{m}=f^{n}$

If $n=1$, we take $, latex M=m$, to obtain the result. If $n>1$, multiply both sides by $(f^{-1})^{n-1}$, to get $f^{m-n-1}=f$. We take $M=m-n+1$ to get the relation $f^{M}=f$ when $M>1$.

Note this means $f^{M}(i)=f(i)$ for all $i \in A$.

Aliter:

Take any element r in the set A and consider the sequence of elements

$r, f(r), (f \circ f)(r), (f \circ f \circ f)(r), \ldots$

obtained by applying f successively. Since A has only n elements there must be repetitions in the above sequence. But, when the first repetition occurs, this must be r itself, for, if the above sequence looks (for instance) like:

$r, a, b, c, d, e, c, \ldots$ where the first repetition is an element c other than r, this would imply $f(b)=c$ and $f(e)=c$ contradicting the fact that f is a bijection. Thus, for some positive integer $l_{r} \geq 1$, we have $f^{l_{r}}=r$.

This is true for each r in the set $A=1,2, \ldots, n$. By taking M to be the lcm of $l_{1}, l_{2}, \ldots, l_{r}$, we get

$f^{M}(r)=r$ for each $r \in A$.

Note: If f itself is the identity function the above proof fails because each $l_{r}=1$. But, in this case, we may take M to be any integer greater than or equal to 2.

Problem:

Show that there exists a convex hexagon in the plane such that:

(a) all its interior angles are equal, (b) its sides are 1,2,3,4,5,6 in some order.

Proof:

Let ABCDEF be an equiangular hexagon with side-lengths as 1,2,3,4,5,6 in some order. We may assume WLOG that $AB=1$. Let $BC=a$, $CD=b$, $DE=c$, $EF=d$, $FA=e$.

Since the sum of all the angles of a hexagon is equal to $(6-2) \times 180 \deg=720 \deg$, it follows that each interior angle must be equal to $\frac{720 \deg}{6}=120 \deg$. Let us take A as the origin, the positive x-axis along AB and the perpendicular at A to AB as the y-axis. Use vectors. If the vector is denoted by $(x,y)$, we then have

$\overline {AB}=(1,0)$

$\overline {BC}=(a\cos{60 \deg},a \sin{60\deg})$

$\overline {CD}=(b\cos{120\deg},b\sin{120 \deg})$

$\overline{DE}=(c\cos{180\deg},c\sin{180\deg})=(-c,0)$

$\overline{EF}=(a\cos {240} \deg, d\sin {240}\deg)$,

$\overline{FA}=(e\cos {300}\deg, e\sin{300}\deg)$

This is because these vectors are inclined to the positive x-axis at angles $0 \deg, 60 \deg, 120 \deg, 180 \deg, 240\deg, 300 \deg$ respectively.

Since the sum of all these 6 vectors is $\overline{0}$, it follows that $1+\frac{a}{2}-\frac{b}{2}-c-\frac{d}{2}+\frac{e}{2}=0$,

and, $(a+b-d-e)\frac{\sqrt{3}}{2}=0$. That is, $a-b-2c-d+e+2=0$…call this I

and $a+b-d-e=0$….call this II.

Since $\{a,b,c,d,e \} = \{2,3,4,5,6 \}$, in view of II, we have the following:

(i) $\{a,b \}=\{2,5 \}, \{d,e \}=\{ 3,4\}, c=6$

ii) $\{ a,b\}=\{ 3,6\}, \{d,e \}=\{4,5 \}, c=2$.

iii) $\{a,b \}=\{2,6 \}, \{d,e \}=\{3,5 \}, c=4$

Note: the possibility that $\{ a,b\}=\{3,4 \}$ and $\{ d,e\}=\{ 2,5\}$ in (i), for instance,need not be considered separately, because we can reflect the figure about $x=\frac{1}{2}$ and interchange these two sets.

Case (i):

Here, $(a-b)-(d-e)=2c-2=10$. Since $a-b= \pm 3$, $d-e= \pm 1$, this is not possible.

Case (ii):

Here, $(a-b)-(d-e)$=2c-2=2\$. This is satisfied by $(a,b,d,e)=(6,3,5,4)$

Case (iii):

Here, $(a-b)-(d-e)=2c-2=6$

This is satisfied by $(a,b,d,e)=(6,2,3,5)$.

Hence, we have essentially two different solutions: $(1,6,3,2,5,4)$ and $(1,6,2,4,3,5)$. It may be verified that (I) and (II) are both satisfied by these sets of values.

Aliter:

Consider an equilateral triangle of side 9 units. Remove from the three corners equilateral triangles of sides 1 unit, 2 units, and 3 units respectively. The remaining portion is now an equiangular hexagon ABCDEF with sides 1,6,2,4,3,5 as required.

Problem:

There are ten objects with total weight 20, each of the weights being a positive integer. Given that none of the weights exceed 10, prove that the ten objects can be divided into two groups that balance each other when placed in the two pans of a balance.

Solution:

Let $a_{1}, a_{2}, \ldots, a_{10}$ denote the weights of the 10 objects in decreasing order. It is given that $10 \geq a_{1} \geq a_{2} \geq \ldots a_{10} \geq 1$ and that $a_{1}+a_{2}+ \ldots + a_{10}=20$. For each i, $1 \leq i \leq 9$, let $S_{i}=a_{1}+ \ldots + a_{i}$. (For example, $S_{1}=a_{1}$, $S_{2}=a_{1}+a_{2}$, etc.Consider the 11 numbers $0, S_{1}, S_{2}, \ldots, S_{9}, a_{1}-a{10}$. Note that all these 11 numbers are non-negative and we have $0 \leq a_{1}-a_{10}<10$ and $1 for $1 \leq i \leq 9$. Now, look at the remainders when these 11 numbers are divided by 10. We have 10 possible remainders and 11 numbers and hence, by the Pigeon Hole Principle at least some two of these 11 numbers have the same remainder.

Case (i):

For some j, $S_{j}$ has the remainder 0, that is, $S_{j}$ is multiple of 10. But, since $1, the only possibility is that $S_{j}=10$. Thus, we get a balancing by taking the two groups to be $a_{1}, \ldots, a_{j}$ and $a_{j+1}, \ldots, a_{10}$.

Case (ii):

Suppose $a_{1}-a_{10}$ is a multiple of 10. But, then since $0 \leq a_{1}-a_{10}<10$, this forces $a_{1}-a_{10}=0$, which, in turn, implies that all the weights are equal and equal to 2 as they add up to 20. In this case, taking any five weights in one group and the remaining in the other we again get a balancing.

Case (iii):

For some j and k, say $j,  we have that $S_{j}$ and $S_{k}$ have the same remainder, that is, $S_{k}-S_{j}$ is a multiple of 10. But, again since $0, we should have $S_{k}-S_{j}=10$, that is, $a_{k}+a_{k-1}+\ldots + a_{j+1}=10$, and we get a balancing.

Case (iv):

Suppose $(a_{1}-a_{10})$ and $S_{j}$ for some j ($1 \leq j \leq 9$) have the same remainder, that is, $S_{j}-(a_{1}-a_{10})$ is a multiple of 10. As in the previous cases, this implies that $S_{j}-(a_{1}-a_{10})=10$. That is, $a_{2}+a_{3}+ \ldots + a_{j}+a_{10}=10$. Hence, $\{a_{2},a_{3}, ldots, a_{j},a_{10} \}$ and $\{ a_{1}, a_{j+1}, \ldots, a_{9}\}$ balance each other.

Thus, in all cases, the given 10 objects can be split into two groups that balance each other.

Problem:

At each of the eight corners of a cube write +1 or -1 arbitrarily. Then, on each of the six faces of the cube write the product of the numbers written at the four corners of that face. Add all the fourteen numbers so written down. Is it possible to arrange the numbers +1 and -1 at the corners initially so that this final sum is zero?

Solution:

Let $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}$ be the numbers written at the corners. Then, the final sum is given by

$\sum_{i=1}^{8}x_{i}+x_{1}x_{2}x_{3}x_{4}+x_{5}x_{6}x_{7}x_{8}+x_{1}x_{4}x_{5}x_{8}+x_{2}x_{3}x_{6}x_{7}+x_{1}x_{2}x_{5}x_{6}+x_{3}x_{4}x_{7}+x_{8}$.

Because there are fourteen terms in the above sum, and each of the terms is +1 or -1, the sum will be zero only if some seven terms are +1 each and the remaining 7 terms are -1 each.

But, the product of the fourteen terms is $(x_{1}x_{2}x_{3}x_{4}x_{5}x_{6}x_{7}x_{8})^{4}=(\pm 1)^{4}=+1$.

Therefore, it is impossible to have an odd number of -1’s in the above sum.

We conclude that the desired arrangement is not possible.

Problem:

Given the 7-element set $A= \{ a,b,c,d,e,f,g\}$, find a collection T of 3-element subsets of A such that each pair of elements from A occurs exactly in one of the subsets of T.

Solution:

One possible solution collection is as follows:

$\{ a, b, c\}$, $\{ a,d,e\}$, $\{a, f, g\}$, $\{ b,d,f\}$. $\{b,e,g \}$, $\{ c,e,f\}$, $\{ c,d,g\}$. Note that there could be other combinations obtained by permitting the letters. WLOG, a can be associated with three pairs b,c,d; e, f, g. Now b can be associated with d, f and e, g. The possible choices left for c are only the pairs e,f and d,g. This arrangement does work.

Hope you all enjoy such type of questions. Please compare your attempts with the solutions given above.

Cheers,

Nalin Pithwa.

Reference: Problem Primer for the Olympiad, C. R. Pranesachar, B J Venkatchala, C. S. Yogananda, Prism Books.