Monday, March 29, 2021

2011 IMO Problems And Solutions

 

Problem 01

Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 +a_2 +a_3 +a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i, j)$ with $1 \leq i < j \leq 4$ for which $a_i +a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$

Solution

Firstly, if we order $a_1 \ge a_2 \ge a_3 \ge a_4$, we see $2(a_3 + a_4) \ge (a_1+a_2)+(a_3+a_4) = s_A \geq 0$, so $(a_3, a_4)$ isn't a couple that satisfies the conditions of the problem. Also, $2(a_4 + a_2) = (a_4 + a_4) + (a_2 + a_2) \ge (a_4+a_3)+(a_2+a_1) = s_A \ge 0$, so again $(a_2, a_4)$ isn't a good couple. We have in total 6 couples. So $n_A \leq 6-2=4$.

We now find all sets $A$ with $n_A = 4$. If $(a,b)$ and $(c,d)$ are both good couples, and $A=\{a, b, c, d\}$, we have $a+b=c+d=s_A/2$. So WLOG $A=\{a,b,a+x,b-x\}$ with $x > 0$ and $a < b, b-x, a+x$. It's easy to see $a=a_1$ and since $(a_2, a_4),(a_3,a_4)$ are bad, all couples containing $a$ must be good. Obviously $(a,b)$ and $(a+x,b-x)$ are good ($s_A=2(a+b)$). So we have $2a+x | 2a+2b$ and $a+b-x|2a+2b \Rightarrow a+b-x|2x$.

Using the second equation, we see that if $y=a+b$, $y-x|2x \Rightarrow yk_1-xk_1=2x \Rightarrow yk_1 = x(2+k_1) \Rightarrow y=x((2+k_1)/k_1)$, for some $k_1$ a positive integer.

So now we use the first equation to get $2ak_2 + xk_2 = 2y = 2x(2+k_1)/k_1 \Rightarrow 2ak_2 = x(\frac{4+2k_1}{k_1}-k_2) \Rightarrow 2a=x(\frac{4+2k_1}{k_1k_2} - 1)$, for a natural $k_2$.

Finally, we obtain $k_1 | 4+2k-1 \Rightarrow k_1 | 4 \Rightarrow k_1=$ 1, 2 or 4. We divide in cases:

CASE I: $k_1=1$. So $y=3x$ and $2a=x((\frac{6}{k_2}) -1)$. But $a < b-x \Rightarrow 2a < y-x=2x \Rightarrow (6/k_2) - 1 < 2 \Rightarrow k_2 > 2 \Rightarrow k_2 =$3, 4,5 or 6. $k_2=6$ implies $a=0$, impossible. $a=x$ when $k_2=3$. We easily see $b=3x=3x$ and $A=\{x, 3x, 3x-x, 2x\}$, impossible since $3x-x=2x$. When $k_2=4$, $a=x/4=y/12$, and we get $\{11a, a, 5a, 7a\}$.Uf $k_2=5$, $a=x/5=y/15$ and we get $\{a, 14a, 6a, 9a\}$.

CASE II and III:$k_1=$2, 4. Left to the reader.

ANSWER: $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$, for any positive integer $a$.

(Note: The above solution looks generally correct, but the actual answer should be $\{11a, a, 5a, 7a\}$,$\{a, 11a, 19a, 29a\}$. You can check that $\{a, 14a, 6a, 9a\}$ doesn't actually work. -Someone who didn't write up the above solution but solved the problem in a similar way)

Problem 02

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal S$. This process continues indefinitely. Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

Solution

Choose a coordinate system so that all points in $\mathcal S$ have distinct x-coordinates. Number the points $P_i=(x_i,y_i)$ of $\mathcal S$ by increasing x-coordinates: $x_1<x_2<\ldots<x_N$.

In order to divide the set $\mathcal S$ into two halves, define $n$ so that $N=2n+1+d$ where $d=0$ for an odd number of points and $d=1$ for an even number of points.

Start the "windmill" process with the line $\ell$ going vertically through the point $P_{n+1}$. Attach a down-up direction to this line so that we can color all points as follows: Points to the left of $\ell$ (with lower x-coordinates) are blue, the pivot point on $\ell$ is white and point to the right of $\ell$ (with higher x-coordinates) are red. We have now $n$ blue points, one white point and $n+d$ red points.

After processing the "windmill" by 180 degrees, the line $\ell$ goes vertically up-down. Now, points with lower x-coordinates are to the right of $\ell$ and colored red; points with higher x-coordinates are to the left of $\ell$ and colored blue.

Note that at each pivot exchange, the old pivot point enters the same side of $\ell$ where the new pivot point came from. This means that throughout the "windmill" process, the number of blue points and the number of red points stay constant, respectively: We still have $n$ blue points, one white point and $n+d$ red points. This means that the current pivot point is $P_{n+d}$.

Note that all blue and all red points changed their color from the start of the "windmill" process. This implies that every point was a pivot at some stage of the rotation.

For every 180 degrees of "windmill" rotation, the same argument applies: all colored points must change their color and hence be a pivot at some stage. Infinitely many rotations imply infinitely many color changes. This completes the proof.

Problem 03

Let $f: \mathbb R \to \mathbb R$ be a real-valued function defined on the set of real numbers that satisfies\[f(x + y) \le yf(x) + f(f(x))\]for all real numbers $x$ and $y$. Prove that $f(x) = 0$ for all $x \le 0$.

Solution

Problem 04

Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0,2^1, \cdots ,2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed. Determine the number of ways in which this can be done.

Solution

Call our answer $W(n)$. We proceed to prove $W(n)=(2n-1)!!$.

It is evident $W(1)=1$.

Now, the key observation is that smaller weights can never add up to the weight of a larger weight, ie which side is heavier is determined completely by the heaviest weight currently placed. It follows, therefore, that the number of ways to place $n$ weights on the balance according to the rule is the same no matter which $n$ distinct powers of two are the weights, as each weight completely overpowers any smaller weight and is completely overpowered by any larger weight. That is, there is the 1st heaviest weight, the 2nd heaviest, the 3rd, ..., the n-th heaviest, and each weight is negligible compared to any heavier weight. Thus, any valid placement of $n$ weights of weight $2^0,2^1, \cdots ,2^{n-1}$ can changed by replacing $2^i$ with the $(n-i)$-th heaviest weight in the set ${2^{a_k}}$, where $a_k \in \mathbb{Z}$, and vice versa, forming a $1:1$ relation. With this in mind, we use recursion upon the last weight placement. There are $2n-1$ choices; namely, you can put any weight on either side except for the heaviest weight on the right. For the first $n-1$ weight placements, the answer reduces to $W(n-1)$. We can reduce $W(n-1)$ in the same way.

$W(n)=(2n-1)W(n-1)=(2n-1)(2n-3)W(n-2)=...=(2n-1)!!W(1)=(2n-1)!!$

Problem 05

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m - n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$

Solution

We first note the following facts:

  1. $f(m)|f(0)$ for all $m \in \mathbb{Z}$: Since $f(m) |( f(m) - f(0))$.
  2. $f(m) = f(-m)$ for all $m \in \mathbb{Z}$: Since $f(m) | (f(0) - f(-m))$, we get $f(m) | f(-m)$ from above. This holds for all $m$, so $f(m) = f(-m)$ for all $m$.
  3. $f(m)|f(km)$ for all $k \in \mathbb{Z}$. Because of the the above observations, we need to show this only for $k > 0$. When $k = 1$, this is clearly true. We now use induction, along with the observation that $f(m)|(f((k+1)m) - f(km))$, so that $f(m)|f(km) \implies f(m)|f((k+1)m)$.
  4. If $f(a) | f(ax + b)$, then $f(a) | f(b)$. We have from the hypotheses that $f(ax)|(f(ax+b)-f(b))$ which implies that $f(a)|(f(ax + b) - f(b))$ and therefore $f(a) | f(b)$ (here we used the last observation).


From the first three observations, we get the following lemma:

Lemma 1: Suppose $m \neq n$, and $f(m) \leq f(n)$. If $|n-m|$ divides $n$, then $f(m) | f(n)$.

Proof: Let $d = |n-m|$. Using the second observation above, we get that\[f(n)|(f(d) - f(m)).\;\;\;\;\;\;(1)\]Now, since $d|n$, we get that $f(d) | f(n)$ (from the third observation above), and hence $f(d) \leq f(n)$. Since $f(m) \leq f(n)$ as well, and the range of $f$ is positive integers, equation (1) can hold only if $f(m) = f(d)$. But $f(d) | f(n)$, so $f(m) | f(n)$, as required.


We can now complete the proof. Notice that because of the first and second observations above, we can assume without loss of generality that $m, n > 0$. So, let $m,n$ be positive integers, and let $g = {\rm gcd (n, m)}$. We now show that if $f(m) \leq f(n)$ then $f(m)|f(g)$, and hence $f(m) | f(n)$.

By the Euclidean algorithm, there exist positive integers $x$ and $y$ such that $mx = ny + g$. Notice that $g = mx - ny$ divides both $mx$ and $ny$. We now have two cases:


Case 1: $f(mx) \leq f(ny)$. In this case, by Lemma 1, $f(mx) | f(ny)$, and hence by the third and fourth observations above, $f(m) | f(mx - g)$ which implies that $f(m) | f(g)$. This immediately implies $f(m) | f(n)$ by the third observation above, since $g | n$.

Case 2: $f(mx) > f(ny)$. In this case, by Lemma 1, $f(ny) | f(mx)$, and hence by the third and fourth observations above $f(n) | f(g)$. However, $g$ divides both $m$ and $n$, so by the third observation above, we get that $f(g)|f(n)$ and $f(g)|f(m)$. Thus, using the fact that $f(m) \leq f(n)$, we get $f(g) = f(m) = g(n)$ and hence $f(m) | f(n)$.

Problem 06

Let $ABC$ be an acute triangle with circumcircle $\Gamma$. Let $\ell$ be a tangent line to $\Gamma$, and let $\ell_a, \ell_b$ and $\ell_c$ be the lines obtained by reflecting $\ell$ in the lines $BC$, $CA$ and $AB$, respectively. Show that the circumcircle of the triangle determined by the lines $\ell_a, \ell_b$ and $\ell_c$ is tangent to the circle $\Gamma$.

Solution

Without loss of generality, let $\Gamma$ be the unit circle and let $\ell$ be the line $y=1$.

Denote the coordinates of $A,B,C$ by $(x_a, y_a)$ and similarly for B and C.

We get $x_a^2+y_a^2=1$, ...

The equation for line $AB$ is $\frac{x-x_a}{y-y_a}=\frac{x-x_b}{y-y_b}$

Through a little bash, (0,1) reflects to $(\frac{(-x_a+x_b+x_by_a)(y_b-_a)}{(x_a-x_b)^2+(y_a-y_b)^2}, \frac{(x_by_a-x_ay_b)(x_a-x_b)+(y_a-y_b)^2}{(x_a-x_b)^2+(y_a-y_b)^2}$. $(x_a-x_b)^2+(y_a-y_b)^2$ simplifies to $-(2x_ax_b+2y_ay_b)$. The terms for the other 2 are symmetric. The intersection point must reflect to itself, and the equation is $(\frac{x_by_a-x_ay_b-x_a+x_b}{y_b-y_a}, 1)$.

It is trivial to find the intersections of a,b and their perpendicular bisectors, so this is left to the reader as an exercise.

Regardless, the circumcenter and an intersection of the circles are collinear with (0,0), so it is a tangency.


Posted by at
Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)