Beni Bogoşel's blog

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 2

July 31, 2019 beni22sof Leave a comment

Problem 6. Let ${f,g : \Bbb{R} \rightarrow \Bbb{R}}$ be contiouous function such that ${g}$ is differentiable. Assume that ${(f(0)-g'(0))(g'(1)-f(1))>0}$ . Show that there exists a point ${c \in (0,1)}$ such that ${f(c) = g'(c)}$ .

Problem 7. Let ${C = \{4,6,8,9,10,...\}}$ be the set of composite positive integers. For each ${n \in C}$ let ${a_n}$ be the smallest positive integer ${k}$ such that ${k!}$ is divisible by ${n}$ . Determine whether the following series converges:

$\displaystyle \sum_{n \in C} \left( \frac{a_n}{n} \right)^n.$

Problem 8. Let ${x_1,...,x_n}$ be real numbers. For any set ${I \subset \{1,2,...,n\}}$ let ${s(I) = \sum_{i \in I} x_i}$ . Assume that the function ${I \mapsto s(I)}$ takes on at least ${1.8^n}$ values where ${I}$ runs over all ${2^n}$ subset of ${\{1,2,...,n\}}$ . Prove that the number of sets ${I \subset \{1,2,...,n\}}$ for which ${s(I) = 2019}$ does not exceed ${1.7^n}$ .

Problem 9. Determine all positive integers ${n}$ for which there exist ${n \times n}$ real invertible matrices ${A}$ and ${B}$ that satisfy ${AB-BA = B^2A}$ .

Problem 10. ${2019}$ points are chosen at random, independently, and distributed uniformly in the unit disk ${\{(x,y) \in \Bbb{R}^2 : x^2+y^2 \leq 1\}}$ . Let ${C}$ be the convex hull of the chosen points. Which probability is larger: that ${C}$ is a polygon with three vertices or a polygon with four vertices?

Source: http://www.imc-math.org.uk

Categories: Algebra, Analysis, Geometry, Olympiad, Probability, Problem Solving

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

IMO 2019 – Problems

July 18, 2019 beni22sof Leave a comment

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

Problem 2. In triangle ${ABC}$ , point ${A_1}$ lies on the side ${BC}$ and point ${B_1}$ lies on side ${AC}$ . Let ${P}$ and ${Q}$ be points on segments ${AA_1}$ and ${BB_1}$ , respectively, such that ${PQ}$ is parallel to ${AB}$ . Let ${P_1}$ be a point on line ${PB_1}$ such that ${B_1}$ lies strictly between ${P}$ and ${P_1}$ and ${\angle PP_1C=\angle BAC}$ . Similarly, let ${Q_1}$ be a point on line ${QA_1}$ such that ${A_1}$ lies strictly between ${Q}$ and ${Q_1}$ and ${\angle CQ_1Q = \angle CBA}$ .

Prove that points ${P,Q,P_1}$ and ${Q_1}$ are concyclic.

Problem 3. A social network has ${2019}$ users, some pairs of whom are friends. Whenever user ${A}$ is friends with user ${B}$ , user ${B}$ is also friends with user ${A}$ . Events of the following kind may happen repeatedly, one at a time:

Three users ${A,B,C}$ such that ${A}$ is friends with both ${B}$ and ${C}$ but ${B}$ and ${C}$ are not friends change their friendship statuses such that ${B}$ and ${C}$ are now friends, but ${A}$ is no longer friends with ${B}$ and no longer friends with ${C}$ . All other friendship statuses are unchanged.

Initially, ${1010}$ users have ${1009}$ friends each and ${1009}$ users haf ${1010}$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Problem 4. Find all pairs ${(k,n)}$ of positive integers such that

$\displaystyle k! = (2^n-1)(2^n-2)(2^n-4)...(2^n-2^{n-1}).$

Problem 5. The Bank of Bath issues coins with an ${H}$ on a side and a ${T}$ on the other. Harry has ${n}$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly ${k>0}$ coins showing ${H}$ , then he turns over the ${k}$ th coin from the left; otherwise, all coins show ${T}$ and he stops. For example, if ${n=3}$ the process starting with the configuration ${THT}$ would be

$\displaystyle THT \rightarrow HHT \rightarrow HTT \rightarrow TTT,$

which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration ${C}$ , let ${L(C)}$ be the number of operation before Harry stops. For example ${L(THT)=3}$ and ${L(TTT)=0}$ . Determine the average value of ${L(C)}$ over all ${2^n}$ possible initial configurations ${C}$ .

Problem 6. Let ${I}$ be the incenter of the acute triangle ${ABC}$ with ${AB \neq AC}$ . The incircle ${\omega}$ of ${ABC}$ is tangent to sides ${BC,CA}$ and ${AB}$ at ${D,E,F}$ , respectively. The line through ${D}$ perpendicular to ${EF}$ meets ${\omega}$ again at ${R}$ . The line ${AR}$ meets ${\omega}$ again at ${P}$ . THe circumcircles of triangles ${PCE}$ and ${PBF}$ meet again at ${Q}$ .

Prove that lines ${DI}$ and ${PQ}$ meet on a line through ${A}$ , perpendicular to ${AI}$ .

Source: http://www.imo-official.org

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

Computing the Shape Derivative of the Wentzell Problem

July 2, 2019 beni22sof Leave a comment

Computing shape derivatives is a nice thing to know if you do numerical shape optimization. When you want to minimize a quantity depending on a shape in a more or less direct way, you should be able to differentiate it so that gradient algorithms could be applied. Computing shape derivatives is not that easy, but below there is a method which is not that hard once you practice some simple examples. For some bibliography on the subject I present you the following:

Jean CEA, Conception optimale ou identification de formes, calcul rapide de la dérivée directionnelle de la fonction coût: this is in French, but it presents the method nicely.
Chicco-Ruiz, Morin, Pauletti, The shape derivative of the Gauss curvature. This is not an original source of the classical results, but it contains a very nice summary of the basic notions of shape derivatives.
Delfour, Zolesio, Shapes and Geometries
Henrot, Pierre, Shape Variation and Optimization
Gregoire Allaire, see his the shape optimization course on his homepage

We start directly with a complicated example, containing some complex boundary terms. The Wentzell eigenvalue problem is given by the following:

$\displaystyle \left\{\begin{array}{rcll} -\Delta u & = & 0 & \text{ in } \Omega\\ -\beta \Delta_\tau u +\frac{\partial u}{\partial n} & = & \lambda u & \text{ on } \partial \Omega \end{array}\right. \ \ \ \ \ (1)$

It is not hard to see that the associated variational formulation is given by

$\displaystyle \int_\Omega \nabla u \cdot \nabla v + \beta \int_{\partial \Omega} \nabla_\tau u \cdot \nabla_\tau v = \lambda\int_{\partial \Omega} uv \ \ \ \ \ (2)$

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

Beni Bogoşel's blog

IMC 2019 – Solutions to some problems from Day 1

IMC 2019 – Problems from Day 2

IMC 2019 – Problems from Day 1

IMO 2019 Problem 1

IMO 2019 – Problems

Computing the Shape Derivative of the Wentzell Problem

Putnam 2018 – Problem B4

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Share this:

Like this:

Beni Bogoşel

Blog Stats

Today’s Visitors

Stay connected

Blogroll