Monday, March 29, 2021

2019 IMO Problems And Solutions

 

Problem 01

Let $\mathbb{Z}$ be the set of integers. Determine all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that, for all integers $a$ and $b$,\[f(2a) + 2f(b) = f(f(a + b)).\]

Solutions

Solution 1

Let us substitute $0$ in for $a$ to get\[f(0) + 2f(b) = f(f(b)).\]

Now, since the domain and range of $f$ are the same, we can let $x = f(b)$ and $f(0)$ equal some constant $c$ to get\[c + 2x = f(x).\]


Therefore, we have found that all solutions must be of the form $f(x) = 2x + c.$

Plugging back into the original equation, we have: $4a + c + 4b + 2c = 4a + 4b + 2c + c$ which is true. Therefore, we know that $f(x) = 2x + c$ satisfies the above for any integral constant c, and that this family of equations is unique.

(This solution does not work though because we don't know that $f$ is surjective)

Solution 2

We plug in $a=-b=x$ and $a=-b=x+k$ to get\[f(2x)+2f(-x)=f(f(0)),\]\[f(2(x+k))+2f(-(x+k))=f(f(0)),\]respectively.

Setting them equal to each other, we have the equation\[f(2x)+2f(-x)=f(2(x+k))+2f(-(x+k)),\]and moving "like terms" to one side of the equation yields\[f(2(x+k))-f(2x)=2f(-x)-2f(-(x+k)).\]Seeing that this is a difference of outputs of $f,$ we can relate this to slope by dividing by $2k$ on both sides. This gives us\[\frac{f(2x+2k)-f(2x)}{2k}=\frac{f(-x)-f(-x-k)}{k},\]which means that $f$ is linear.

Let $f(x)=mx+n.$ Plugging our expression into our original equation yields $2ma+2mb+3n=m^2a+m^2b+mn+n,$ and letting $b$ be constant, this can only be true if $2m=m^2 \implies m=0,2.$ If $m=0,$ then $n=0,$ which implies $f(x)=0.$ However, the output is then not all integers, so this doesn't work. If $m=2,$ we have $f(x)=2x+n.$ Plugging this in works, so the answer is $f(x)=2x+c$ for some integer 

Problem 02

In triangle $ABC$, point $A_1$ lies on 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 the 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 03

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$, and $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 have $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 04

Find all pairs $(k,n)$ of positive integers such that

\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1}).\]

Solution

$LHS$

$k! = 1$ (when $k = 1$), $2$ (when $k = 2$), $6$ (when $k = 3$)

$RHS = 1$(when $n = 1$), $6$ (when $n = 2$)

Hence, $(1,1)$$(3,2)$ satisfy

For $k = 2: RHS$ is strictly increasing, and will never satisfy $k$ = 2 for integer n since $RHS = 6$ when $n = 2$.

\[k!=(2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})  ...                                                                       (1)\]

In all solutions, for any prime $p$ and positive integer $N$, we will denote by\[v_p(N)\]the exponent of the largest power of $p$ that divides $N$. The right-hand side of $(1)$ will be denoted by\[L_n;\]that is,\[L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})\]

\[(2^{1+2+3+\dots+(n-1)})(2^n-1)(2^{n-1}-1)(2^{n-2}-1)\dots(2^1-1)\]=\[v_2(L_n) = {\frac{n(n-1)}{2}}\]

On the other hand,\[v_2(k!)\]is expressed by the $Legendre$ $formula$ as\[v_2(k!) < \sum_{i=1}^{\infty} (\frac{k}{2^i})) = k\]

Thus, $k! = L_n$ implies the inequality\[\frac{n(n-1)}{2} < k    ...                                                   (2)\]In order to obtain an opposite estimate, observe that\[L_n = (2^n-1)(2^n-2)(2^n-4)\dots(2^n-2^{n-1})\]We claim that\[2^{n^2} < (\frac{n(n-1)}{2})!                   ...                                                     (3)\]for all $n \geq 6$

For $n \geq 6$ the estimate (3) is true because\[2^{6^2} < (6.9)(10^{10})\]and\[(\frac{n(n-1)}{2})! = 15! > (1.3)(10^{12})\]

Problem 05

The Bank of Bath issues coins with an $H$ on one 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 $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 operations 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 06

Let $I$ be the incenter of acute triangle $ABC$ with $AB \neq AC$. The incircle $\omega$ of $ABC$ is tangent to sides $BC$$CA$, and $AB$ at $D$$E$, and $F$, respectively. The line through $D$ perpendicular to $EF$ meets ω again at $R$. Line $AR$ meets ω again at $P$. The circumcircles of triangles $PCE$ and $PBF$ meet again at $Q$. Prove that lines $DI$ and $PQ$ meet on the line through $A$ perpendicular to $AI$.

No comments:

Post a Comment