International Mathematical Olympiad

First, consider a particular arrangement of circles $C_1,C_2,\dots ,C_n$ where all the centers are aligned and each $C_i$ is eclipsed from the other circles by its neighbors - for example, taking $C_i$ with center $(i^2,0)$ and radius $i/2$ works. Then the only tangent segments that can be drawn are between adjacent circles $C_i$ and $C_{i+1}$, and exactly three segments can be drawn for each pair. So Luciano will draw exactly $3(n-1)$ segments in this case.



For the general case, start from a final configuration (that is, an arrangement of circles and segments in which no further segments can be drawn). The idea of the solution is to continuously resize and move the circles around the plane, one by one (in particular, making sure we never have 4 circles with a common tangent line), and show that the number of segments drawn remains constant as the picture changes. This way, we can reduce any circle/segment configuration to the particular one mentioned above, and the final number of segments must remain at $3n-3$.

Some preliminary considerations: look at all possible tangent segments joining any two circles. A segment that is tangent to a circle $A$ can do so in two possible orientations - it may come out of $A$ in clockwise or counterclockwise orientation. Two segments touching the same circle with the same orientation will never intersect each other. Each pair $(A,B)$ of circles has 4 choices of tangent segments, which can be identified by their orientations - for example, $(A+,B-)$ would be the segment which comes out of $A$ in clockwise orientation and comes out of $B$ in counterclockwise orientation. In total, we have $2n(n-1)$ possible segments, disregarding intersections.

Now we pick a circle $C$ and start to continuously move and resize it, maintaining all existing tangent segments according to their identifications, including those involving $C$. We can keep our choice of tangent segments until the configuration reaches a transition. We lose nothing if we assume that $C$ is kept at least $\epsilon$ units away from any other circle, where $\epsilon$ is a positive, fixed constant; therefore at a transition either: (1) a currently drawn tangent segment $t$ suddenly becomes obstructed; or (2) a currently absent tangent segment $t$ suddenly becomes unobstructed and available.

Claim. A transition can only occur when three circles $C_1,C_2,C_3$ are tangent to a common line $\ell$ containing $t$, in a way such that the three tangent segments lying on $\ell$ (joining the three circles pairwise) are not obstructed by any other circles or tangent segments (other than $C_1,C_2,C_3$).

Proof. Since (2) is effectively the reverse of (1), it suffices to prove the claim for (1). Suppose $t$ has suddenly become obstructed, and let us consider two cases.

Case 1: $t$ becomes obstructed by a circle



Then the new circle becomes the third circle tangent to $\ell$, and no other circles or tangent segments are obstructing $t$.

Case 2: $t$ becomes obstructed by another tangent segment $t^{\prime }$

When two segments $t$ and $t^{\prime }$ first intersect each other, they must do so at a vertex of one of them. But if a vertex of $t^{\prime }$ first crossed an interior point of $t$, the circle associated to this vertex was already blocking $t$ (absurd), or is about to (we already took care of this in case 1). So we only have to analyze the possibility of $t$ and $t^{\prime }$ suddenly having a common vertex. However, if that happens, this vertex must belong to a single circle (remember we are keeping different circles at least $\epsilon$ units apart from each other throughout the moving/resizing process), and therefore they must have different orientations with respect to that circle.



Thus, at the transition moment, both $t$ and $t^{\prime }$ are tangent to the same circle at a common point, that is, they must be on the same line $\ell$ and hence we again have three circles simultaneously tangent to $\ell$. Also no other circles or tangent segments are obstructing $t$ or $t^{\prime }$ (otherwise, they would have disappeared before this transition). $\square$

Next, we focus on the maximality of a configuration immediately before and after a transition, where three circles share a common tangent line $\ell$. Let the three circles be $C_1,C_2,C_3$, ordered by their tangent points. The only possibly affected segments are the ones lying on $\ell$, namely $t_{12},t_{23}$ and $t_{13}$. Since $C_2$ is in the middle, $t_{12}$ and $t_{23}$ must have different orientations with respect to $C_2$. For $C_1$, $t_{12}$ and $t_{13}$ must have the same orientation, while for $C_3$, $t_{13}$ and $t_{23}$ must have the same orientation. The figure below summarizes the situation, showing alternative positions for $C_1$ (namely, $C_1$ and $C_1^{\prime }$ ) and for $C_3$ ($C_3$ and $C_3^{\prime }$ ).



Now perturb the diagram slightly so the three circles no longer have a common tangent, while preserving the definition of $t_{12},t_{23}$ and $t_{13}$ according to their identifications. First note that no other circles or tangent segments can obstruct any of these segments. Also recall that tangent segments joining the same circle at the same orientation will never obstruct each other.

The availability of the tangent segments can now be checked using simple diagrams.

Case 1: $t_{13}$ passes through $C_2$



In this case, $t_{13}$ is not available, but both $t_{12}$ and $t_{23}$ are.

Case 2: $t_{13}$ does not pass through $C_2$



Now $t_{13}$ is available, but $t_{12}$ and $t_{23}$ obstruct each other, so only one can be drawn.

In any case, exactly 2 out of these 3 segments can be drawn. Thus the maximal number of segments remains constant as we move or resize the circles, and we are done.

Answer: If there were $n$ circles, there would always be exactly $3(n-1)$ segments; so the only possible answer is $3\cdot 2017-3=6048$.

---

Alternative solution.

First note that all tangent segments lying on the boundary of the convex hull of the circles are always drawn since they do not intersect anything else. Now in the final picture, aside from the $n$ circles, the blackboard is divided into regions. We can consider the picture as a plane (multi-)graph $G$ in which the circles are the vertices and the tangent segments are the edges. The idea of this solution is to find a relation between the number of edges and the number of regions in $G$; then, once we prove that $G$ is connected, we can use Euler's formula to finish the problem.

The boundary of each region consists of 1 or more (for now) simple closed curves, each made of arcs and tangent segments. The segment and the arc might meet smoothly (as in $S_i$, $i=1,2,\dots ,6$ in the figure below) or not (as in $P_1,P_2,P_3,P_4$; call such points sharp corners of the boundary). In other words, if a person walks along the border, her direction would suddenly turn an angle of $\pi$ at a sharp corner.



Claim 1. The outer boundary $B_1$ of any internal region has at least 3 sharp corners.

Proof. Let a person walk one lap along $B_1$ in the counterclockwise orientation. As she does so, she will turn clockwise as she moves along the circle arcs, and not turn at all when moving along the lines. On the other hand, her total rotation after one lap is $2\pi$ in the counterclockwise direction! Where could she be turning counterclockwise? She can only do so at sharp corners, and, even then, she turns only an angle of $\pi$ there. But two sharp corners are not enough, since at least one arc must be present-so she must have gone through at least 3 sharp corners. $\square$

Claim 2. Each internal region is simply connected, that is, has only one boundary curve.

Proof. Suppose, by contradiction, that some region has an outer boundary $B_1$ and inner boundaries $B_2,B_3,\dots ,B_m(m⩾2)$. Let $P_1$ be one of the sharp corners of $B_1$.

Now consider a car starting at $P_1$ and traveling counterclockwise along $B_1$. It starts in reverse, i.e., it is initially facing the corner $P_1$. Due to the tangent conditions, the car may travel in a way so that its orientation only changes when it is moving along an arc. In particular, this means the car will sometimes travel forward. For example, if the car approaches a sharp corner when driving in reverse, it would continue travel forward after the corner, instead of making an immediate half-turn. This way, the orientation of the car only changes in a clockwise direction since the car always travels clockwise around each arc.

Now imagine there is a laser pointer at the front of the car, pointing directly ahead. Initially, the laser endpoint hits $P_1$, but, as soon as the car hits an arc, the endpoint moves clockwise around $B_1$. In fact, the laser endpoint must move continuously along $B_1$ ! Indeed, if the endpoint ever jumped (within $B_1$, or from $B_1$ to one of the inner boundaries), at the moment of the jump the interrupted laser would be a drawable tangent segment that Luciano missed (see figure below for an example).



Now, let $P_2$ and $P_3$ be the next two sharp corners the car goes through, after $P_1$ (the previous lemma assures their existence). At $P_2$ the car starts moving forward, and at $P_3$ it will start to move in reverse again. So, at $P_3$, the laser endpoint is at $P_3$ itself. So while the car moved counterclockwise between $P_1$ and $P_3$, the laser endpoint moved clockwise between $P_1$ and $P_3$. That means the laser beam itself scanned the whole region within $B_1$, and it should have crossed some of the inner boundaries.

Claim 3. Each region has exactly 3 sharp corners.

Proof. Consider again the car of the previous claim, with its laser still firmly attached to its front, traveling the same way as before and going through the same consecutive sharp corners $P_1,P_2$ and $P_3$. As we have seen, as the car goes counterclockwise from $P_1$ to $P_3$, the laser endpoint goes clockwise from $P_1$ to $P_3$, so together they cover the whole boundary. If there were a fourth sharp corner $P_4$, at some moment the laser endpoint would pass through it. But, since $P_4$ is a sharp corner, this means the car must be on the extension of a tangent segment going through $P_4$. Since the car is not on that segment itself (the car never goes through $P_4$ ), we would have 3 circles with a common tangent line, which is not allowed.



We are now ready to finish the solution. Let $r$ be the number of internal regions, and $s$ be the number of tangent segments. Since each tangent segment contributes exactly 2 sharp corners to the diagram, and each region has exactly 3 sharp corners, we must have $2s=3r$. Since the graph corresponding to the diagram is connected, we can use Euler's formula $n-s+r=1$ and find $s=3n-3$ and $r=2n-2$.

Answer: If there were $n$ circles, there would always be exactly $3(n-1)$ segments; so the only possible answer is $3\cdot 2017-3=6048$.