## IMC 2022 – Day 1 – Problem 2

Problem 2. Let ${n}$ be a positive integer. Find all ${n \times n}$ real matrices ${A}$ having only real eigenvalues satisfying

$\displaystyle A+A^k = A^T$

for some integer ${k \geq n}$

## IMC 2022 – Day 1 – Problem 1

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.

## Function with zero average on vertices of all regular polygons

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}$.

## Hadwiger-Finsler inequality – translation of the original paper

The Hadwiger-Finsler inequality states that if $a,b,c$ are the side lengths of a triangle and $S$ is its area then we have

$a^2+b^2+c^2 \geq (a-b)^2+(b-c)^2+(c-a)^2 + 4\sqrt{3}S$.

I recently decided to take a look at the original paper: Finsler, PaulHadwiger, Hugo (1937). “Einige Relationen im Dreieck”. Commentarii Mathematici Helvetici10 (1): 316–326. doi:10.1007/BF01214300

This motivated me to try and translate it. Below you can find the document translated into English. Since do not speak German, do not hesitate to suggest corrections and improvements!

## Three circles meet again

Consider a triangle $\Delta ABC$ and the reflections $A', B', C'$ of $A, B, C$ with respect to the opposite sides. If $H$ is the orthocenter of $ABC$ then prove that the circles $(AHA'),(BHB'),(CHC')$ have another common point.

I’m sure this problem is classical, but I found it at the following link. There, a solution using inversion is given. Here’s a different one.

Note that one can identify $A,B,C$ with the midpoints of the triangle $\Delta A'B'C'$ and $H$ becomes the circumcenter of $A'B'C'$. Thus we get the following equivalent problem:

Let $\Delta ABC$ be a triangle with circumcenter $O$ and denote by $A',B',C'$ the midpoints of the corresponding opposite sides. Then the circles $(AOA'),(BOB'),(COC')$ have another common point.

A quick drawing shows that three concurrent circles have another common point if and only if their centers are colinear. Let us try to show this. To identify a diameter of $(AOA')$, construct the tangent in $A$ to the circumcenter of $\Delta ABC$. This tangent meets $BC$ at $A_1$. It is not hard to show that $AA_1A'O$ is cyclic and $OA_1$ is the diameter of $(AOA')$. Construct $B_1,C_1$ in the same way.

Now we arrive at a different well known problem: the tangents to the circumcircle at vertices meet opposite sides at colinear points. This can be proved using Menelaus’s theorem, working out the ratios in which the tangents cut the opposite sides. Another proof can be given using Pascal’s theorem. Therefore $A_1,B_1,C_1$ are colinear. But since $OA_1,OB_1,OC_1$ are diameters of the circles that interest us, it follows at once that the centers of these circles are colinear, therefore these circles meet again.

## Weitzenböck’s inequality – graphical proof

As discussed in a previous post for any triangle we have the inequality $a^2+b^2+c^2\geq 4\sqrt{3}S$ where $a, b, c$ are the side lengths and $S$ is the area. Various proofs exist, however, there is a very beautiful visual one due to  Claudi Alsina, Roger B. Nelsen: Geometric Proofs of the Weitzenböck and Hadwiger–Finsler Inequalities. Mathematics Magazine, Vol. 81, No. 3 (Jun., 2008), pp. 216–219

Consider first the case where all angles are smaller than 120 degrees. Then construct the Fermat point (or Torricelli point) which corresponds to the minimizer of the sum $TA+TB+TC$. From the optimality condition, the angles at $T$ must be equal. Construct now equilateral triangles outside the triangle $ABC$ and note that triangles $TAB, TBC, TCA$, can all be put three times inside the corresponding equilateral triangle. Writing down everything, together with the formula for the area of an equilateral triangle gives you the result!

The quantitative form, namely the Hadwiger-Finsler inequality, can also be obtained from this construction. But more on this in some other post. For now, just take a look at the picture below and try to understand this very nice geometric proof!

Categories: Geometry, IMO, Inequalities

## Weitzenböck’s inequality

Given a triangle ${\Delta ABC}$, denote by ${a,b,c}$ the lengths of the sides opposite to angles ${A,B,C}$. Also denote by ${S}$ the area of the triangle. Weitzenbrock’s inequality states that the following holds:

$\displaystyle a^2+b^2+c^2 \geq 4\sqrt{3}S.$

There are multiple ways of proving this inequality. Perhaps one of the most straightforward ways to approach this is to use the law of sines and trigonometry. We have ${a=2R\sin A}$ where ${R}$ is the circumradius. Moreover, ${R}$ is related to ${S}$ by ${R= \frac{abc}{4S}}$. Thus

$\displaystyle S = \frac{abc}{4R} = \frac{8R^3 \sin A\sin B\sin C}{4R} = 2R^2 \sin A\sin B\sin C.$

Therefore the original inequality is equivalent to

$\displaystyle \sin^2A +\sin^2 B+\sin^2 C \geq 2\sqrt{3} \sin A \sin B\sin C.$

One would be tempted to try the arithmetic geometric mean inequality here, but that cannot work, since the inequality is not homogeneous and ${A,B,C}$ are not free, they verify ${A+B+C=\pi}$. However, note that the function ${\sin}$ is concave on ${[0,\pi]}$ therefore, applying Jensen’s inequality we get

$\displaystyle \sin A+\sin B+\sin C \leq 3\frac{\sqrt{3}}{2}.$

As a consequence, using cyclic sums over ${A,B,C}$, we get

$\displaystyle \frac{3\sqrt{3}}{2} \sum \sin^2 A \geq \sum \sin^2 A \sum \sin A\geq 9 \sin A\sin B\sin C,$

where for the last inequality above we applied AM-GM inequality two times. Regrouping we obtain exactly

$\displaystyle \sin^2A +\sin^2 B+\sin^2 C \geq 2\sqrt{3} \sin A \sin B\sin C,$

which is equivalent to the original inequality. Note that with the same ideas we have

$\displaystyle \frac{3\sqrt{3}}{2} \sum \sin A\sin B \geq \sum \sin A\sin B \sum \sin A\geq 9 \sin A\sin B\sin C,$

showing that we also have

$\displaystyle \sin A\sin B+\sin B\sin C+\sin C\sin A \geq 2\sqrt{3} \sin A \sin B\sin C.$

Observe that the equality can hold only if the triangle is equilateral.

This leads to the stronger inequality

$\displaystyle ab+bc+ca\geq 4\sqrt{3}S.$

Other proofs can be found in the Wikipedia article.

It can be observed that combining the above inequalities we can get the isoperimetric inequality for triangles

$(a+b+c)^2 \geq 12\sqrt{3}S,$

where the equality holds if and only if the triangle is equilateral.

Categories: Algebra, Geometry, IMO, Inequalities

## Construct center of an ellipse

1. Let ${\mathcal E}$ be an ellipse and ${T}$ an exterior point. Draw tangents ${TA, TB}$ to the ellipse with ${A,B \in \mathcal E}$. Let ${M}$ be the midpoint of ${AB}$. Then ${TM}$ passes through the center of the ellipse.

2. Given an ellipse ${\mathcal E}$ construct its center.

Solution: There are many properties of ellipses that resemble the analogue one for the circle. This is especially true for facts involving colinearities, concurrent lines and ratios. The deeper reason for this comes from the fact that any ellipse is the projection of some circle. Conversely, for any given ellipse, there is a plane such that its projection is a circle. For example, just think of a right cylinder whose section with a plane is an ellipse. Since projection preserves colinearity, ratios and concurrent lines it is obvious that properties holding for circles should also hold for ellipses.

With this in mind, the solution to the first point above becomes obvious. Suppose ${\mathcal E}$ is contained in a plane ${\alpha}$ and consider ${d}$ a line orthogonal to ${\alpha}$. There exists a circle ${C}$ contained in a plane ${\beta}$ such that the orthogonal projection of ${C}$ onto ${\alpha}$ is the ellipse ${\mathcal E}$. Through ${T}$ draw a line parallel to ${d}$ and denote ${S}$ the intersection with ${\beta}$. Draw ${SA'}$, ${SB'}$ the tangents from ${S}$ to the circle ${C}$ (in the plane ${\beta}$).

Then of course, the projection of ${SA',SB'}$ on ${\alpha}$ are given by, respectively, ${TA}$ and ${TB}$. Moreover, the midpoint ${M'}$ of ${A'B'}$ projects onto the middle of ${AB}$. The line ${SM'}$ contains the center of ${C}$ which projects onto the center of ${\mathcal E}$. Therefore the line ${TM}$, being the projection of ${SM'}$ also passes through the center of ${\mathcal E}$.

The reasoning above can be made shorter using affine transformations. These transformations preserve colinearities and ratios. Moreover, there exist affine mappings which map an ellipse onto a disk. However, the solution involving the projection is maybe more intuitive.

For solving the second point, note that according to a previous post, it is possible to construct the tangent to a point on the ellipse using only a ruler. This is a consequence of Pascal’s theorem. Therefore, pick two points ${A,B}$ on the ellipse ${\mathcal E}$ and draw the corresponding tangents and their intersection point ${T}$. If the tangents are parallel just pick another point. According to the first point, the line joining ${T}$ with the midpoint of ${AB}$ is going through the center of ${\mathcal E}$. Repeat this process to get another line going through the center. The intersection of the two lines will give the center ${C}$.

Categories: Geometry, Problem Solving

## Draw the tangent to a point on ellipse using only a ruler

May 20, 2022 1 comment

Given an ellipse and a point ${A}$ on the ellipse, construct the tangent to the ellipse at ${A}$ using only a ruler.

Solution: It turns out that there exists such a procedure, and it is a consequence of Pascal’s theorem. The theorem says that if ${A,B,C,D,E,F}$ are six points on a conic and joined by segments to form a hexagon, then the pairs of opposite sides ${(AB,DE), (BC,EF), (CD,FA)}$ will meet at three colinear points. Moreover, the hexagon does not need to be convex. Just pick six points, put the labels on them as you want, find the intersections (parallel lines meet at infinity) and they will be on the same line.

This type of result comes from projective geometry, a branch of geometry where one considers what happens to some figure when projected on another plane. Working with points “at infinity” one can make every two lines intersect at one point (even parallel ones). Projective transformations will preserve colinearity, intersection points and will turn conics into conics. However, the goal here is not to prove Pascal’s theorem, but to use it.

Pick additional, distinct points ${B,C,D,E}$ on the ellipse, different from ${A}$. Suppose that the sixth point ${F}$ coincides with ${A}$. Construct the point ${I \in AB \cap DE}$ and ${J \in BC\cap EF=BC\cap EA}$. Moreover, we also need the point ${K \in CD \cap FA}$. However, since ${A}$ and ${F}$ coincide, how can one define the line ${AF}$? Well, think about a point ${F}$ on the ellipse that is different than ${A}$ and which gets closer and closer to ${A}$. The line ${AF}$ converges to the tangent line to the ellipse at ${A}$. Therefore ${AF}$ is just the tangent to the ellipse at ${A}$. Ok, so we have the three points ${I,J,K}$ from Pascal’s theorem and these should be colinear.

However, in our case, we don’t know the tangent ${AF}$. However, we can draw points ${I,J}$ and the line ${IJ}$. We find ${K}$, the intersection of ${CD}$ with ${IJ}$ and by Pascal’s theorem the line ${KA}$ is the tangent to the ellipse at ${A}$.

You can note that only line intersections and lines passing through two points were used, so everything can be done using only a ruler. This makes the approach “projective”: the compass is not used!

This construction is classical. It can be found in various other places on the internet, like this page.

Categories: Geometry Tags: , ,

Problem 1. Let ${ABC}$ be an acute triangle such that ${CA \neq CB}$ with circumcircle ${\omega}$ and circumcentre ${O}$. Let ${t_A}$ and ${t_B}$ be the tangents to ${\omega}$ at ${A}$ and ${B}$ respectively, which meet at ${X}$. Let ${Y}$ be the foot of the perpendicular from ${O}$ onto the line segment ${CX}$. The line through ${C}$ parallel to line ${AB}$ meets ${t_A}$ at ${Z}$. Prove that the line ${YZ}$ passes through the midpoint of the line segment ${AC}$

Problem 2. Let ${a, b}$ and ${n}$ be positive integers with ${a>b}$ such that all of the following hold:

i. ${a^{2021}}$ divides ${n}$,

ii. ${b^{2021}}$ divides ${n}$,

iii. 2022 divides ${a-b}$.

Prove that there is a subset ${T}$ of the set of positive divisors of the number ${n}$ such that the sum of the elements of ${T}$ is divisible by 2022 but not divisible by ${2022^2}$

Problem 3. Find all functions ${f: (0, \infty) \rightarrow (0, \infty)}$ such that $f(y(f(x))^3 + x) = x^3f(y) + f(x)$ for all ${x, y>0}$

Problem 4. Consider an ${n \times n}$ grid consisting of ${n^2}$ until cells, where ${n \geq 3}$ is a given odd positive integer. First, Dionysus colours each cell either red or blue. It is known that a frog can hop from one cell to another if and only if these cells have the same colour and share at least one vertex. Then, Xanthias views the colouring and next places ${k}$ frogs on the cells so that each of the ${n^2}$ cells can be reached by a frog in a finite number (possible zero) of hops. Find the least value of ${k}$ for which this is always possible regardless of the colouring chosen by Dionysus.

Source: AOPS

## Korn’s inequalities

In the study of PDEs inequalities between various types of norms are often quite useful. Take for example Poincaré’s inequality (see also this older post), which bounds the $L^2$ norm of a function using the norm of the gradient. Of course, for such an inequality to hold, the functions should be restricted to a closed subspace which does not contain the pathological counterexamples: non-zero constant functions. There are various references proving Poincaré’s inequality and the study of the best constant is well established: one can prove that the constant in the Poincaré’s inequality depends on the diameter of the set.

Recently, I needed to work on problems related to the elasticity equation on moving domains. In this context there is another well known inequality: Korn’s inequality. This inequality states that it is possible to bound the $H^1(\Omega)$ norm (containing the $L^2$ norms of all the partial derivatives of all the components) of a vectorial function $u: \Omega\to \Bbb{R}^d$ in terms of the $L^2(\Omega)$ norms of the symmetrized gradient $e(u) = \nabla u+\nabla u^T$ and the $L^2$ norm of $u$. The components of the matrix $e(u)$ are $\frac{1}{2}(\partial_{x_j}u_i+\partial_{x_i}u_j)$. It should be underlined that this is not a trivial result: one obtains a bound for all the $d^2$ partial derivatives in terms of only $d(d+1)/2$ ones in the symmetric part. The proofs of this inequality are not trivial and it turns out that the dependence of the optimal constant in the inequality in terms of the geometry of the domain is not as obvious as for Poincaré’s inequality.

Usually, there are two types of Korn inequalities:

1. The first one holds for general functions: $\|u\|_{H^1(\Omega)}\leq C(\|u \|_{L^2(\Omega)}+\|e(u)\|_{L^2(\Omega)})$.
2. The second one resembles Poincaré’s inequality even more, but it only holds in particular classes of functions, for example considering closed subspaces of $H^1$ not containing rigid motions (functions for which $e(u)=0$).
$\|\nabla u\|_{L^2(\Omega)}\leq C\|e(u)\|_{L^2(\Omega)}$

It is not my objective here to give proofs for these inequalities. I just want to provide a list of references that helped me in my research, in particular focusing on papers which explicit the dependence of the constants on the geometry of the domain.

1. Oleinik, Olga Arsenievna; Kondratiev, Vladimir Alexandrovitch (1989), On Korn’s inequalities, Comptes rendus hebdomadaires des séances de l’Académie des Sciences, Série I: Mathématiques, 308 (16): 483–487
This article describes a simple proof of Korn’s inequality with explicit constants for domains which are star-shaped with respect to a ball. The proof method is instructive, since it shows that a global bound on the symmetrized gradient together with a local bound on the gradient are enough to give a global bound on the gradient.
2. O.A. Oleinik, A.S. Shamaev, G.A. Yosifian, Mathematical Problems in Elasticity and Homogenization. This book contains a nice and concise description of Korn’s inequalities of both types. Simple and clear proofs are given. The result in the article 1. referenced above are proved in more detail, in particular the constants are explicited in terms of geometric quantities.
3. C.O. Horgan and L.E. Payne, On Inequalities of Korn, Friedrichs and Babuska-Aziz. In this nice article, a connection is made between Korn’s inequality and two other inequalities. The relation between the optimal constants is explicited and an upper bound for the optimal constant in Korn’s inequality is given for star-shaped domains in dimension two. One drawback is that Korn’s inequality is stated here in the second form, considering function having the integral of the anti-symmetric part of the gradient equal to zero. This is not the most useful type of Korn inequality (at least in what I had to do).
4. Philippe G. Ciarlet, On Korn’s Inequality, Chin. Ann. Math, 2010. Various forms of Korn’s inequality are presented, together with proofs.
5. M. Lewicka, S. Muller, On the optimal constants in Korn’s and Geometric rigidity estimates, in bounded and unbounded domains, under Neumann boundary conditions. This paper shows that the study of optimal constants in Korn’s inequality is not at all trivial. In particular, the optimal constant is not necessarily bounded by any geometric quantity for general domains.
6. R. Duran, M.A. Muschietti, The Korn inequality for Jones domains. This paper shows that Korn’s inequality holds for a wide class of domains. The proofs in the reference 2. above also shows that Korn’s inequality holds for Lipschitz domains. In this paper, even more general domains are considered.
7. S. Dominguez, Steklov eigenvalues for the Lame operator in linear elasticity. This work is not focused on Korn inequalities, however, in Theorem 2, a nice inequality of the same type as Korn’s first one is presented, where the $L^2$ norm is replaced by a continuous mapping whose kernel does not contain a non-zero rigid motion.

This is far from being an exhaustive list. However, I hope it will give you a starting point for learning (quickly) about Korn’s inequalities.

## Putnam 2021 – Day 1

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?

## Explicit Euler Method – practical aspects

In a previous post I presented the classical Euler methods and how they apply to the simple pendulum equation. Let me now be a little more explicit regarding the coding part. I will present a Python code and give you some main ideas, important from my point of view, regarding the implementation. Here is a summary of these ideas

• Use numpy in Python. When performing numerical simulations related to ODEs it is recommended to work in floating point precision. This will give you accurate enough results (at least for usual academical examples) and will produce a more efficient code.
• Structure the code using functions. The code for the Explicit Euler method should be easily adaptable to other problems, by changing the function defining the ODE (like shown in this post)
• Any numerically implemented method for solving ODEs should be tested on a simple example where the analytical solution is known. In particular, the convergence order of the method can be identified and should coincide with the theoretical prediction. This can easily help debug implementation errors for more complex methods.
• When the ODE comes from an isolated system where there is an invariant (like the energy for the pendulum), the numerical preservation of this invariant should be tested. Errors might be seen, but they should be quantifiable in terms of the step size and the order of the method. Aberrant results here could indicate the presence of a bug.

## Simple Pendulum – Euler methods

January 31, 2022 1 comment

Given ${f: \Bbb{R}\times \Bbb{R}^d \rightarrow \Bbb{R}^d}$, Lipschitz in the second variable, consider the ODE

$\displaystyle \dot y = f(t,y), y(0) = y_0 \in \Bbb{R}^d. \ \ \ \ \ (1)$

In most cases where equation (1) models some real world phenomena, the solutions are not explicit. Therefore, numerical methods are developed in order to solve such problems.

## The simple pedulum

January 30, 2022 1 comment

In physics the simple pendulum is a punctual mass fixed at the extremity of a wire without mass and in-extensible (or rigid), which oscillates under the effect of gravity. It is straightforward to see that if the point of attachment of the wire is fixed, then the resulting dynamical system can be uniquely determined knowing the inclination ${\theta}$ of the wire with the vertical and the parameters of the system (mass, length of wire, gravitational acceleration). The easiest way of deriving the equation of movement for the pendulum (supposing there is no friction) is to write the total energy of the system. The angular speed of the pendulum being ${\dot \theta}$ we find that the speed of the point mass is ${v = l\dot \theta}$. This shows that the kinetic energy of the mass is ${E_c=\frac{1}{2} m l^2\dot \theta^2}$. The potential energy due to the gravitational force is ${E_p= mgl(1-\cos \theta)}$, assuming that ${\theta=0}$ corresponds to zero height. Therefore, the total energy is given by

$\displaystyle E = E_c+E_p = \frac{1}{2} m l^2 \dot \theta^2 + mgl(1-\cos \theta).$

Supposing the system is isolated and no energy is lost due to friction we have that the derivative of the energy ${E}$ with respect to time is zero:

$\displaystyle \dot E_m =ml^2 \dot \theta \ddot \theta +mgl \sin \theta \dot \theta = 0.$

## Find coefficients of trigonometric polynomial given samples

Suppose the values ${v_i}$ of some trigonometric polynomial

$\displaystyle p(\theta) = a_0+\sum_{k=1}^N (a_k\cos(k\theta)+b_k\sin(k\theta))$

are known for a set of distinct angles ${\theta_i \in [0,2\pi]}$, ${i=1,...,M}$

Question: Recover the coefficients of the trigonometric polynomial ${p}$ that verify ${p(\theta_i) = v_i}$ when ${M = 2N+1}$ or which best fits the values ${v_i}$ in the sense of least squares when ${M>2N+1}$

Answer: Obviously, since there are ${2N+1}$ unknowns, we need at least ${2N+1}$ equations, therefore we restrict ourselves to the case ${M\geq 2N+1}$. The equalities ${p(\theta_i) = v_i}$ produce a set of ${M}$ equations which has at most a solution when ${M \geq 2N+1}$, provided the rank of the matrix of the system is ${2N+1}$. Define the function

$\displaystyle f(x) = \sum_{i=1}^{M}(a_0+\sum_{k=1}^N (a_k\cos(k\theta_i)+b_k\sin(k\theta_i)) - v_i)^2.$

This function is a sum of squares, which has zero as a lower bound. The function ${f}$ can be written using norms as ${f(x) = \|Ax-v\|^2}$ where

$\displaystyle A = \begin{pmatrix} 1 & \cos \theta_1 & ... & \cos (N\theta_1) & \sin\theta_1 & ... & \sin(N\theta_1) \\ \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 1 & \cos \theta_M & ... & \cos (N\theta_M) & \sin\theta_M & ... & \sin(N\theta_M) \end{pmatrix}, x = \begin{pmatrix} a_0\\ a_1\\ \vdots \\ a_N \\ b_1 \\ \vdots \\ b_N \end{pmatrix}, v = (v_1,...,v_M)^T$

A straightforward computation shows that the gradient of ${f}$ is

$\displaystyle \nabla f(x) = A^TAx-A^Tv.$

The ${(2N+1)\times (2N+1)}$ matrix ${A^TA}$ is invertible, provided all angles ${\theta_i,\ i=1,...,M}$ are distinct. This is a direct application of the formula of the Vandermonde determinant: using operations on columns you can recover the Vandermonde matrix corresponding to ${x_j = e^{i\theta_j}}$. Therefore, one can always solve the system ${\nabla f(x) = 0}$ when ${M\geq 2N+1}$ and ${x^* = (A^TA)^{-1}A^Tv}$ will minimize ${f}$. In particular, when ${M=2N+1}$ the minimum will be equal to zero and the coefficients of the trigonometric polynomial verifying ${p(\theta_i) = v_i}$ will be found. When ${M>2N+1}$ the best fit, in the sense of least squares, of the values ${v_i}$ with a trigonometric polynomial will be found.

Below, you can find a Python code which solves the problem in some particular case.

import numpy as np
import matplotlib.pyplot as plt

N = 5 # coeffs
M = 2*N+1 # M>=2N+1 samples

# function to be approximated
def fun(x):
return np.sin(x+np.sqrt(2))+0.3*np.sin(5*x-np.sqrt(3))+0.1*np.sin(8*x-np.sqrt(7))

thetas =np.linspace(0,2*np.pi,M,endpoint=0)
dthetas =np.linspace(0,2*np.pi,1000,endpoint=1)

# values of the function at sample points
vals = fun(thetas)

A = np.zeros((M,2*N+1))

# construct the matrix of the system
A[:,0] = 1
for i in range(0,N):
A[:,i+1] = np.cos((i+1)*thetas)
A[:,N+i+1] = np.sin((i+1)*thetas)

coeffs = np.zeros(2*N+1)

B = (A.T)@A
print(np.shape(B))

# solve the system to find the coefficients
coeffs = np.linalg.solve(B,A.T@vals)

# function computing a trigonometric polynomial
def ptrig(x,c):
res = np.zeros(np.shape(x))
res = c[0]
n = len(c)
m = (n-1)//2
for i in range(0,m):
res = res+c[i+1]*np.cos((i+1)*x)+c[i+m+1]*np.sin((i+1)*x)
return res

vals2 = ptrig(thetas,coeffs)

# plotting the result
plt.figure()
plt.plot(thetas,vals,'.b',label="Sample values")
plt.plot(dthetas,fun(dthetas),'g',label="Original function")
plt.plot(dthetas,ptrig(dthetas,coeffs),'r',label="Fitted trigonometric polynomial")
plt.legend()
plt.savefig("TrigPoly.png",dpi=100,bbox_inches='tight')
plt.show()

For the parameters chosen above the program outputs the following result. You can play with the input parameters to observe the changes.

## Some 9th grade geometry problem

Suppose $A_1,B_1,C_1$ are the projections of the center of gravity $G$ of the triangle $ABC$ on its sides. Prove that

$a^2 \overrightarrow{GA_1}+b^2 \overrightarrow{GB_1}+c^2 \overrightarrow{GC_1}=0,$

where as usual $a = BC, b=CA, c=AB$.

## Harmonic series avoiding a digit

The harmonic series $1+\frac{1}{2}+...+\frac{1}{n}+...$ is divergent. Show that removing all terms in the previous series where the denominator contains the digit $9$ leaves us with a convergent series.

Proof: The key idea here is to count how many numbers are left in the interval $[10^{m-1},10^{m}-1]$ when removing those who do not contain the digit $9$. One can easily see that there are $9^m$ such numbers in the interval $[1,10^m-1]$. Therefore in $[10^{m-1},10^{m}-1]$ there are $9^m-9^{m-1}$ numbers which do not contain $9$.

As a consequence, the sum of the inverses of numbers which do not contain $9$ is bounded by

$\frac{9}{1}+\frac{9^2-9}{10}+\frac{9^3-9^2}{10^2}+...$

It is straightforward to see that the above series is convergent. Therefore the sum of inverses of natural numbers not containing $9$ in their decimal representation is convergent. The same can be said when removing numbers that contain some other digit different from $9$.

This simple fact shows that numbers containing a particular digit are not that rare. In particular, since the sum of the inverses of the prime numbers is divergent it can be seen that there should always be arbitrarily large prime numbers containing a particular digit.

Question: What can you say about the sum of the inverses of natural numbers which do not contain a particular subsequence of digits $\overline{a_1...a_k}$? Can the same type of reasoning be applied?

## On the first eigenfunction of the Dirichlet-Laplacian on the regular polygon

Suppose that ${P_n}$ is the regular polygon inscribed in the unit circle with one vertex at ${(1,0)}$. Consider the Dirichlet-Laplace eigenvalue problem

$\displaystyle \left\{ \begin{array}{rcll} -\Delta u &= &\lambda u& \text{ in }P_n \\ u & = & 0 & \text{ on } \partial P_n \end{array}\right.$

This problem has solutions for a sequence of eigenvalues

$\displaystyle 0<\lambda_1(P_n)<\lambda_2(P_n)\leq ... \rightarrow +\infty.$

Denote by ${u_i}$ the eigenfunction associated to ${\lambda_i}$, ${i \geq 1}$ normalized such that ${\int_{P_n} u_i^2 = 1}$. The case of the first eigenvalue is particular. Since the first eigenvalue is simple, there exists a unique normalized eigenfunction such that ${u_1 \geq 0}$. This implies that the function ${u_1}$ has all the symmetries of the regular polygon. Below you can see an image of the eigenfunction ${u_1}$ in the case of the regular pentagon.

Consider now the triangles ${T_j}$ given by vertices ${(0,0),(\cos (j\theta),\sin (j\theta)),(\cos((j+1)\theta),\sin((j+1)\theta)}$ for ${j=0,..,n-1}$, where ${\theta = 2\pi/n}$. These triangles decompose ${P_n}$ into equal slices.

Furthermore, let ${A_{xx} = \int_{T_0} (\partial_x u)^2, A_{yy} = \int_{T_0} (\partial_y u)^2, A_{xy} = \int_{T_0} \partial_x u \partial_y u}$. Then we have, by the symmetry of the eigenfunction, that ${A_{xx}+A_{yy} = \lambda_1/n}$.

In the following, due to the symmetry we can infer that ${\partial_x u}$ is an even function with respect to ${y}$ and ${\partial_y u}$ is odd. The fact that the gradients undergo a rotation when transferred from ${T_{-1}}$ to ${T_0}$ we have the matrix equality

$\displaystyle \begin{pmatrix} \cos\theta& -\sin \theta \\ \sin \theta& \cos \theta \end{pmatrix}\begin{pmatrix} A_{xx} & -A_{xy} \\ -A_{xy} & A_{yy} \end{pmatrix} \begin{pmatrix} \cos\theta& \sin \theta \\ -\sin \theta& \cos \theta \end{pmatrix} = \begin{pmatrix} A_{xx} & A_{xy} \\ A_{xy} & A_{yy} \end{pmatrix}$which implies that ${-A_{xx}\sin \frac{2\pi}{n} + A_{yy} \sin \frac{2\pi}{n} + 2A_{xy} \cos \frac{2\pi}{n} = 0}$.

Up until now we have two relations between ${A_{xx},A_{yy},A_{xy}}$. Any supplementary independent relation would completely determine these quantities.

Question: Can you find such a relation?

## IMC 2021 Problems – Day 1

Problem 1. Let ${A}$ be a real ${n\times n}$ matrix such that ${A^3=0}$.

(a) Prove that there is a unique real ${n\times n}$ matrix ${X}$ that satisfies the equation

$\displaystyle X+AX+XA^2 = A.$

(b) Express ${X}$ in terms of ${A}$

Problem 2. Let ${n}$ and ${k}$ be fixed positive integers, and let ${a}$ be an arbitrary non-negative integer. Choose a random ${k}$-element subset ${X}$ of ${\{1,2,...,k+a\}}$ uniformly (i.e., all ${k}$-element subsets are chosen with the same probability) and, independently of ${X}$, choose a random ${n}$-element subset ${Y}$ of ${\{1,...,k+n+a\}}$ uniformly. Prove that the probability

$\displaystyle P(\min(Y)>\max(X))$does not depend on ${a}$

Problem 3. We say that a positive real number ${d}$ is good if there exists an infinite sequence ${a_1,a_2,... \in (0,d)}$ such that for each ${n}$ the points ${a_1,...,a_n}$ partition the interval ${[0,d]}$ into segments of length at most ${1/n}$ each. Find $\displaystyle \sup \{d | d\text{ is good} \}$

Problem 4. Let ${f: \Bbb{R}\rightarrow \Bbb{R}}$ be a function. Suppose that for every ${\varepsilon>0}$ there exists a function ${g: \Bbb{R}\rightarrow (0,\infty)}$ such that for every pair ${(x,y)}$ of real numbers if ${|x-y|<\min\{g(x),g(y)\}}$ then ${|f(x)-f(y)|<\varepsilon}$.

Prove that ${f}$ is the pointwise limit of a sequence of continuous functions, i.e. there is a sequence of functions ${h_n :\Bbb{R} \rightarrow \Bbb{R}}$ such that ${\lim_{n\rightarrow \infty} h_n(x) = f(x)}$ for every ${x \in \Bbb{R}}$.