IMC 2022 – Day 1 – Problem 2

Problem 2. Let be a positive integer. Find all real matrices having only real eigenvalues satisfying

for some integer . 

IMC 2022 – Day 1 – Problem 1

Problem 1. Let be an integrable function such that for all . Prove that

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 . Let be a function such that for any regular -gon we have

Prove that 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 . It is possible to produce another two equilateral triangles and such that , are equilateral. Note that we kept a common vertex and we rotated the initial triangle by and . Applying the result for all the small triangles and summing we obtain

where the missing terms are again sums of values of on some equilateral triangles. It follows that .

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 at the center needs to be equal to zero, summing the values of the function on the vertices of all small squares.

In the general case, the idea is the same. Consider an initial polygon and rotate it around with angles , . Then sum all the values of the function on the vertices of these regular polygons. Observe that the vertex is repeated times while all other vertices are part of some regular polygon. In the end we get

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 , then integrate on all rotations of the circle through . On one side this integral should be equal to zero. On the other it contains the value of in and values on concentric circles in . This should imply that is zero for any point .

Hadwiger-Finsler inequality – translation of the original paper

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

.

I recently decided to take a look at the original paper: Finsler, Paul; Hadwiger, Hugo (1937). “Einige Relationen im Dreieck”. Commentarii Mathematici Helvetici. 10 (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!

Some relations in the triangle by H. Hadwiger and Paul FinslerDownload

Three circles meet again

Consider a triangle and the reflections of with respect to the opposite sides. If is the orthocenter of then prove that the circles 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 with the midpoints of the triangle and becomes the circumcenter of . Thus we get the following equivalent problem:

Let be a triangle with circumcenter and denote by the midpoints of the corresponding opposite sides. Then the circles 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 , construct the tangent in to the circumcenter of . This tangent meets at . It is not hard to show that is cyclic and is the diameter of . Construct 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 are colinear. But since 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 where are the side lengths and 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 . From the optimality condition, the angles at must be equal. Construct now equilateral triangles outside the triangle and note that triangles , 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!

Weitzenböck’s inequality

Given a triangle , denote by the lengths of the sides opposite to angles . Also denote by the area of the triangle. Weitzenbrock’s inequality states that the following holds:

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 where is the circumradius. Moreover, is related to by . Thus

Therefore the original inequality is equivalent to

One would be tempted to try the arithmetic geometric mean inequality here, but that cannot work, since the inequality is not homogeneous and are not free, they verify . However, note that the function is concave on therefore, applying Jensen’s inequality we get

As a consequence, using cyclic sums over , we get

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

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

showing that we also have

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

This leads to the stronger inequality

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

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

Construct center of an ellipse

1. Let be an ellipse and an exterior point. Draw tangents to the ellipse with . Let be the midpoint of . Then passes through the center of the ellipse.

2. Given an ellipse 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 is contained in a plane and consider a line orthogonal to . There exists a circle contained in a plane such that the orthogonal projection of onto is the ellipse . Through draw a line parallel to and denote the intersection with . Draw , the tangents from to the circle (in the plane ).

Then of course, the projection of on are given by, respectively, and . Moreover, the midpoint of projects onto the middle of . The line contains the center of which projects onto the center of . Therefore the line , being the projection of also passes through the center of .

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 on the ellipse and draw the corresponding tangents and their intersection point . If the tangents are parallel just pick another point. According to the first point, the line joining with the midpoint of is going through the center of . Repeat this process to get another line going through the center. The intersection of the two lines will give the center .

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

Given an ellipse and a point on the ellipse, construct the tangent to the ellipse at 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 are six points on a conic and joined by segments to form a hexagon, then the pairs of opposite sides 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 on the ellipse, different from . Suppose that the sixth point coincides with . Construct the point and . Moreover, we also need the point . However, since and coincide, how can one define the line ? Well, think about a point on the ellipse that is different than and which gets closer and closer to . The line converges to the tangent line to the ellipse at . Therefore is just the tangent to the ellipse at . Ok, so we have the three points from Pascal’s theorem and these should be colinear.

However, in our case, we don’t know the tangent . However, we can draw points and the line . We find , the intersection of with and by Pascal’s theorem the line is the tangent to the ellipse at .

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!

Construct a tangent to a point on ellipse using Pascal’s theorem

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

Balkan Mathematical Olympiad 2022

Problem 1. Let be an acute triangle such that with circumcircle and circumcentre . Let and be the tangents to at and respectively, which meet at . Let be the foot of the perpendicular from onto the line segment . The line through parallel to line meets at . Prove that the line passes through the midpoint of the line segment . 

Problem 2. Let and be positive integers with such that all of the following hold:

i. divides ,

ii. divides ,

iii. 2022 divides .

Prove that there is a subset of the set of positive divisors of the number such that the sum of the elements of is divisible by 2022 but not divisible by . 

Problem 3. Find all functions such that for all . 

Problem 4. Consider an grid consisting of until cells, where 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 frogs on the cells so that each of the cells can be reached by a frog in a finite number (possible zero) of hops. Find the least value of 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 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 norm (containing the norms of all the partial derivatives of all the components) of a vectorial function in terms of the norms of the symmetrized gradient and the norm of . The components of the matrix are . It should be underlined that this is not a trivial result: one obtains a bound for all the partial derivatives in terms of only 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: .
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 not containing rigid motions (functions for which ).
   

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 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 , and after each hop the grasshopper is at a point whose coordinates are both integers; thus, there are possible locations for the grasshopper after the first hop. What is the smallest number of hops needed for the grasshopper to reach the point ? 

A2. For every positive real number , let

Find . 

A3. Determine all positive integers for which the sphere

has an inscribed regular tetrahedron whose vertices have integer coordinates. 

A4. Let

Find , or show that this limit does not exist. 

A5. Let be the set of all integers such that and . For every nonnegative integer , let

Determine all values of such that is a multiple of . 

A6. Let be a polynomial whose coefficients are all either or . Suppose that can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that 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

Given , Lipschitz in the second variable, consider the ODE

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

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 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 we find that the speed of the point mass is . This shows that the kinetic energy of the mass is . The potential energy due to the gravitational force is , assuming that corresponds to zero height. Therefore, the total energy is given by

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

Find coefficients of trigonometric polynomial given samples

Suppose the values of some trigonometric polynomial

are known for a set of distinct angles , . 

Question: Recover the coefficients of the trigonometric polynomial that verify when or which best fits the values in the sense of least squares when . 

Answer: Obviously, since there are unknowns, we need at least equations, therefore we restrict ourselves to the case . The equalities produce a set of equations which has at most a solution when , provided the rank of the matrix of the system is . Define the function

This function is a sum of squares, which has zero as a lower bound. The function can be written using norms as where

A straightforward computation shows that the gradient of is

The matrix is invertible, provided all angles 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 . Therefore, one can always solve the system when and will minimize . In particular, when the minimum will be equal to zero and the coefficients of the trigonometric polynomial verifying will be found. When the best fit, in the sense of least squares, of the values 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 are the projections of the center of gravity of the triangle on its sides. Prove that

where as usual .

Harmonic series avoiding a digit

The harmonic series is divergent. Show that removing all terms in the previous series where the denominator contains the digit leaves us with a convergent series.

Proof: The key idea here is to count how many numbers are left in the interval when removing those who do not contain the digit . One can easily see that there are such numbers in the interval . Therefore in there are numbers which do not contain .

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

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

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 ? Can the same type of reasoning be applied?

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

Suppose that is the regular polygon inscribed in the unit circle with one vertex at . Consider the Dirichlet-Laplace eigenvalue problem

This problem has solutions for a sequence of eigenvalues

Denote by the eigenfunction associated to , normalized such that . The case of the first eigenvalue is particular. Since the first eigenvalue is simple, there exists a unique normalized eigenfunction such that . This implies that the function has all the symmetries of the regular polygon. Below you can see an image of the eigenfunction in the case of the regular pentagon.

Consider now the triangles given by vertices for , where . These triangles decompose into equal slices.

Furthermore, let . Then we have, by the symmetry of the eigenfunction, that .

In the following, due to the symmetry we can infer that is an even function with respect to and is odd. The fact that the gradients undergo a rotation when transferred from to we have the matrix equality

which implies that .

Up until now we have two relations between . Any supplementary independent relation would completely determine these quantities. 

Question: Can you find such a relation?

IMC 2021 Problems – Day 1

Problem 1. Let be a real matrix such that .

(a) Prove that there is a unique real matrix that satisfies the equation

(b) Express in terms of  

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

does not depend on . 

Problem 3. We say that a positive real number is good if there exists an infinite sequence such that for each the points partition the interval into segments of length at most each. Find

Problem 4. Let be a function. Suppose that for every there exists a function such that for every pair of real numbers if then .

Prove that is the pointwise limit of a sequence of continuous functions, i.e. there is a sequence of functions such that for every .