Shortlist 2017/G8

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Shortlist 2017/G8

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

436 posts

#1 h Jul 10, 2018, 11:29 AM • 6 Y

Y by Amir Hossein, ValidName, scimaths, megarnie, Adventure10, Mango247

There are $2017$ mutually external circles drawn on a blackboard, such that no two are tangent and no three share a common tangent. A tangent segment is a line segment that is a common tangent to two circles, starting at one tangent point and ending at the other one. Luciano is drawing tangent segments on the blackboard, one at a time, so that no tangent segment intersects any other circles or previously drawn tangent segments. Luciano keeps drawing tangent segments until no more can be drawn.

Find all possible numbers of tangent segments when Luciano stops drawing.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3223 posts

#2 h Jul 10, 2018, 12:05 PM • 22 Y

Y by DVDthe1st, yugrey, rkm0959, coolstuff, StoryScene, ac_math, Amir Hossein, DrMath, AIME12345, trumpeter, Kagebaka, bluephoenix, shankarmath, TheUltimate123, amar_04, Toinfinity, Aryan-23, BVKRB-, megarnie, rayfish, Adventure10, Mango247

Beautiful geometry problem!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

104 posts

#5 h Jul 17, 2018, 11:44 AM • 2 Y

Y by CANBANKAN, Adventure10

Solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

104 posts

#6 h Jul 17, 2018, 9:02 PM • 3 Y

Y by CANBANKAN, Adventure10, Mango247

ABCDE wrote:

Beautiful gold medalist! Beautiful solution!

Beautiful solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

366 posts

#7 h Jul 17, 2018, 9:36 PM • 3 Y

Y by SleepWalker, Adventure10, Mango247

I believe it's always $3n-3$ (let $n=2017$ ). Say we have $n$ circles and $m$ segments such that no more can be drawn. Choose a circle and continuously dilate and translate it, together with its segments, while keeping the rest of the picture the same. Do this until either a new segment becomes available or an old segment becomes intersected (wlog assume the latter). If the old segment becomes intersected by a circle, we easily see that at this moment 3 circles must have a common tangent. If the old segment becomes intersected by another segment, assume these 2 segments are tangent to the same circle. (We can assume this wlog if we assume all circles are always $\ge 1$ cm apart). Then again at this moment, 3 circles must have a common tangent.

In any case, the maximality of $m$ can only change when 3 circles share a common tangent. It is easy to check, however, that this situation only affects 3 segments (the ones lying on the common tangent line), and both before and after the event, exactly 2 of these 3 segments can be drawn. Therefore, as long as the circles are always $\ge 1$ cm apart, the number $m$ can never change. Consider the following configuration: a giant circle and little tiny circles very close to it, resembling a regular $n-1$ -gon. We can easily check that no segments are drawable between the tiny circles. And the segments drawn between two distinct tiny circles and the giant circle don't affect each other. Between each tiny circle and the giant one we can draw 3 segments. Thus, no matter how he draws the segments, Luciano will always draw $m=3n-3$ segments.

Thus, if we start with any picture, re-scale it so that all circles are at least $\ge G$ cm apart (where $G$ is very big), and continuously deform it circle-by-circle to the configuration previously explained, we see that $m=3n-3$ always. $\square$

This post has been edited 1 time. Last edited by JuanOrtiz, Jul 17, 2018, 9:36 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

104 posts

#8 h Jul 20, 2018, 2:34 PM • 2 Y

Y by Adventure10, Mango247

Thank you!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#9 h Mar 27, 2022, 5:49 AM • 2 Y

Y by Awesome_guy, ihatemath123

We can think of the edges as windmills along faces of the graph permitting circular edges between vertices (tangency points): The outer windmill has an angle sum of $2\pi$ . It can be shown that if a windmill changes direction, it must only touch two circles and have angle sum $\pi$ . If a windmill doesn't change direction, it can be shown by various convexity arguments that it must touch only three circles and by extending to a triangle, the angle sum of the windmill is $\pi$ .

By the Euler characteristic, since every vertex in this graph has degree 3, $E + 2 = F + \frac{2}{3}E$ , where since the sum of the angle measures of all windmills must allow you to recover all circular arcs of the graph, if $F'$ is the number of non-circular faces then $(F'-1)\pi + 2\pi = n(2\pi)$ so $F = 3n-1$ , so $E = 9n-9$ . Then notice the number of circular edges is equal to the number of vertices on each circle, so the number of straight edges is $E - V = 3n-3$ , and so the only number is $6048$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#10 h Sep 25, 2023, 6:01 AM • 1 Y

Y by The_Great_Learner

Let $2017$ be replaced with arbitrary $n$ . I claim the only answer is $3n-3$ .

Draw a multigraph $G$ on the circles where two vertices are connected if and only if their corresponding circles have a tangent drawn.

Split the figure into multiples regions, which correspond to the faces of $G$ , some of which are bounded. A short proof shows that the sum of the angles induced by the arcs on the boundary of each bounded region $\mathcal{R}$ is $2\pi$ ; this can be seen by considering the orientation of a directed point moving along the path of the boundary. Now call a tangency point that forms an acute angle with the previous arc on the path a pocket knife, and all other tangency points revolvers. As a consequence of the arc sum result, there are at least $3$ pocket knives.

Consider the line tangent to the boundary of $\mathcal{R}$ as a point moves along it, and refer to these lines as lightsabers. By geometric continuity, there exists a lightsaber from one arc of a circle (not at an endpoint of the arc) that is tangent to another. This inductively proves that $G$ is connected.

Now we show that there are at most $3$ pocket knives. Assume for contradiction that there are $4$ pocket knives, and WLOG $3$ of them are consecutive. Label the consecutive circles $\omega_1, \omega_2, \omega_3$ in that order and the 4th one $\omega_4$ . Then we have a contradiction since there is then a lightsaber from $\omega_2$ through both $\omega_4$ and either one of $\omega_1$ and $\omega_3$ . Thus there are exactly $3$ pocket knives.

The pocket knives allow us to use a double counting strategy to prove a correlation between $E$ and $F$ . Each edge of $G$ corresponds to $2$ pocket knives, and each face of $G$ corresponds to $3$ pocket knives, so counting the total pocket knives we have $2E=3F$ . Thus by Euler's formula, $V+F-E=2 \rightarrow E = 3n-3,$ as desired.

Remark: This is just a convexity problem where you have to know what you want to prove, which is essentially the small graph theory portion of the problem.

This post has been edited 3 times. Last edited by Leo.Euler, Sep 25, 2023, 10:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

140 posts

#11 h Dec 16, 2023, 5:31 AM

Y by

this problem took me like 2 hrs to digest and then 1 hr to finish, after given the hint that it's local. i maintain that g6 summit should be g8 summit (this is unrelated, this is from zcx globloc)

Consider a situation where the common external tangent between two consecutive circles ``covers'' the other circles to the left; it's evident that now you can only draw tangents between consec circles which gives 3(n-1) with n circles. We prove this is always the answer by local technique of moving/dilating one circle at a time. The main claim is that a \emph{change} where a tangent is (WLOG) now obstructed (rather than made possible) can only occur when three circles share a common tangent at some moment of moving before then. Indeed, if a tangent line t is blocked by a circle, at some point it must've been tangent so at that moment done; while if t is blocked by a segment t', t,t' must both have a vertex on a common circle (otherwise to intersect you'd have to move the circle through t'), so we observe that at some moment t,t' must be ``tangent'' (in the sense that all points of t are on the same side of t'), but since they're on same circle they must be collinear (tangent at the same point), proved.

and oh wait!! we're done!!!!!!!!!!!! if we perturb by ever so slightly s.t. no other circles/segments obstruct anything, either t12 and t23 are available but t13 is obstructed by C2 (where C1,C2,C3 are the circles), or all are available but then t12 and t23 intersect. hence exactly 2 tangents exist, but remember. we started with t,t' as the 2 tangents, so no. of tangents is invariant!!!

This post has been edited 1 time. Last edited by signifance, Dec 16, 2023, 5:32 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a