A positive integer $m(\ge 2$) is given. From circle $C_1$ with a radius 1, construct $C_2, C_3, C_4, ... $ through following acts: In the $i$th act, select a circle $P_i$ inside $C_i$ with a area $\frac{1}{m}$ of $C_i$. If such circle dosen't exist, the act ends. If not, let $C_{i+1}$ a difference of sets $C_i -P_i$. Prove that this act ends within a finite number of times.
Problem
Source: 2021 Korea Winter Program Test1 Day1 #4
Tags: combinatorics, geometry, combinatorial geometry
03.02.2021 15:41
chrono223 wrote: If not, let $C_{i+1}$ a $C_i -P_i$ Please clarify
04.02.2021 23:15
The point is that there is too much space between disjoint circles. So, at some step, the area of the new circle, that is cut off, will be less than $1/m$ of that space. Assume for the sake of contradiction, the process can last infinitely. Let $P_1, P_2, \dots$ be the cut-off circles with radii $r_1> r_2>\dots .$ They form a geometric progression with a ratio less than $1$, but it's not so essential. Fix some $n\in\mathbb N$. We expand each circle $P_k,k=2,\dots,n$ (if needed) so that each of them is tangent to at least 3 other circles (one of them may be the outer circle $C_1$). Denote the new circles as $P_1',P_2',\dots,P_n'$ with radii respectively $r'_1,\dots,r'_n.$ Mark a point $v_0$ outside $C_1$ and consider a graph with vertices all the centers of $P'_1,P'_2,\dots,P'_n$ plus the point $v_0.$ Connect any two centers of $P'_i$ and $P'_j, 1\le i\neq j\le n$ if $P'_i$ and $P'_j$ are tangent (externally). Connect $v_0$ to any $P'_i, 1\le i\le n$ if $P'_i$ is internally tangent to $C_1.$ Thus, $G$ is a planar graph with minimum degree at least $3$. Applying the Euler's formula, it follows the faces of $G$ are at least $n/2.$ At this point we need a pure geometrical claim Claim. Inside the intersection of any face and $C_1$ can be inscribed a circle, disjoint from the others, and with radius greater than some constant multiplied by the minimal radius of the circles that have centers in the vertices of that face. I provide only a sketch, without calculations. Consider first a face that lies inside $C_1,$ i.e. when $v_0$ is not a vertex of the face. The worst case scenario is when this face consists of the centers of three equal circles touching each other externally. In the case when $v_0$ is among the vertices of the face, we consider two consecutive circles $C'_i,C'_j$ (corresponding to an edge of that face) that touch $C_1$ internally, and construct a circle that is externally tangent to $C'_i,C'_j$ and internally tangent to $C_1$. Using the above claim, we can construct $n/2$ circles entirely inside $C_1\setminus\left( P'_1\cup P'_2\cup\dots\cup P'_n\right)$, each of them with radius at least $cr_n$ where $c>0$ is a constant. It means that $$S(P_n)<\frac{c_1}{n}S\big(C_1\setminus\left( P_1\cup P_2\cup\dots\cup P_{n-1}\right)\big).$$($S(X)$ means the area of $X$, $c_1$ is an absolute constant). Taking $n$ large enough, it contradicts with the given condition.
07.02.2021 19:26
actualy, it can be a harder problem by changing it like this. harder one: A positive integer $m(\ge 2$) is given. From circle $C_1$ with a radius 1, construct $C_2, C_3, C_4, ... $ through following acts: In the $i$th act, select a circle $P_i$ inside $C_i$ with a area $\frac{1}{m}$ of $C_i$. If such circle dosen't exist, the act ends. If not, let $C_{i+1}$ a difference of sets $C_i -P_i$. Prove that this act ends within $500m$ times.
10.02.2021 19:48
Yes, from math point of view, it's stronger than the OP. It boils down to estimate the constant from the claim in #3. Which means to find the radius of the circle that externally touches three given mutually tangential circles of the same radius, which means to make some routine calculations. But purely psychologically, this is not a more difficult problem. It is even easier because it contains the direction which should be followed. I mean, given that the process should stop after $cm$ steps ($c$ is some constant), it's not far away to conclude that after the $n$ th step the cut-off circle should have area at most $\frac{c}{n}S(C_n)$ for some constant $c.$ So, my opinion is, in this case revealing the rate of when the process stops gives us some additional information about the possible approach.