Ty.

Given a natural number $n>3$. We will call a set of $n$ points on the coordinate plane admissible if their abscissas are distinct, and each of these points is colored either red or blue. We will say that a polynomial $P(x)$ separates an admissible set of points if either there are no red points above the graph of $P(x)$ and no blue points below, or vice versa (points of both colors may lie on the graph itself). For what smallest $k$ can any admissible set of $n$ points be separated by a polynomial of degree no more than $k$?

#
Let's take any $n-1$ of the given $n$ points; there exists a polynomial of degree not greater than $n-2$ whose graph passes through them. This polynomial, obviously, separates our points. Thus, $k=n-2$ works. We will prove that this number cannot be reduced.

Take the graph of some reduced polynomial $f(x)$ of degree $n-2$ and place $n$ points on it, alternating colors. Suppose that some polynomial $P(x)$, whose degree is not more than $n-3$, separates these points; we can assume that there are no red points below the graph of $P(x)$, and no blue points above it.

The degree of the polynomial $Q(x)=f(x)-P(x)$ is $n-2 \geq 1$. Moreover, if $r$ and $b$ are the abscissas of any red and blue points, respectively, then $P(r) \leq f(r)$ and $P(b) \geq f(b)$, which means $Q(r) \geq 0$ and $Q(b) \leq 0$.

Notice that if $Q(s) \leq Q(t)$ for some $s$ and $t$ (here we use that $Q(x)$ is not a constant), then there exists a point $x$ between $s$ and $t$ where $Q'(x) > 0$. This means that on each interval between a red and a blue point (the red one being to the left of the blue one), there is a point where the value of $Q'(x)$ is positive. Similarly, on each interval between a blue and a red point, there is a point where the value of $Q'(x)$ is negative. Thus, we have found $n-1$ points where $Q'(x)$ takes values of alternating signs. Between any two such neighboring points, $Q'(x)$ has a root. Therefore, the polynomial $Q'(x)$ has at least $n-2$ roots. But this is impossible, since $Q'(x)$ is a polynomial of degree $n-3$. Contradiction.

| Problem 73774 Topics: | $\left[\begin{array}{llll} \\ \text { l }\end{array}\right.$ | Inscribed and circumscribed circles | ] | Difficulty: 4+  Grades: 10,11 |
| :---: | :---: | :---: | :---: | :---: |
|  | [ | Iterations | ] |  |
|  | [ | Rational and irrational numbers | ] |  |
|  | [ | Euler's theorem | ] |  |
|  | $\left[\begin{array}{llll} \\ \text { l }\end{array}\right.$ | Periodicity and non-periodicity | ] |  |
|  | [ | Dirichlet's principle (other). | ] |  |
|  |  | Triangle angles. Theorem about external angles |  |  |

Author: N. Chernov

On a plane, there are two points $A$ and $B$. Let $C$ be some point on the plane, equidistant from points $A$ and $B$. Construct a sequence of points

$C_{1}=C, C_{2}, C_{3}, \ldots$, where $C_{n+1}$ is the center of the circumscribed circle of triangle $A B C_{n}$. For which position of point $C$

a) will the point $C_{n}$ fall on the midpoint of segment $A B$ (in which case $C_{n+1}$ and subsequent terms of the sequence are not defined)?

b) will the point $C_{n}$ coincide with $C$?

## Solution

Let $\angle C_{n} B A=\angle C_{n} A B=\alpha_{n}$. It is easy to verify (see the figure) that for an acute triangle, $\alpha_{n+1}=2 \alpha_{n}-\pi / 2, \pi / 4<\alpha_{n}<\pi / 2$, and for an obtuse triangle, $\alpha_{n+1}=\pi / 2-2 \alpha_{n}, 0<\alpha_{n}<\pi / 4$.

![](https://cdn.mathpix.com/cropped/2024_05_06_70ca2515d9f952ff6eb4g-16.jpg?height=426&width=700&top_left_y=1268&top_left_x=679)

This can be written in one formula: $\alpha_{n+1}=\left|2 \alpha_{n}-\pi / 2\right|, 0<\alpha_{n}<\pi / 2$, which is valid for a right triangle as well; when $\alpha_{n}=\pi / 4$, we get $\alpha_{n+1}=0$ - the center $C_{n+1}$ falls on the midpoint of segment $A B$.

Let $\alpha_{n}=\pi / 2 \cdot x_{n}$. Then $x_{n}$ is obtained from $x_{0}$ by applying the mapping $x \rightarrow f(x)=|2 x-1|, x \in [0,1]$, $n$ times, i.e., $x_{n}=f^{n}\left(x_{0}\right)=\underbrace{f\left(f\left(f \ldots\left(f\left(x_{0}\right)\right) \ldots\right)\right)}_{n \text{ times}}$

Note that $f(0)=f(1)=1, f(1 / 2)=0$. Each of the segments $[0,1 / 2],[1 / 2,1]$ is stretched by $f$ to twice its length and mapped onto the entire segment $[0,1]$ (see the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_70ca2515d9f952ff6eb4g-16.jpg?height=189&width=1397&top_left_y=2112&top_left_x=342)

Clearly, $f^{n}$ "folds" the segment $[0,1]$ not by 2, but by $2^{n}$; the points dividing $[0,1]$ into $2^{n}$ equal parts are mapped by $f^{n}$ to the ends of the segment:

$f^{n}\left(k \cdot 2^{-n}\right)=1$, if $k=2 m$, and $f^{n}\left(k \cdot 2^{-n}\right)=0$, if $k=2 m+1$, (where $k, m, n$ are natural numbers), and each segment $\left[k \cdot 2^{-n},(k+1) 2^{-n}\right]$ is similarly stretched to the entire $[0,1]$.

It is not difficult to verify (see the figure) that $f^{n}(x)=2^{n}\left(x-\frac{2 m-1}{2^{n}}\right)$ for $x \in\left[\frac{2 m-1}{2^{n}}, \frac{2 m}{2^{n}}\right]$, and $f^{n}(x)=2^{n}\left(\frac{2 m+1}{2^{n}}-x\right)$ for $x \in\left[\frac{2 m}{2^{n}}, \frac{2 m+1}{2^{n}}\right]$.

![](https://cdn.mathpix.com/cropped/2024_05_06_70ca2515d9f952ff6eb4g-17.jpg?height=354&width=1392&top_left_y=0&top_left_x=339)

a) The question reduces to finding the roots of the equation $f^{n}(x)=0$. These are clearly all numbers of the form $p \cdot 2^{-n}$ (where $p$ is an odd natural number) from the interval $[0,1]$.

b) It is sufficient to solve the equation $f^{n}(x)=x$. It has $2^{n}$ roots: $x=\frac{2 m-1}{2^{n} \pm 1}\left(m=1,2,3, \ldots, 2^{n-1}\right)$.

## Answer

a) When $\angle C B A=p \pi \cdot 2^{-n-1}$, where $p$ is an odd natural number less than $2^{n}$.

b) When $\angle C B A=\frac{p \pi}{2\left(2^{n} \pm 1\right)}$, where $p$ is an odd natural number, $p \leq 2^{n}-1$ (except for the case $\angle C B A=\pi / 2$).