There is $n$ black points in the plane.We do the following algorithm: Start from any point from those $n$ points and colour it red. Then connect this point to the nearest black point available and colour this new point red. Then do the same with this point but at any step , but you are never allowed to draw a line which intersects on of the current drawn segments. If you reach an intersection , the algorithm is over. Is it true that for any $n$ and at any initial position , we can start from a point st in the algorithm , we reach all the points?
Problem
Source: Iran MO 3rd round 2023 , Day 2 P2
Tags: algorithm, combinatorics
carefully
23.08.2023 20:36
No. Consider the following shape of "two diamonds". Note that $EA$ is shorter than $EC$ and $ED$. (Analogously, $FB$ is shorter than $FC$ and $FD$.) If we start at $A$, we go $A \rightarrow B \rightarrow C \rightarrow D$ or $A \rightarrow B \rightarrow D \rightarrow C$, intersecting. (Analogously, starting at $B$ is the same.) If we start at $C$, we go $C \rightarrow A \rightarrow B \rightarrow D \rightarrow E \rightarrow F$ ($A$ and $B$ can swap; $E$ and $F$ can swap.), intersecting. (Analogously, starting at $D$ is the same.) If we start at $E$, we go $E \rightarrow A \rightarrow B \rightarrow C \rightarrow D$ or $E \rightarrow A \rightarrow B \rightarrow D \rightarrow C$, intersecting. (Analogously, starting at $F$ is the same.)
jannatiar
30.08.2023 21:51
NO Example: We draw A and B on the two sides of the points on a circle Proof: If we start from point A: the algorithm enters the circle and makes a round. Obviously, point B does not turn red. Also, if we start from point B, it will be solved similarly. If we start from one of the points on the circle: we make one round and then we can go to one of the points A or B at most.
Attachments:
rama1728
28.12.2023 15:00
Cute troll. Solved with cursed_tangent1434 The answer is no. Assume FTSOC that this is not the case. We provide a construction. Put two points very far away and a circle exactly in between them with small radius. Place $5$ equally spaced points on the circle so that no three points in this configuration are collinear, but one of the points has infinitisimally small distance to the line adjoining those two points not on the circle. Now, if the initial position is of one of the points on the circle, then the pentagon must be completed except for one missing segment and then the segment joining the two points not on the circle must be drawn. This clearly intersects one of the drawn segments inside the circle, a contradiction. While if the initial position is one of the two points not on the circle, then the segment joining one of the two closest points of that point on the circle which is nearest to one of the two points not on the circle which is the initial point, to the other of the two points not on the circle (i.e. not the initial point) should be drawn. As above, this also clearly intersects a drawn segment within the circle and we're done.