Home » Posts tagged 'Contests'

Tag Archives: Contests

On an infinite summation

Let \{x_n\}_{n=1}^{\infty} be a sequence of real numbers. Compute:

    \[\mathcal{V} = \sum_{n=1}^{\infty} \sin^2 x_n \prod_{k=1}^{n-1} \cos^2 x_k + \prod_{n=1}^{\infty} \cos^2 x_n\]

Solution

First and foremost we set a_n = \sin^2 x_n and it is obvious that 0 \leq a_n \leq 1. We are making use of probabilistic methods. Suppose than an infinite number of coins are flipped. Let a_n be the probability that the n -th coin toss lands heads and let us consider the first time heads comes up. Then a_n \prod \limits_{k=1}^{n-1} (1 -a_k) is the probability that the first head appears in the n – th flip and \prod \limits_{n=1}^{\infty} (1-a_n) is the probability that all flips come up tails. Thus,

    \[\sum_{n=1}^{\infty} \sin^2 x_n \prod_{k=1}^{n-1} \cos^2 x_k + \prod_{n=1}^{\infty} \cos^2 x_n=1\]

Read more

Trigonometric equality

Prove that in any triangle ABC it holds that

    \[\sum \sqrt{\frac{\sin A}{\sin B \sin C}} = \sqrt{\frac{2R}{r} \sum \sin A}\]

where R denotes the circumradius and r the inradius.

Solution

Using the law of sines we have that

    \[\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2 R\]

and if we denote \mathcal{A} the area of the triangle then

    \[\frac{r \left ( a + b + c \right )}{2} = \mathcal{A} = \frac{abc}{4R}\]

Thus,

    \begin{align*} \sum \sqrt{\frac{\sin A}{\sin B \sin C}} &= \sum \sqrt{\frac{a}{2R} \cdot \frac{2R}{b} \cdot \frac{2R}{c}} \\ &=\sum \sqrt{\frac{ a}{bc} \cdot 2 R} \\ &=\sum \sqrt{\frac{a}{bc} \cdot \frac{abc}{2\mathcal{A}}} \\ &=\frac{a+b+c}{\sqrt{2 \mathcal{A}}} \\ &= \sqrt{\frac{a+b+c}{\frac{2\mathcal{A}}{a+b+c}}} \\ &= \sqrt{\frac{a+b+c}{r}} \\ &= \sqrt{\frac{1}{r} \sum a} \\ &= \sqrt{\frac{2R}{r} \sum \frac{a}{2R}} \\ &= \sqrt{\frac{2R}{r} \sum \sin A} \end{align*}

Read more

 

Root inequality

Let a, b, c be three positive real numbers such that \sqrt{a} + \sqrt{b} + \sqrt{c}=1. Prove that

    \[\frac{\sqrt{a}}{a^2+2bc} + \frac{\sqrt{b}}{b^2+2ca} + \frac{\sqrt{c}}{c^2+2ab} \leq \frac{1}{a} + \frac{1}{b} + \frac{1}{c}\]

Solution

By AM – GM we have,

    \begin{align*} \sum \frac{\sqrt{a}}{a^2+2bc} &\leq \sum \frac{\sqrt{a}}{a^2 + 2\left ( \frac{b^2+c^2}{2} \right )} \\ &= \frac{1}{a^2+b^2+c^2} \sum \sqrt{a}\\ &= \frac{1}{a^2+b^2+c^2} \end{align*}

However,

    \begin{align*} 1 &= \left (\sum \sqrt{a} \right )^2 \\ &=\left ( \sum \frac{a}{\sqrt{a}} \right )^2 \\ &\leq \left ( \sum a^2 \right ) \cdot \left ( \sum \frac{1}{a} \right ) \end{align*}

Hence \displaystyle \frac{1}{a^2+b^2+c^2} \leq \frac{1}{a} + \frac{1}{b} + \frac{1}{c} and the exercise is complete.

Read more

Square of an integer

Let a, b be positive integers such that ab +1 divides a^2+b^2. Show that

    \[\frac{a^2+b^2}{ab+1}\]

is the square of an integer.

Solution

This is a very well known problem. It first appeared in IMO 1988 held in Canberra, Australia. It even has its own Wikipedia page.

History Background

One of the organisers had sent this exercise to all professors of Number Theory to check if the exercise is original and try to solve it within 4 hours. No one was able to do so. However, one Bulgarian student managed to solve the problem in less than 4 hours ( his solution was fallen from the sky )  and for that he was awarded a special reward beyond the medal.

Solution

 

Choose integers a,b,k such that a^2+b^2=k(ab+1) Now, for fixed k, out of all pairs (a,b) choose the one with the lowest value of \min(a,b). Label b'=\min(a,b), a'=\max(a,b). Thus, a'^2-kb'a'+b'^2-k=0 is a quadratic in a'. Should there be another root, c', the root would satisfy: b'c'\leq a'c'=b'^2-k<b'^2\implies c'<b' Thus, c' isn’t a positive integer (if it were, it would contradict the minimality condition). But c'=kb'-a', so c' is an integer; hence, c'\leq 0. In addition, (a'+1)(c'+1)=a'c'+a'+c'+1=b'^2-k+b'k+1=b'^2+(b'-1)k+1\geq 1 so that c'>-1. We conclude that c'=0 so that b'^2=k.

This construction works whenever there exists a solution (a,b) for a fixed k, hence k is always a perfect square.

Read more

On permutation

Let x_1, x_2, \dots, x_k be vectors of m – dimensional Euclidean space such that x_1+x_2+\cdots+x_k=0. Prove that there exists a permutation \pi of the integers \{1, 2, \dots,k\} such that

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|\leq\left ( \sum_{i=1}^{k} \left \| x_i \right \|^2 \right )^{1/2}\]

for each n=1,2, \dots, k.

Solution

We define \pi inductively. Set \pi(1)=1.Assume \pi is defined for i=1, 2, \dots, n and also

(1)   \begin{equation*} \left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \end{equation*}

Note that (1) is true for n=1. We choose \pi(n+1) in a way that (1) is fulfilled for n+1 instead of n. Set y=\sum \limits_{i=1}^{n} x_{\pi(i)} and A=\{1,2, \dots, k\} \setminus \{\pi(i) : i=1,2, \dots, n\}. Assume that (y, x_r)>0 for all r \in A.  Then \left ( y , \sum \limits_{r \in A} x_r \right )>0 and in view of y + \sum \limits_{r \in A} x_r =0 ones gets -(y, y)>0 which is impossible. Hence , there is r\in A such that

(2)   \begin{equation*} (y, x_r)\leq 0\end{equation*}

Put \pi(n+1) = r . Then using (2) and (1) we have

    \begin{align*} \left \| \sum_{i=1}^{n+1} x_{\pi(i)} \right \|^2 &= \left \| y + x_r \right \|^2 \\ &=\left \| y \right \|^2 + 2\left ( y, x_r \right ) + \left \| x_r \right \|^2 \\ &\leq \left \| y \right \|^2 + \left \| x_r \right \|^2 \\ &\leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 + \left \| x_r \right \|^2\\ &= \sum_{i=1}^{n+1} \left \| x_{\pi(i)} \right \|^2 \end{align*}

which verifies (1) for n+1. Thus we define \pi for every n=1, 2, \dots, k. Finally from (1) we get

    \[\left \| \sum_{i=1}^{n} x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{n} \left \| x_{\pi(i)} \right \|^2 \leq \sum_{i=1}^{k} \left \| x_i \right \|^2\]

Read more

Donate to Tolaso Network