A positive integer m(≥2) is given. From circle C1 with a radius 1, construct C2,C3,C4,... through following acts: In the ith act, select a circle Pi inside Ci with a area 1m of Ci. If such circle dosen't exist, the act ends. If not, let Ci+1 a difference of sets Ci−Pi. 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 Ci+1 a Ci−Pi 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 P1,P2,… be the cut-off circles with radii r1>r2>…. They form a geometric progression with a ratio less than 1, but it's not so essential. Fix some n∈N. We expand each circle Pk,k=2,…,n (if needed) so that each of them is tangent to at least 3 other circles (one of them may be the outer circle C1). Denote the new circles as P′1,P′2,…,P′n with radii respectively r′1,…,r′n. Mark a point v0 outside C1 and consider a graph with vertices all the centers of P′1,P′2,…,P′n plus the point v0. Connect any two centers of P′i and P′j,1≤i≠j≤n if P′i and P′j are tangent (externally). Connect v0 to any P′i,1≤i≤n if P′i is internally tangent to C1. 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 C1 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 C1, i.e. when v0 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 v0 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 C1 internally, and construct a circle that is externally tangent to C′i,C′j and internally tangent to C1. Using the above claim, we can construct n/2 circles entirely inside C1∖(P′1∪P′2∪⋯∪P′n), each of them with radius at least crn where c>0 is a constant. It means that S(Pn)<c1nS(C1∖(P1∪P2∪⋯∪Pn−1)).(S(X) means the area of X, c1 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(≥2) is given. From circle C1 with a radius 1, construct C2,C3,C4,... through following acts: In the ith act, select a circle Pi inside Ci with a area 1m of Ci. If such circle dosen't exist, the act ends. If not, let Ci+1 a difference of sets Ci−Pi. 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 cnS(Cn) 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.