Solution

Solution 1:$\\$
a$)$ Let’s denote a as a = 2 + $\sqrt{3}$. Since $(2 + \sqrt{3}) (2 – \sqrt{3}) = 1, {a} + {1/a} = (\sqrt{3} – 1) + (2 – \sqrt{3}) = 1$. $\\$
b$)$ Assume that the number a is rational, and we represent it in the form of an irreducible fraction: a = m / n. If {a} + {1 / a} = 1, then, obviously, a + 1 / a is an integer; we denote it by k. So, m / n + n / m = k, that is, $m^2$ + $n^2$ = kmn. It follows that $m^2$ is divisible by n, and $n^2$ is divisible by m, and since m and n are relatively prime, this is possible only for | m | = | n | = 1, that is, for a = ± 1. But in this case {a} + {1 / a} = 0. Which is a contradiction.

Solution 2:$\\$
It follows from the condition that a + 1 / a is an integer, but for an irreducible fraction a = p / q this is impossible: the fraction is also irreducible. Thus, equality holds if and only if a + 1 / a is an integer n, and a is not an integer. Since the equation $a^2$ – na + 1 = 0 for n $>$ 2 can not have rational roots $($see problem 61013$)$, the answer in part b is negative. As an example $($ part a $)$, it is only necessary to solve this equation, for example, for n = 3.

Remarks: $\\$

points: 3 + 5

Answer

a$)$ For example, a = 2 + $\sqrt{3}$. b$)$ It can not.

Hint

Solution

We will plug the “holes” in the graph with vertical segments $($by connecting the limit on the left and the limit on the right at the break point$)$. If we now interchange the coordinate axes, we obtain a graph of a continuous non-decreasing function. Therefore, we can assume that the original function is continuous. For the same reasons, we can assume that its graph contains points $($0, 0$)$ and $($1, 1$)$.

$\\$ Let $A_k (k = 0, 1, …, N)$ be the point of intersection of the graph with the line x + y = 2k/N. The section of the graph between $A_k$ and $A_{k + 1}$ is covered by a rectangle with sides parallel to the axes of coordinates, $($ which is non-degenerate with diagonal $A_kA_{k + 1}$ or degenerate is the segment $A_kA_{k + 1}$$)$ of the perimeter 4/N, that is, an area that is not larger than $1/N^2$. Increasing each rectangle to the area $1/N^2$, we obtain the required covering.

Remarks:$\\$
1. 9 points $($the preparatory version, where the continuity of the function f was also assumed, is worth 8 points$)$.
$\\$ 2. Compare with problem number M884 from the “Quant” problems.

Answer

See the solution above.

Hint

Solution

We will draw an arrow to each female cat from the male cat sitting next to her, which is fatter than she is. Then, the number of arrows is 19: the same as the number of cats. But, on the other hand, no more than two arrows can leave from each male cat since the arrows point to neighbouring cats, and yet, they do not point to all of the female cats, but only to the thinner ones. Consequently, the arrows lead from all male cats, as required.

Answer

See the solution above.

Hint

Solution

We denote the nth word by $W_n$, and the indicated operation by f: $W_n + 1 = f (W_n)$. Note that $f (UV) = f (U) f (V)$. We can assume that
$W_0 = B$. Since $W_2 = W_1W_1W_0, W_{n + 1} = W_nW_nW_{n-1}. (*)$
$\\$ Let $W_n$ contain $a_n$ letters A and $b_n$ letters B. It follows from $(*)$ that $a_{n + 1} = 2a_n + a_{n-1}. (**)$
$\\$ By hypothesis $b_{n + 1} = a_n$.
$\\$ a) We can calculate successively: $a_0 = 0, a_1 = 1, a_2 = 2, a_3 = 5, a_4 = 12, a_5 = 29, a_6 = 70, a_7 = 169, a_8 = 408, a_9 = 985$. Consequently, the 1000th the letter will already appear in the word $W_10 = W_9W_9W_8 = W_9W_5 … = W_9W_4W_4 … = W_9W_4W_3W_3 … = W_9W_4W_2W_2 …$
$\\$ The word $W_9$ contains 985 + 408 = 1393 letters, the word $W_4$ – 12 + 5 = 17 letters, $W_2W_2$ = AAB(A)AB $($the marked letter is the 1000th letter A$)$. Thus, the 1000th letter A is on the 1414th place $(1393 + 17 + 4 = 1414)$.
$\\$ b) Suppose that there exists Then Then, passing to the limit in the equality obtained from $(**)$ , we see that l is the root of the equation l = 2 + 1/l, that is, irrational.
$\\$ Suppose that our sequence is periodic, the pre-period contains c letters, the period contains a letters A, b letters B and fits $k_n$ times in the word $W_n$. Then $k_na ≤ a_n $<$c + (k_n + 1) a, k_nb ≤ b_n $<$c + (k_n + 1) b$; hence, . It follows that $a_n/b_n$ tends to a rational number a/b. This is a contradiction.

Answer

a) At the 1414th place.

Hint

Solution

The solution is similar to the solution of the problem 86118.

Hint

Solution

By hypothesis, the function y = sin x + a – b x vanishes exactly at two points $x-1$ and $x_2$, $x_14$ $<$ $x_2$. These points divide the numerical axis into 3 intervals $($-∞, $x_1$], $(x_1, x_2], (x_2, + ∞)$, Since b ≠ 0 and | sin x | $≤$ 1, then on the intervals $(-∞, x_1)$ and $(x_2, + ∞)$ the function has different signs, therefore on some two adjacent intervals $(-∞, x_1)$, $(x_1, x_2)$ or $(x_1, x_2)$, $(x_2, + ∞)$ the function has the same sign, and then either the point $x_1$ or the point $x_2$ is an extremum point and the derivative on it is y '= $($sin x + a – bx$)$' = cos x - b vanishes.

Hint

Solution

First, let’s “glue” the opposite points of the equator. Then we can assume that Aladdin did not move along the equator, but along the circle obtained after gluing the points together. We will also assume that Aladdin did not teleport at any point in time and that he visited all of the planet’s points. Let 2πφ $($t$)$ be the angular coordinate of Aladdin at time t. Since Aladdin did not teleport at any time, the function φ can be chosen to be continuous. Then it suffices to prove the following assertion:

A continuous function $φ (t)$, where ${φ (t)}$ takes all possible values, is given. Prove that $ \max_ {t}φ (t) – \min_ {t} φ (t) ≥ 1$. But this assertion is obvious: if this difference is less than one, then the function φ cannot take values from {$ \max_ {t} φ (t)$} to 1 and from 0 to {$\min_ {t} φ (t)$}.

Answer

See the solution above.

Hint

Solution

Answer: no this line does not exist. Indeed, if the graph of the function y = $2^x$ is symmetric with respect to some line, then for symmetry with respect to this line the horizontal asymptote y = 0 of this the graph should coincide with some asymptote of this graph. But the graph of the function y = $2^x$ has no other asymptotes. Consequently, for this symmetry, the straight line y = 0 goes into itself, and hence the symmetry axis either coincides with the straight line y = 0, or is perpendicular to it. Checking that the straight line y = 0 and the straight lines of the form x = const are not axes of symmetry of the graph of the function y = $2^x$, is left to the reader as an exercise

Hint

Solution

a) The first way. After each “move” the grasshopper will not jump to the point where the next grasshopper was before. So, the next one after him will not reach this point in two consecutive jumps. So, continuing in this way, we get that after the 12th jump the first one will not reach its initial position.

The second way. Suppose that one of the grasshoppers $($let’s call it the first one$)$ returned to the starting point A after 12 moves. Then the remaining 11 grasshoppers jumped through point A before the first grasshopper returned to this point. But in one move through point A, no more than one grasshopper could jump over, and on the first move through A no one jumped. This is a contradiction.

b) If at the beginning, one of the grasshoppers is moved clockwise, then the first jump, and the next one after it, will jump further, and the rest will jump as before. For the second jump, three grasshoppers will now jump further, and the rest – as before. Continuing the argument in this way, we see that as a result, for 13 jumps all grasshoppers will jump further. We number the grasshoppers counter-clockwise and move all but the first one to the point O, where the first sits $($first we shift the 2nd, then the 3rd, etc.$)$. At this initial position, it is easy to follow the sequence of jumps: the k-th grasshopper will first leave O on the k-th “go”, jumping by $1/2^k$ from the circumference, and the first after this jump will be at the same distance from O on the other side. As a result, the first grasshopper on his 13th jump will return to point O. Hence, in the initial situation, he will not jump to his starting point.

Marks: 4 + 3

Answer

See the solution above.

Hint

Solution

Let the numbers be written out in the order $a_1, …, a_{100}; x_k$ and $y_k$ are respectively the largest lengths of increasing and decreasing sequences starting with $a_k$. Suppose that $x_k ≤ 10$ and $y_k ≤ 10$ for all k. Then the number of all different pairs $($x_k, y_k$)$ does not exceed 100. Therefore, $x_k = x_l$ and $y_k = y_l$ for some numbers k $<$ l. But this cannot be: if $a_k $<$ a_l$, then $x_k $>$ x_l$, and if $a_k $>$ a_l$, then $y_k$ $>$ $y_l$.

1. This task was not solved by any of the participants in the Olympiad.

2. Similarly, one can prove that any sequence of mn + 1 pairwise distinct numbers contains either an increasing sequence of m + 1 numbers or a decreasing sequence of n + 1 numbers.

Answer

See the solution above.

Hint

Solution

See the article by L.N. Kamnev “Irrationality of the sum of radicals”.

Hint

Solution

Nothing to translate.

Answer

$a_n = C_{2n}^n$.

Hint

Hint

Solution

Applying the Jensen inequality $($see problem number 61407$)$ to the function $y = x^p$, we obtain After the substitution we arrive at the inequality or
To obtain the necessary inequality, it remains to make the following substitution

Answer

See the solution above.

Hint

Solution

Nothing to translate.

Hint

Solution

Solution 1

We can find natural numbers m and n such that the inequality holds After the substitution $α = a^{1 / m}, β = b^{1 / n}$, the original inequality takes the form To prove it, it suffices to use the Cauchy inequality:

Solution 2

By the convexity of the function ln x, the inequality $ln (αx + (1 – α) y) ≥ α ln x + (1 – α) ln y$ holds for 0 $<$ α $<$ 1 for all positive x and y $($see problem number 61406$)$. Substituting $α = 1/p, x = a^p, y = b^q$, we obtain as required.

As can be seen from Solution 2, the word “rational” in the condition is not necessary.

Answer

See the solution above.

Hint

Solution

Nothing to translate.

Hint

Solution

Nothing to translate.

Hint

Solution

Let Q $(x)$ = $(x+1)^n$ – $x^n$ – 1, p $(x)$ = $x^2$ + x + 1, then x + 1 = -$x^2$, $x^3$ = 1 $($ mod P $)$ $($ the comparison of polynomials is analogous to the comparison of numbers $)$
a$)$ Q $(x)$ = $(-1)^n$ $x^{2n}$ – $x^n$ + 1 $($ mod P $)$. Let’s consider all possible cases.

1$)$ n is a multiple of 3. Then $(-1)^n$ $x^{2n}$ – $x^n$ – 1 = $(-1)^n$ – 2 $($ mod P $)$.

2$)$ n =1 $($ mod 6 $)$. Then $(-1)^n$ $x^{2n}$ – $x^n$ – 1 = – $x^2$ -x -1 = 0 $($ mod P $)$.

3$)$ n = 2 $($ mod 6 $)$. Then $(-1)^n$ $x^{2n}$ – $x^n$ – 1 = x – $x^2$ – 1 = 2x $($ mod P $)$.

4$)$ n = 4 $($ mod 6 $)$. Then $(-1)^n$ $x^{2n}$ – $x^n$ – 1 = $x^2$ -x -1 = -2x -2 $($ mod P $)$.

5$)$ n = 5 $($ mod 6 $)$. Then $(-1)^n$ $x^{2n}$ – $x^n$ – 1 = -x – $x^2$ -1 = 0 $($ mod P $)$.

Thus, Q is divisible by P for n ≡ 1, 5 (mod 6). In particular, n is odd.

b) As in Problem 61139, it is sufficient to verify whether Q ‘ is divisible by P. Q’ $(x)$ = n $(x+1^{n-1}$ – $nx^{n-1}$ = n $(x^{2n-2} – x^{n-1})$ $($ mod P $)$.
For n=1 $($ mod 3 $)$ $x^{2n-2}$ – $x^{n-1}$ = 1-1 = 0$($ mod P $)$
For n = 2 $($ mod 3 $)$ $x^{2n-2}$ – $x^{n-1}$ = $x^2$ – x = – 2x – 1 $($ mod P $)$.
With this method, we see that Q divides by $P^2$ for n=1 $($ mod 6 $)$.
c$)$ Q” n$(n-1)$ $(( x+1)^{n-2} – x^{n-2})$ = -n $(n-1)$ $(x^{2n-4} + x^{n-2})$ = -n$(n-1)$ $(x + x^2)$ = n $(n-1)$ $($ mod P $)$. With this method we show that Q divides by $P^3$ only if n=1. In fact the polynomial Q is equal to zero.

Answer

For a$)$ n = 6k ± 1; b$)$ n= 6k + 1; c$)$ n = 1

Hint

Solution

Let be a real number. Then is a positive number, that is, is a 2n-th power root of 1. Let then φ can be expressed by a rational number of degrees. In addition, $ tan φ = \sqrt {\frac {b}{a}}$ and $ cos 2 φ = \frac {1-tan^2 φ}{1+tan^2 φ} $ are rational. According to problem number 61103, 2φ is equal to πk/2 or πk/3, as required.

Answer

See the solution above.

Hint