olympiad | Beni Bogoşel's blog

An inequality involving complex numbers

March 19, 2024 beni22sof Leave a comment

Consider ${n\geq 1}$ and ${n}$ complex numbers ${z_1,...,z_n \in \Bbb C}$ . Show that

$\displaystyle \sum_{k =1}^n |z_k||z-z_k|\geq \sum_{k=1}^n |z_k|^2, \text{ for every } z \in \Bbb{C},$

if and only if ${z_1+...+z_n = 0}$ .

Proposed by Dan Stefan Marinescu in the Romanian Mathematical Gazette

Solution: For someone familiar with optimality conditions in multi-variable calculus this is straightforward. Notice that

$\displaystyle f(z) = \sum_{k =1}^n |z_k||z-z_k|$

is a convex function (linear combination of distances in the plane). The inequality is equivalent to ${f(z) \geq f(0)}$ , which means that ${0}$ is the global minimum of the function.

For a convex, differentiable function global minimality is equivalent to verifying first order optimality conditions. Denoting ${z = x+iy}$ , ${z_k = x_k+iy_k}$ the partial derivatives of the function ${f}$ with respect to ${x,y}$ are

$\displaystyle \frac{\partial f}{\partial x}(x,y) = \sum_{k=1}^n \sqrt{x_k^2+y_k^2}\frac{x-x_k}{\sqrt{(x-x_k)^2+(y-y_k)^2}},$

$\displaystyle \frac{\partial f}{\partial y}(x,y) = \sum_{k=1}^n \sqrt{x_k^2+y_k^2}\frac{y-y_k}{\sqrt{(x-x_k)^2+(y-y_k)^2}}.$

If ${\frac{\partial f}{\partial x}(0,0) = \frac{\partial f}{\partial y}(0,0)}$ then ${\sum x_k=\sum y_k = 0}$ and the conclusion follows. The converse also holds, obviously.

Since this problem was proposed for 10th grade, let’s use some simpler arguments to arrive to a proof. Denote by ${g = \frac{1}{n}(z_1+...+z_n)}$ . A quick computation using properties of the modulus gives:

$\displaystyle \sum_{k=1}^n |z-z_k|^2 = n|z-g|^2+\sum_{i=1}^n |z_k|^2$

Thus ${\sum_{k=1}^n |g-z_k|^2 = \sum_{i=1}^n |z_k|^2}$ . Of course, the classical inequality ${a^2+b^2 \geq 2ab}$ implies

$\displaystyle 2\sum_{k=1}^n |z_k|^2 = \sum_{k=1}^n |g-z_k|^2+\sum_{i=1}^n |z_k|^2\geq 2 \sum_{k=1}^n |z_k||g-z_k|.$

If the inequality in the statement of the problem holds, the above relation becomes an equality and ${|z_k|=|g-z_k|}$ for all ${k=1,...,n}$ . Therefore points ${z_k}$ belong to the mediatrix of the segment ${0g}$ . Therefore the centroid ${g}$ also belongs to this mediatrix and to ${0g}$ , which implies ${g=0}$ , as requested.

Conversely, if ${z_1+...+z_k = 0}$ consider the inequality

$\displaystyle |a||b| \geq \frac{1}{2}(\overline a b + a\overline b)$ to conclude.

Categories: Complex analysis, Geometry, Inequalities, Olympiad Tags: complex, Geometry, inequality, olympiad

Romanian Regional Olympiad 2024 – 10th grade

March 12, 2024 beni22sof Leave a comment

Problem 1. Let ${a,b \in \Bbb{R}}$ , ${a>1}$ , ${b>0}$ . Find the smallest real number ${\alpha}$ such that

$\displaystyle (a+b)^x \geq a^x+b, \forall x \geq \alpha.$

Problem 2. Consider ${ABC}$ a triangle inscribed in the circle ${\mathcal C}$ of center ${O}$ and radius ${1}$ . For any ${M \in \mathcal C\setminus \{A,B,C\}}$ denote by ${S(M) = OH_1^2+OH_2^2+OH_3^2}$ where ${H_1,H_2,H_3}$ are the orthocenters of the triangles ${MAB,MBC,MCA}$ , respectively.

a) Prove that if the triangle ${ABC}$ is equilateral then ${s(M)=6}$ for every ${M \in \mathcal C \setminus \{A,B,C\}}$ .

b) Show that if there exist three distinct points ${M_1,M_2,M_3 \in \mathcal C\setminus \{A,B,C\}}$ such that ${s(M_1)=s(M_2)=s(M_3)}$ , then the triangle ${ABC}$ is equilateral.

Problem 3. Let ${a,b,c}$ be three non-zero complex numbers with the same modulus for which ${A=a+b+c}$ and ${B=abc}$ are real numbers. Show that for every positive integer ${n}$ the number ${C_n = a^n+b^n+c^n}$ is real.

Problem 4. Let ${n \in \Bbb N^*}$ . Determine all functions ${f:\Bbb{R} \rightarrow \Bbb{R}}$ which verify

$\displaystyle f(x+y^{2n})=f(f(x))+y^{2n-1}f(y),$

for every ${x,y \in \Bbb{R}}$ and such that ${f(x)=0}$ has a unique solution.

Hints:

Problem 1: study the monotonicity of the function ${g(x)= (a+b)^x-a^x}$ . Then observe that the inequality is equivalent to ${g(x) \geq g(1)}$ .

Problem 2: Recall the identity ${OH^2 = 9R^2-AB^2-BC^2-CA^2}$ whenever ${H}$ is the orthocenter of ${ABC}$ with circumcenter ${O}$ . This can be proved using complex numbers and recalling that ${OH = 3OG}$ , where ${G}$ is the center of gravity. Therefore

$\displaystyle OH_1^2 = 9-MA^2-MB^2-AB^2$ and the analogue equalities. Summing we get

$\displaystyle s(M) = 27-2\sum MA^2-\sum AB^2.$ a) When ${ABC}$ is equilateral and inscribed in a circle of radius ${1}$ we have ${AB=BC=CA=\sqrt{3}}$ . Moreover, the identity In particular, one can prove the following:

$\displaystyle AM^2+BM^2+CM^2 = AG^2+BG^2+CG^2+3MG^2$ applied to the triangle equilateral triangle ${ABC}$ with centroid ${O}$ shows that

$\displaystyle MA^2+MB^2+MC^2 = AO^2+BO^2+CO^2+3MO^2=6.$ Thus

$\displaystyle s(M) = 27-12-9 = 6.$ b) Assume there exist three distinct points such that ${s(M_1)=s(M_2)=s(M_3)}$ . This implies that

$\displaystyle \sum M_1A^2 = \sum M_2A^2 = \sum M_3A^2.$ The relation above concerning the center of gravity of ${ABC}$ shows that ${M_1G=M_2G=M_3G}$ . Since the points are distinct, it follows that ${G}$ coincides with ${O}$ , the circumcenter of ${ABC}$ , therefore ${ABC}$ is equilateral.

Problem 3: Denote ${r>0}$ the common value of the modulus: ${|a|=|b|=|c|=r}$ . Then

$\displaystyle \overline{a+b+c} = r^2\left( \frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) = r^2 \frac{ab+bc+ca}{abc}.$ Since ${r, a+b+c, abc \in \Bbb{R}}$ it follows that ${ab+bc+ca\in \Bbb{R}}$ . Then of course ${a^2+b^2+c^2 = (a+b+c)^2-2(ab+bc+ca) \in \Bbb{R}}$ . Finally, we know that ${a,b,c}$ are roots of

$\displaystyle (z-a)(z-b)(z-c)=0 \Longleftrightarrow z^3-(a+b+c)z^2+(ab+bc+ca)z-abc=0.$ Since the coefficients of this polynomial are real, an inductive argument shows that if ${C_n, C_{n+1}, C_{n+2}}$ are real then ${C_{n+3}}$ is real, finishing the proof.

Problem 4. Take ${y=0}$ and get ${f(x) = f(f(x))}$ . Thus, ${f}$ is the identity mapping on its image!! Take ${y\mapsto -y}$ and observe that ${y^{2n-1}f(y) = -y^{2n-1}f(-y)}$ . Therefore ${f(-y)=-f(y)}$ for any ${y \neq 0}$ . Since the equation ${f(x)=0}$ has a unique solution, it follows that ${f(0)=0}$ and ${f(x) \neq 0}$ for ${x \neq 0}$ . Take ${x=0}$ and get ${f(y^{2n}) = y^{2n-1}f(y)}$ . Therefore

$\displaystyle f(x+y^{2n})=f(x)+f(y^{2n})$ for any ${x,y}$ . Since ${y^{2n}}$ takes all positive values in ${\Bbb{R}}$ it follows that

$\displaystyle f(x+y) = f(x)+f(y)$ for every ${x\in \Bbb{R}}$ , ${y \geq 0}$ . Coupled with ${f(-y)=-f(y)}$ this implies that

$\displaystyle f(x+y)= f(x)+f(y).$ for all ${x,y}$ . If ${f(x_1)=f(x_2)}$ it follows that ${f(x_1-x_2)=0}$ therefore ${x_1=x_2}$ . From ${f(f(x))=f(x)}$ we obtain ${f(x)=x}$ for all reals ${x}$ . It should be noted that this function obviously verifies the functional equation!

Categories: Algebra, Geometry, Olympiad Tags: Algebra, complex, Geometry, olympiad

Geometry problem: a property of the 40-40-100 triangle

December 5, 2022 beni22sof 1 comment

Consider the triangle ${ABC}$ with ${\angle A = 100^\circ}$ and ${\angle B = \angle C = 40^\circ}$ . Consider ${D \in AC}$ such that ${\angle CBD = 10^\circ}$ . Prove that ${AD = BC}$ .

This is a surprising result and easy to remember. I first saw this back in the days I was solving olympiad problems. The 40-40-100 triangle has this nice characteristic property. There is a very nice geometric proof and a one liner trigonometry argument.

Categories: Geometry, IMO, Olympiad Tags: angle chasing, Geometry, olympiad

Minimal volume of some particular convex sets in the cube

November 21, 2022 beni22sof Leave a comment

Consider a cube and a convex body $K$ contained in it such that the projections of this body on every face of the cube completely covers that face. Prove that the volume of the convex body is at least equal with a third of the volume of the cube.

Categories: Calculus of Variations, Combinatorics, Geometry, IMO, Inequalities, Olympiad, Optimization Tags: convex, cube, minimal, olympiad, optimization, volume

IMC 2022 – Day 1 – Problem 1

August 8, 2022 beni22sof Leave a comment

Problem 1. Let ${f:[0,1]\rightarrow (0,\infty)}$ be an integrable function such that ${f(x)\cdot f(1-x) = 1}$ for all ${x\in [0,1]}$ . Prove that

$\displaystyle \int_0^1 f(x) dx \geq 1.$

Solution: If you want just a hint, here it is: Cauchy-Schwarz. For a full solution read below.

Categories: Analysis, Olympiad, Problem Solving Tags: Analysis, IMC, IMO, olympiad

Function with zero average on vertices of all regular polygons

July 4, 2022 beni22sof Leave a comment

Fix a positive integer ${n \geq 3}$ . Let ${f:\Bbb{R}^2 \rightarrow \Bbb{R}}$ be a function such that for any regular ${n}$ -gon ${A_1...A_n}$ we have

$\displaystyle f(A_1)+...+f(A_n) = 0.$

Prove that ${f}$ is identically equal to zero.

Source: Romanian Team Selection Test 1996, see also the Putnam Contest Problems from 2009.

Solution: The solution comes by looking at some examples:

1. Consider an equilateral triangle ${A_1A_2A_3}$ . It is possible to produce another two equilateral triangles ${A_1B_2B_3}$ and ${A_1C_2C_3}$ such that ${A_2B_2C_2}$ , ${A_3B_3C_3}$ are equilateral. Note that we kept a common vertex and we rotated the initial triangle by ${2\pi/3}$ and ${4\pi/3}$ . Applying the result for all the small triangles and summing we obtain

$\displaystyle 3f(A_1)+... = 0$

where the missing terms are again sums of values of ${f}$ on some equilateral triangles. It follows that ${f(A_1)=0}$ .

2. For a square things are even simpler, since considering rotations of a square around one vertex one ends up with a configuration containing a square, its midpoints and its center. A similar reasoning shows that the value of the function ${f}$ at the center needs to be equal to zero, summing the values of the function ${f}$ on the vertices of all small squares.

In the general case, the idea is the same. Consider an initial polygon ${A_1...A_n}$ and rotate it around ${A_1}$ with angles ${2k\pi/n}$ , ${1\leq k \leq n-1}$ . Then sum all the values of the function on the vertices of these regular polygons. Observe that the vertex ${A_1}$ is repeated ${n}$ times while all other vertices are part of some regular polygon. In the end we get

$\displaystyle n f(A_1)+0 = 0$

where the zeroes correspond to sums over vertices of regular polygons.

The same type of reasoning should hold when the sum over vertices of regular polygons is replaced by an integral on a circle. The proof would follow the same lines. Fix a point ${A}$ , then integrate ${f}$ on all rotations of the circle ${C}$ through ${A}$ . On one side this integral should be equal to zero. On the other it contains the value of ${f}$ in ${A}$ and values on concentric circles in ${A}$ . This should imply that ${f(A)}$ is zero for any point ${A}$ .

Categories: Geometry, IMO, Olympiad, puzzles Tags: IMO, integral, olympiad, regular polygons

Putnam 2021 – Day 1

February 7, 2022 beni22sof Leave a comment

Here you can find the problems of the first day of the Putnam 2021 contest. Source.

A1. A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops. Each hop has length ${5}$ , and after each hop the grasshopper is at a point whose coordinates are both integers; thus, there are ${12}$ possible locations for the grasshopper after the first hop. What is the smallest number of hops needed for the grasshopper to reach the point ${(2021,2021)}$ ?

A2. For every positive real number ${x}$ , let

$\displaystyle g(x) = \lim_{r\rightarrow 0} \left((x+1)^{r+1}-x^{r+1}\right)^{\frac{1}{r}}.$

Find ${\lim_{x \rightarrow \infty} \frac{g(x)}{x}}$ .

A3. Determine all positive integers ${N}$ for which the sphere

$\displaystyle x^2+y^2+z^2=N$

has an inscribed regular tetrahedron whose vertices have integer coordinates.

A4. Let

$\displaystyle I(R)= \iint_{x^2+y^2\leq R^2} \left( \frac{1+2x^2}{1+x^4+6x^2y^2+y^4}-\frac{1+y^2}{2+x^4+y^4}\right) dx dy.$

Find ${\lim_{R\rightarrow \infty} I(R)}$ , or show that this limit does not exist.

A5. Let ${A}$ be the set of all integers ${n}$ such that ${1 \leq n \leq 2021}$ and ${\gcd (n,2021)=1}$ . For every nonnegative integer ${j}$ , let

$\displaystyle S_j = \sum_{n\in A} n^j.$

Determine all values of ${j}$ such that ${S(j)}$ is a multiple of ${2021}$ .

A6. Let ${P(x)}$ be a polynomial whose coefficients are all either ${0}$ or ${1}$ . Suppose that ${P(x)}$ can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that ${P(2)}$ is a composite integer?

Categories: Algebra, Analysis, IMO, Number theory, Olympiad, Problem Solving Tags: Analysis, olympiad, Problem Solving, putnam

IMC 2020 Online – Problems – Day 1

August 28, 2020 beni22sof Leave a comment

Problem 1. Let ${n}$ be a positive integer. Compute the number of words ${w}$ (finite sequences of letters) that satisfy all the following requirements: (1) ${w}$ consists of ${n}$ letters, all of them from the alphabet ${\{a,b,c,d\}}$ (2) ${w}$ contains an even number of letters ${a}$ (3) ${w}$ contains an even number of letters ${b}$ (For example, for ${n=2}$ there are ${6}$ such words: ${aa, bb, cc,dd,cd}$ and ${dc}$ .)

(proposed by Armend Sh. Shabani, University of Prishtina)

Problem 2. Let ${A}$ and ${B}$ be ${n\times n}$ real matrices such that

$\displaystyle \text{rank}(AB-BA+I) = 1,$

where ${I}$ is the ${n\times n}$ identity matrix. Prove that

$\displaystyle \text{tr}(ABAB)-\text{tr}(A^2B^2) = \frac{1}{2}n(n-1).$

(proposed by Rustam Turdibaev, V.I. Romanovskiy Institute of Mathematics)

Problem 3. Let ${d \geq 2}$ be an integer. Prove that there exists a constant ${C(d)}$ such that the following holds: For any convex polytope ${K\subset \Bbb{R}^d}$ , which is symmetric about the origin, and any ${\varepsilon \in (0,1)}$ , there exists a convex polytope ${L \subset \Bbb{R}^d}$ with at most ${C(d) \varepsilon^{1-d}}$ vertices such that

$\displaystyle (1-\varepsilon)K \subseteq L \subset K.$

(For a real ${\alpha}$ , a set ${T\subset \Bbb{R}^d}$ with nonempty interior is a convex polytope with at most ${\alpha}$ vertices if ${T}$ is a convex hull of a set ${X \subset \Bbb{R}^d}$ of at most ${\alpha}$ points.)

(proposed by Fedor Petrov, St. Petersburg State University)

Problem 4. A polynomial ${p}$ with real coefficients satisfies the equation ${p(x+1)-p(x) = x^{100}}$ for all ${x \in \Bbb{R}}$ . Prove that ${p(1-t)\geq p(t)}$ for ${0\leq t\leq 1/2}$ .

(proposed by Daniil Klyuev, St. Petersburg State University)

source: http://www.imc-math.org

Categories: Affine Geometry, Algebra, Combinatorics, Higher Algebra, IMO, Problem Solving Tags: IMC, olympiad, Problem Solving

IMC 2019 – Solutions to some problems from Day 1

July 31, 2019 beni22sof Leave a comment

Problem 1. Evaluate the product

$\displaystyle \prod_{n=3}^\infty \frac{(n^3+3n)^2}{n^6-64}.$

Solution: When dealing with this kind of questions there aren’t that many options. Either use a known product, or find a telescopic argument, i.e. show that all but finitely many terms simplify.

The telescopic argument is the most likely to work. Indeed, we have the following

$\displaystyle \frac{(n^3+3n)^2}{n^6-64} = \frac{n^2(n^2+3)^2}{(n-2)(n^2+2n+4)(n+2)(n^2-2n+4)}$

which is a product of two telescopic expressions:

$\displaystyle \frac{n^2}{(n-2)(n+2)}$

and

$\displaystyle \frac{(n^2+3)^2}{((n+1)^2+3)((n-1)^2+3)}.$

I leave to you the pleasure of finding which of the terms remain after all simplifications.

Problem 2. A four-digit ${YEAR}$ is called very good if the system

$\displaystyle \left\{\begin{array}{rcl} Yx+Ey+Az+Rw & = & Y \\ Rx+Yy+Ez+Aw & = & E \\ Ax+Ry+Yz+Ew & = & A \\ Ex+Ay+Rz+Yw & = & R \end{array} \right.$

of linear equations in the variables ${x,y,z,w}$ has at least two solutions. Find all very good ${YEAR}$ s in the ${21}$ st century (between ${2001}$ and ${2100}$ ). Solution: Well, this is not too complicated in the first part. The fact that the system has at least two solutions implies that the square matrix of the system is singular, i.e. the determinant of

$\displaystyle \begin{pmatrix} Y&E&A&R \\ R&Y&E&A \\ A&R&Y&E \\ E&A&R&Y \end{pmatrix}$

is zero. Now, it is not difficult to note that the determinant can be factorized as follows:

$\displaystyle (Y+E+A+R)(Y-E+A-R)((Y-A)^2+(R-E)^2).$

The first two factors may be obtained by adding all lines to the first one, for example, factoring out ${Y+E+A+R}$ and obtaining a line of ones. Then we do the classical trick of creating zeros in all positions except one on the first line by subtracting the first column from everything else. This reduces the dimension of the matrix. The second factor may be obtained with a similar trick, while the third comes directly by computing the determinant of a ${2\times 2}$ matrix. The rest of the exercise (the most difficult part, for me 🙂 ) is just casework.

Problem 3. Let ${f : (-1,1) \rightarrow \Bbb{R}}$ be a twice differentiable function such that

$\displaystyle 2f'(x)+xf''(x)\geq 1 \text{ for } x \in (-1,1).$

Prove that

$\displaystyle \int_{-1}^1 xf(x) dx \geq \frac{1}{3}.$

Solution: The first question here is what is the connection between the hypothesis and the conclusion? We have some derivatives in the hypothesis. It would be more useful if we could write them as a single derivative. In order to do this note that ${(xf'(x))' = f'(x)+xf''(x)}$ and there is a ${f'}$ missing to have the complete expression. Therefore

$\displaystyle 2f'(x)+xf''(x) = (f(x)+xf'(x))'.$

Now, surprisingly, we find that the function ${f(x)+xf'(x)}$ is connected to ${xf(x)}$ in a natural way: ${(xf(x))' = f(x)+xf'(x)}$ . This means that the hypothesis simply says that the second derivative of ${xf(x)}$ is greater or equal than ${1}$ . Integrating this a few times is enough to obtain the desired inequality. A nice observation is the following: note that the hypothesis contains only derivatives of ${f}$ . Therefore, if we replace ${f}$ by ${f+c}$ where ${c}$ is a constant, the conclusion should not change. And indeed, it doesn’t, since ${\int_{-1}^1 cx = 0}$ . You may need this information at some point in order to simplify the computations.

Problem 5. Determine whether there exist an odd positive integer ${n}$ and ${n \times n}$ matrices ${A}$ and ${B}$ with integer entries that satisfy the following conditions:

${\det B = 1}$ .
${AB = BA}$ .
${A^4+4A^2B^2+16B^4 = 2019 I}$

As usual ${I}$ denotes the ${n\times n}$ identity matrix.

Solution: This problem is an example of an overkill. Having that many hypotheses makes you think that the solution is complicated. In fact, the last relation suffices, when looking at remainders modulo ${4}$ .

$\displaystyle A^4+4A^2B^2+16B^4 \equiv A^4 \mod{4}$

Passing to determinants we find that

$\displaystyle 2019^n \equiv \det(A)^4 \mod 4$

which means that ${2019^n}$ should be a quadratic residue modulo ${4}$ . However, since ${n}$ is odd, we find that ${2019^n \equiv 3^n \equiv 3 \mod 4}$ , which is not a quadratic residue. Therefore no such matrices exist for odd ${n}$ .

Categories: Algebra, Number theory, Olympiad, Problem Solving Tags: Algebra, Analysis, IMC, olympiad

IMC 2019 – Problems from Day 1

July 30, 2019 beni22sof Leave a comment

Problem 1. Evaluate the product

$\displaystyle \prod_{n=3}^\infty \frac{(n^3+3n)^2}{n^6-64}.$

Problem 2. A four-digit ${YEAR}$ is called very good if the system

$\displaystyle \left\{\begin{array}{rcl} Yx+Ey+Az+Rw & = & Y \\ Rx+Yy+Ez+Aw & = & E \\ Ax+Ry+Yz+Ew & = & A \\ Ex+Ay+Rz+Yw & = & R \end{array} \right.$

of linear equations in the variables ${x,y,z,w}$ has at least two solutions. Find all very good ${YEAR}$ s in the ${21}$ st century (between ${2001}$ and ${2100}$ ).

Problem 3. Let ${f : (-1,1) \rightarrow \Bbb{R}}$ be a twice differentiable function such that

$\displaystyle 2f'(x)+xf''(x)\geq 1 \text{ for } x \in (-1,1).$

Prove that

$\displaystyle \int_{-1}^1 xf(x) dx \geq \frac{1}{3}.$

Problem 4. Define the sequence ${a_0,a_1,...}$ of numbers by the following recurrence:

$\displaystyle a_0 = 1, \ \ a_1 = 2, \ \ (n+3)a_{n+2} = (6n+9)a_{n+1}-na_n \text{ for } n \geq 0.$

Prove that all terms of this sequence are integers.

Problem 5. Determine whether there exist an odd positive integer ${n}$ and ${n \times n}$ matrices ${A}$ and ${B}$ with integer entries that satisfy the following conditions:

${\det B = 1}$ .
${AB = BA}$ .
${A^4+4A^2B^2+16B^4 = 2019 I}$

As usual ${I}$ denotes the ${n\times n}$ identity matrix.

Source: imc-math.org.uk

Categories: Algebra, Analysis, Higher Algebra, IMO, Linear Algebra, Number theory, Olympiad, Problem Solving Tags: Algebra, Analysis, IMC, olympiad, Problem Solving

IMO 2019 Problem 1

July 18, 2019 beni22sof 7 comments

Problem 1. Let ${\Bbb{Z}}$ be the set of integers. Determine all functions ${f:\Bbb Z \rightarrow \Bbb Z}$ such that, for all integers ${a}$ and ${b}$ ,

$\displaystyle f(2a)+2f(b) = f(f(a+b)).$

Solution: As usual with this kind of functional equations the first thing that comes into mind is to pick simple cases of ${a}$ and ${b}$ .

Categories: Algebra, IMO, Olympiad Tags: functional equation, IMO, olympiad

Putnam 2018 – Problem B4

February 8, 2019 beni22sof Leave a comment

B4. Given a real number ${a}$ , we define a sequence by ${x_0=1}$ , ${x_1=x_2=a}$ and ${x_{n+1} = 2x_nx_{n-1}-x_{n-2}}$ for ${n \geq 2}$ . Prove that if ${x_n =0 }$ for some ${n}$ , then the sequence is periodic.

Putnam 2018, Problem B4

Solution: The path to the solution for this problem is really interesting. The first question that pops in mind when seeing the problem is: How do I prove that a sequence is periodic?. It’s not obvious from the given recurrence relation that this should happen, and what’s with the condition ${x_n = 0}$ ?

Categories: Algebra, Analysis, Olympiad, Problem Solving Tags: olympiad, periodic, putnam, sequence, trigonometry

Putnam 2018 – Problem B2

February 7, 2019 beni22sof Leave a comment

B2. Let ${n}$ be a positive integer and let ${f_n(z) = n+(n-1)z+(n-2)z^2+...+z^{n-1}}$ . Prove that ${f_n}$ has no roots in the closed unit disk ${\{z \in \Bbb{C}: |z| \leq 1\}}$ .

Putnam 2018, Problem B2

Solution: This is a cute problem and the path to the solution is quite straightforward once you notice some obvious things. First note that ${f_n(0)=n}$ , so ${0}$ is not a solution.

IMO 2018 Problems – Day 1

July 9, 2018 beni22sof Leave a comment

Problem 1. Let ${\Gamma}$ be the circumcircle of acute triangle ${ABC}$ . Points ${D}$ and ${E}$ are on segments ${AB}$ and ${AC}$ respectively such that ${AD = AE}$ . The perpendicular bisectors of ${BD}$ and ${CE}$ intersect minor arcs ${AB}$ and ${AC}$ of ${\Gamma}$ at points ${F}$ and ${G}$ respectively. Prove that lines ${DE}$ and ${FG}$ are either parallel or they are the same line.

Problem 2. Find all integers ${n \geq 3}$ for which there exist real numbers ${a_1, a_2, \dots a_{n + 2}}$ satisfying ${a_{n + 1} = a_1}$ , ${a_{n + 2} = a_2}$ and

$\displaystyle a_ia_{i + 1} + 1 = a_{i + 2}$

For ${i = 1, 2, \dots, n}$ .

Problem 3. An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following is an anti-Pascal triangle with four rows which contains every integer from ${1}$ to ${10}$

$\displaystyle 4$

$\displaystyle 2\quad 6$

$\displaystyle 5\quad 7 \quad 1$

$\displaystyle 8\quad 3 \quad 10 \quad 9$

Does there exist an anti-Pascal triangle with ${2018}$ rows which contains every integer from ${1}$ to ${1 + 2 + 3 + \dots + 2018}$ ?

Source: AoPS.

Categories: Geometry, IMO, Olympiad, Uncategorized Tags: Geometry, IMO, olympiad, Problem Solving

Balkan Mathematical Olympiad 2018

June 23, 2018 beni22sof Leave a comment

Problem 1. A quadrilateral ${ABCD}$ is inscribed in a circle ${k}$ , where ${AB>CD}$ and ${AB}$ is not parallel to ${CD}$ . Point ${M}$ is the intersection of the diagonals ${AC}$ and ${BD}$ and the perpendicular from ${M}$ to ${AB}$ intersects the segment ${AB}$ at the point ${E}$ . If ${EM}$ bisects the angle ${CED}$ , prove that ${AB}$ is a diameter of the circle ${k}$ .

Problem 2. Let ${q}$ be a positive rational number. Two ants are initially at the same point ${X}$ in the plane. In the ${n}$ -th minute ${(n=1,2,...)}$ each of them chooses whether to walk due north, east, south or west and then walks the distance of ${q^n}$ meters. After a whole number of minutes, they are at the same point in the plane (non necessarily ${X}$ ), but have not taken exactly the same route within that time. Determine all the possible values of ${q}$ .

Problem 3. Alice and Bob play the following game: They start with two non-empty piles of coins. Taking turns, with Alice playing first, each player chooses a pile with an even number of coins and moves half of the coins of this pile to the other pile. The came ends if a player cannot move, in which case the other player wins.

Determine all pairs ${(a,b)}$ of positive integers such that if initially the two piles have ${a}$ and ${b}$ coins, respectively, then Bob has a winning strategy.

Problem 4. Find all primes ${p}$ and ${q}$ such that ${3p^{q-1}+1}$ divides ${11^q+17^p}$ .

Source: https://bmo2018.dms.rs/wp-content/uploads/2018/05/BMOproblems2018_English.pdf

Categories: Algebra, Combinatorics, Geometry, IMO, Number theory, Olympiad Tags: BMO, Geometry, olympiad, Problem Solving

Romanian Masters in Mathematics contest – 2018

March 9, 2018 beni22sof Leave a comment

Problem 1. Let ${ABCD}$ be a cyclic quadrilateral an let ${P}$ be a point on the side ${AB.}$ The diagonals ${AC}$ meets the segments ${DP}$ at ${Q.}$ The line through ${P}$ parallel to ${CD}$ mmets the extension of the side ${CB}$ beyond ${B}$ at ${K.}$ The line through ${Q}$ parallel to ${BD}$ meets the extension of the side ${CB}$ beyond ${B}$ at ${L.}$ Prove that the circumcircles of the triangles ${BKP}$ and ${CLQ}$ are tangent .

Problem 2. Determine whether there exist non-constant polynomials ${P(x)}$ and ${Q(x)}$ with real coefficients satisfying

$\displaystyle P(x)^{10}+P(x)^9 = Q(x)^{21}+Q(x)^{20}.$

Problem 3. Ann and Bob play a game on the edges of an infinite square grid, playing in turns. Ann plays the first move. A move consists of orienting any edge that has not yet been given an orientation. Bob wins if at any point a cycle has been created. Does Bob have a winning strategy?

Problem 4. Let ${a,b,c,d}$ be positive integers such that ${ad \neq bc}$ and ${gcd(a,b,c,d)=1}$ . Let ${S}$ be the set of values attained by ${\gcd(an+b,cn+d)}$ as ${n}$ runs through the positive integers. Show that ${S}$ is the set of all positive divisors of some positive integer.

Problem 5. Let ${n}$ be positive integer and fix ${2n}$ distinct points on a circle. Determine the number of ways to connect the points with ${n}$ arrows (oriented line segments) such that all of the following conditions hold:

each of the ${2n}$ points is a startpoint or endpoint of an arrow;
no two arrows intersect;
there are no two arrows ${\overrightarrow{AB}}$ and ${\overrightarrow{CD}}$ such that ${A}$ , ${B}$ , ${C}$ and ${D}$ appear in clockwise order around the circle (not necessarily consecutively).

Problem 6. Fix a circle ${\Gamma}$ , a line ${\ell}$ to tangent ${\Gamma}$ , and another circle ${\Omega}$ disjoint from ${\ell}$ such that ${\Gamma}$ and ${\Omega}$ lie on opposite sides of ${\ell}$ . The tangents to ${\Gamma}$ from a variable point ${X}$ on ${\Omega}$ meet ${\ell}$ at ${Y}$ and ${Z}$ . Prove that, as ${X}$ varies over ${\Omega}$ , the circumcircle of ${XYZ}$ is tangent to two fixed circles.

Source: Art of Problem Solving forums

Some quick ideas: For Problem 1 just consider the intersection of the circle ${(BKP)}$ with the circle ${(ABCD)}$ . You’ll notice immediately that this point belongs to the circle ${(CLQ)}$ . Furthermore, there is a common tangent to the two circles at this point.

For Problem 2 we have ${10\deg P = 21 \deg Q}$ . Eliminate the highest order term from both sides and look at the next one to get a contradiction.

Problem 4 becomes easy after noticing that if ${q}$ divides ${an+b}$ and ${cn+d}$ then ${q}$ divides ${ad-bc}$ .

In Problem 5 try to prove that the choice of start points determines that of the endpoints. Then you have a simple combinatorial proof.

Problem 6 is interesting and official solutions use inversions. Those are quite nice, but it may be worthwhile to understand what happens in the non-inverted configuration.

I will come back to some of these problems in some future posts.

Categories: Combinatorics, Geometry, IMO, Number theory, Olympiad Tags: Geometry, number theory, olympiad, Problem Solving, RMM

SEEMOUS 2018 – Problems

March 1, 2018 beni22sof Leave a comment

Problem 1. Let ${f:[0,1] \rightarrow (0,1)}$ be a Riemann integrable function. Show that

$\displaystyle \frac{\displaystyle 2\int_0^1 xf^2(x) dx }{\displaystyle \int_0^1 (f^2(x)+1)dx }< \frac{\displaystyle \int_0^1 f^2(x) dx}{\displaystyle \int_0^1 f(x)dx}.$

Problem 2. Let ${m,n,p,q \geq 1}$ and let the matrices ${A \in \mathcal M_{m,n}(\Bbb{R})}$ , ${B \in \mathcal M_{n,p}(\Bbb{R})}$ , ${C \in \mathcal M_{p,q}(\Bbb{R})}$ , ${D \in \mathcal M_{q,m}(\Bbb{R})}$ be such that

$\displaystyle A^t = BCD,\ B^t = CDA,\ C^t = DAB,\ D^t = ABC.$

Prove that ${(ABCD)^2 = ABCD}$ .

Problem 3. Let ${A,B \in \mathcal M_{2018}(\Bbb{R})}$ such that ${AB = BA}$ and ${A^{2018} = B^{2018} = I}$ , where ${I}$ is the identity matrix. Prove that if ${\text{tr}(AB) = 2018}$ then ${\text{tr}(A) = \text{tr}(B)}$ .

Problem 4. (a) Let ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a polynomial function. Prove that

$\displaystyle \int_0^\infty e^{-x} f(x) dx = f(0)+f'(0)+f''(0)+...$

(b) Let ${f}$ be a function which has a Taylor series expansion at ${0}$ with radius of convergence ${R=\infty}$ . Prove that if $\sum_{n=0}^\infty f^{(n)}(0)$ converges absolutely then $\int_0^{\infty} e^{-x} f(x)dx$ converges and

$\displaystyle \sum_{n=0}^\infty f^{(n)}(0) = \int_0^\infty e^{-x} f(x).$

Source: official site of SEEMOUS 2018

Hints: 1. Just use $2f(x) \leq f^2(x)+1$ and $xf^2(x) < f^2(x)$ . The strict inequality comes from the fact that the Riemann integral of strictly positive function cannot be equal to zero. This problem was too simple…

2. Use the fact that $ABCD = AA^t$ , therefore $ABCD$ is symmetric and positive definite. Next, notice that $(ABCD)^3 = ABCDABCDABCD = D^tC^tB^tA^t = (ABCD)^t = ABCD$ . Notice that $ABCD$ is diagonalizable and has eigenvalues among $-1,0,1$ . Since it is also positive definite, $-1$ cannot be an eigenvalue. This allows to conclude.

3. First note that the commutativity allows us to diagonalize $A,B$ using the same basis. Next, note that $A,B$ both have eigenvalues of modulus one. Then the trace of $AB$ is simply the sum $\sum \lambda_i\mu_i$ where $\lambda_i,\mu_i$ are eigenvalues of $A$ and $B$ , respectively. The fact that the trace equals $2018$ and the triangle inequality shows that eigenvalues of $A$ are a multiple of eigenvalues of $B$ . Finish by observing that they have the same eigenvalues.

4. (a) Integrate by parts and use a recurrence. (b) Use (a) and the approximation of a continuous function by polynomials on compacts to conclude.

I’m not sure about what others think, but the problems of this year seemed a bit too straightforward.

Categories: Algebra, Analysis, Higher Algebra, Inequalities Tags: 2018, olympiad, Problem Solving, SEEMOUS

Putnam 2017 A2 – Solution

December 4, 2017 beni22sof Leave a comment

Problem A2. We have the following recurrence relation

$\displaystyle Q_n = \frac{Q_{n-1}^2-1}{Q_{n-2}},$

for ${n \geq 2}$ , given ${Q_0=1}$ and ${Q_1=x}$ . In order to prove that ${Q_n}$ is always a polynomial with integer coefficients we should prove that ${Q_{n-2}}$ divides ${Q_{n-1}^2-1}$ somehow. Recurrence does not seem to work very well. Also, root based arguments might work, but you need to take good care in the computation.

A simpler idea, which is classic in this context, is to try and linearize the recurrence relation. In order to do this, let’s write two consecutive recurrence relations

$\displaystyle Q_nQ_{n-2} +1 = Q_{n-1}^2$

$\displaystyle Q_n^2 = Q_{n+1}Q_{n-1}+1$

We add them and we obtain the following relation

$\displaystyle \frac{Q_n}{Q_{n-1}} = \frac{Q_{n+1}+Q_{n-1}}{Q_n+Q_{n-2}},$

which leads straightforward to a telescoping argument. Finally, we are left with a simple linear recurrence with integer coefficient polynomials, and the result follows immediately.

Categories: Algebra, Olympiad, Uncategorized Tags: olympiad, polynomials, putnam

IMC 2017 – Day 2 – Problems

August 3, 2017 beni22sof 1 comment

Problem 6. Let ${f: [0,\infty) \rightarrow \Bbb{R}}$ be a continuous function such that ${\lim_{x \rightarrow \infty}f(x) = L}$ exists (finite or infinite).

Prove that

$\displaystyle \lim_{n \rightarrow \infty} \int_0^1 f(nx) dx = L.$

Problem 7. Let ${p(x)}$ be a nonconstant polynomial with real coefficients. For every positive integer ${n}$ let

$\displaystyle q_n(x) = (x+1)^n p(x)+x^n p(x+1).$

Prove that there are only finitely many numbers ${n}$ such that all roots of ${q_n(x)}$ are real.

Problem 8. Define the sequence ${A_1,A_2,...}$ of matrices by the following recurrence

$\displaystyle A_1 = \begin{pmatrix} 0& 1 \\ 1& 0 \end{pmatrix}, \ A_{n+1} = \begin{pmatrix} A_n & I_{2^n} \\ I_{2^n} & A_n \end{pmatrix} \ \ (n=1,2,...)$

where ${I_m}$ is the ${m\times m}$ identity matrix.

Prove that ${A_n}$ has ${n+1}$ distinct integer eigenvalues ${\lambda_0<\lambda_1<...<\lambda_n}$ with multiplicities ${{n \choose 0},\ {n\choose 1},...,{n \choose n}}$ , respectively.

Problem 9. Define the sequence ${f_1,f_2,... : [0,1) \rightarrow \Bbb{R}}$ of continuously differentiable functions by the following recurrence

$\displaystyle f_1 = 1; f'_{n+1} = f_nf_{n+1} \text{ on } (0,1) \text{ and } f_{n+1}(0)=1.$

Show that ${\lim_{n\rightarrow \infty}f_n(x)}$ exists for every ${x \in [0,1)}$ and determine the limit function.

Problem 10. Let ${K}$ be an equilateral triangle in the plane. Prove that for every ${p>0}$ there exists an ${\varepsilon >0}$ with the following property: If ${n}$ is a positive integer and ${T_1,...,T_n}$ are non-overlapping triangles inside ${K}$ such that each of them is homothetic to ${K}$ with a negative ratio and

$\displaystyle \sum_{\ell =1}^n \text{area}(T_\ell) > \text{area} (K)-\varepsilon,$

then

$\displaystyle \sum_{\ell =1}^n \text{perimeter} (T_\ell) > p.$

Categories: Olympiad, Problem Solving, Uncategorized Tags: IMC, olympiad

Balkan Mathematical Olympiad 2017 – Problems

May 10, 2017 beni22sof Leave a comment

Problem 1. Find all ordered pairs of positive integers ${ (x, y)}$ such that:

$\displaystyle x^3+y^3=x^2+42xy+y^2.$

Problem 2. Consider an acute-angled triangle ${ABC}$ with ${AB<AC}$ and let ${\omega}$ be its circumscribed circle. Let ${t_B}$ and ${t_C}$ be the tangents to the circle ${\omega}$ at points ${B}$ and ${C}$ , respectively, and let ${L}$ be their intersection. The straight line passing through the point ${B}$ and parallel to ${AC}$ intersects ${t_C}$ in point ${D}$ . The straight line passing through the point ${C}$ and parallel to ${AB}$ intersects ${t_B}$ in point ${E}$ . The circumcircle of the triangle ${BDC}$ intersects ${AC}$ in ${T}$ , where ${T}$ is located between ${A}$ and ${C}$ . The circumcircle of the triangle ${BEC}$ intersects the line ${AB}$ (or its extension) in ${S}$ , where ${B}$ is located between ${S}$ and ${A}$ .

Prove that ${ST}$ , ${AL}$ , and ${BC}$ are concurrent.

Problem 3. Let ${\mathbb{N}}$ denote the set of positive integers. Find all functions ${f:\mathbb{N}\longrightarrow\mathbb{N}}$ such that

$\displaystyle n+f(m)\mid f(n)+nf(m)$

for all ${m,n\in \mathbb{N}}$

Problem 4. On a circular table sit ${n> 2}$ students. First, each student has just one candy. At each step, each student chooses one of the following actions:

(A) Gives a candy to the student sitting on his left or to the student sitting on his right.
(B) Separates all its candies in two, possibly empty, sets and gives one set to the student sitting on his left and the other to the student sitting on his right.

At each step, students perform the actions they have chosen at the same time. A distribution of candy is called legitimate if it can occur after a finite number of steps. Find the number of legitimate distributions.

(Two distributions are different if there is a student who has a different number of candy in each of these distributions.)

Source: AoPS

Categories: Algebra, Geometry, Number theory, Olympiad, Uncategorized Tags: Algebra, BMO, Geometry, number theory, olympiad

Older Entries

Beni Bogoşel's blog

Archive

An inequality involving complex numbers

Romanian Regional Olympiad 2024 – 10th grade

Geometry problem: a property of the 40-40-100 triangle

Minimal volume of some particular convex sets in the cube

IMC 2022 – Day 1 – Problem 1

Function with zero average on vertices of all regular polygons

Putnam 2021 – Day 1

IMC 2020 Online – Problems – Day 1

IMC 2019 – Solutions to some problems from Day 1

IMC 2019 – Problems from Day 1

IMO 2019 Problem 1

Putnam 2018 – Problem B4

Putnam 2018 – Problem B2

IMO 2018 Problems – Day 1

Balkan Mathematical Olympiad 2018

Romanian Masters in Mathematics contest – 2018

SEEMOUS 2018 – Problems

Putnam 2017 A2 – Solution

IMC 2017 – Day 2 – Problems

Balkan Mathematical Olympiad 2017 – Problems

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

Archive

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll