David Kewei Lin

Welcome to my personal site!

239 Olympiad (2019)

Problems from the 239 Olympiad, held by Lyceum 239 in St Petersburg Russia for the year 2019.

Senior

  1. The fractions $\frac{1}{n},\frac{2}{n-1},\frac{3}{n-2},...,\frac{n}{1}$ are written on the board. Bob takes the absolute differences of each pair of neighboring fractions, and finds that there are 10000 unit fractions among them. Show that there are at least 5000 more differences which are unit fractions.
  2. In the square of $100 \times 100$ several cells are marked. Vasya wants to divide the square into several rectangles so that in each rectangle there are no more than two marked cells and no more than $k$ rectangles in which less than two cells are marked. At what minimum $k$ can Vasya always do that?
  3. The radius of the circumscribed circle of the acute triangle is $23$, and the radius of the inscribed is $9$. Common external tangents to its excircles, other than straight lines containing the sides of the original triangle, form a triangle. Find the radius of its inscribed circle.
  4. At the round table sit $n> 1000$ people. Some of them are knights who always tell the truth, and the others are liars who always lie, and there are liars among them. Each of those sitting uttered the phrase: “among the next $20$ sitting clockwise from me there are as many knights as there are among the next $20$ sitting anticlockwise from me.” With what $n$ could this happen?
  5. Circle $\Gamma$ touches the circumcircle of triangle $ABC$ at $R$, and the straight lines $AB$ and $AC$ at $P$ and $Q$ respectively. Let $PQ$ and $BC$ intersect at $X$. The tangent at $R$ to $\Gamma$ intersects segment $QX$ at $Y$. Segment $AX$ intersects the circumcircle of $APQ$ at $Z$. Prove that the circumcircles of $ABC$ and $XYZ$ are tangent.
  6. Find all functions $f: (0; +\infty) \to \mathbb{R}$, such that (i) $f(x)+f(1/x)=1$ for all $x>0$; (ii) $f(xy+x+y)=f(x)f(y)$ for all $x,y>0$.
  7. Given positive $a_1,\ldots,a_n,b_1,\ldots,b_n,c_1,\ldots,c_n$. Let $m_k$ be the maximum product $a_ib_jc_l$ for triples $(i,j,l)$ satisfying $\max(i,j,l)=k$. Prove that $$ (a_1+\dots+a_n)(b_1+\dots+b_n)(c_1+\dots+c_n)\leqslant n^2(m_1+\dots+m_n). $$
  8. Given a natural $k>1$, prove that if each edge of graph $G$ has less than $[e(k-1)!-1]$ simple cycles passing through it, then the vertices are $k$-colorable.

Juniors

  1. On the island of knights and liars held a tennis tournament, which was attended by 100 islanders. Every two played exactly 1 time. After the tournament, each of the participants said: “I beat as many knights as there are liars”, while all the knights told the truth, and all the liars lied. What is the largest number of knights in a tournament?
  2. Is it true that there are 130 consecutive positive integers, each of which has exactly 120 natural dividers?
  3. Circle $\omega$ touches side $AC$ of regular $ABC$ at point $D$, and its circumcircle at $E$,lying on minor arc $BC$. Prove that the segments $AD$, $BE$ and $CD$ forms a triangle where the difference between two of its angles is $60^\circ$.
  4. From the table $20\times 20$ glued torus. In some cage of this board hidden treasure. For one question, you can select a rectangle $1\times 4$ or $4\times 1$ on this torus and find out if there is a treasure in this rectangle. Answers to all questions are absolutely true, but are given only after they are all set. What is the least number of questions is certainly enough to accurately find the treasure? (If we describe the position of the cell in the toric table with the numbers $(i, j)$ row and column, $1\leq i, j \leq 20$, then the two cells are adjacent, if some two coordinates they are the same, and the other two are different by 1 modulo 20).
  5. We call an ordered set of different natural numbers good if for any two numbers the larger is divisible by the smaller. Prove that the number $(n + 1)!-1$ can be expressed as $x_1 + 2x_2 +\dots +nx_n$, where $x_1,\dots, x_n$ forms a good set, in at least $n!$ ways.
  6. Senior #3
  7. Senior #7
  8. There are $n$ devices in the laboratory, each two of which can be wired. Moreover, if for four devices $A, B, C, D$, $AB$, $BC$, $CD$ are connected while $CA$, $AD$, $DB$ are not, the system collapses. The professor came up with a wiring diagram where collapse does not occur. When he arrived at the laboratory, he discovered that a collapse was not yet occurring, but the devices were not connected according to his scheme. Prove that he can realize his scheme by sequentially connecting or disconnecting pairs of devices so that the collapse does not occur at any moment.