So THAT is what Geoff Smith was talking about when he said that he will be with the contestants in a special way...

As I guessed ^^ By the way, IMO seems to be fond of Frogs. In 1979, 2009 a frog was featured.

A simple parity argument proves 6 (a): choose a line L and place a frog on a line anywhere. For all other lines L', - if frog on L passes L cap L' on even clap, place frog on L' such that it passes L cap L' on odd clap. - vice versa. Choose any two lines L1 and L2 and a simple geometry argumet shows that two frogs pass L1 cap L2 in claps of different parity. I'm assuming (b) is much more difficult...

It is not Guess, we can consider segments' endpoints in clockwise order (after extending all segments we will not get new intersections) and understand, that the only way to win is to choose every second as a start point (consider every two neighboring endpoints) In case n is even, we choose both endpoints of the same segments - contradiction. In case n is odd, it's easy to show that no collision will happen because of the parity.

For 6(b), just imagine taking a massive circle encasing all the $\binom{n}{2}$ intersection points of the $n$ lines. Say it intersects the segments at $P_1, P_2, \dots, P_{2n}$ in clockwise order. Then it is easy to see that one cannot place frogs at consecutive points $P_i$ and $P_{i+1}.$ Also, by counting, $P_{i+n}$ is on the same line as $P_i$. So if $n$ is even, the only way to pick $n$ of these points is to choose $P_1, P_3, \dots, P_{2n-1}$, but then you pick $P_1, P_{n+1}$, contradiction. For 6(a), this same thought process gives you a construction of $P_1, P_3, \dots, P_{2n-1}$. The proof is by a simple parity argument. This is very easy to guess if you just do a few small cases and notice that the pairs of "violating points" just forms a large cycle around.

That is definitely the easiest P6 over the last 10+ years.

VadymKa wrote: It is not Guess, we can consider segments' endpoints in clockwise order (after extending all segments we will not get new intersections) and understand, that the only way to win is to choose every second as a start point (consider every two neighboring endpoints) In case n is even, we choose both endpoints of the same segments - contradiction. In case n is odd, it's easy to show that no collision will happen because of the parity. very nice. To prove strictly, say line segment AB and CD, there are p endpoints between A and C, AB and CD intersects at E, so ACE is divided into exactly p +2t parts where t is the number of segments both cutting AE and EC. If p=0, then AE and EC are cut only by the segments both cut AE and EC. then If we choose A and C thus the frogs will meet.

6(b). Extend everything. After all, they will not intersect again. Now place the endpoints in a big large circle. (1) Since all $n$ lines meet inside the circle, the lines must be in a form of $P_iP_{n+i}$. Assume otherwise. Then the "distance" between the two points are less than $n-1$, so it meets no more than $n-2$ lines, a contradiction. (2) First, we show that we cannot select consecutive points. If we select two points $P_i$ and $P_{i+1}$, we show that the two frogs intersect the $P_iP_{i+n} \cap P_{i+1}P_{i+n+1}$ at the same parity. Denote this intersection $X$. If a line was to intersect segment $P_iX$ and $P_{n+i+1}X$ at the same time (or vice versa), the endpoint of that line has to be between $P_i$ and $P_{i+1}$, which is impossible. Therefore, we need to choose $P_1, P_3, P_5, \cdots P_{2n-1}$, but we end up choosing $P_1, P_{n+1}$ since $n$ is even. Contradiction.

6(a). Now we chose $P_1, P_3, \cdots P_{2n-1}$. Let us prove it works. Select $P_{2i+1}$ and $P_{2j+1}$ and let the intersection of the two lines be $X$. There are odd numbers of points between the two points, lines from those points will hit either $P_{2i+1}X$ or $P_{2j+1}X$. Now since the lines are in general position, no line hits $X$ itself. Therefore, number of lines that hit $P_{2i+1}X$ + number of lines that hit $P_{2j+1}X$ is odd, so parity is different. GG. $\blacksquare$

Yep 6b works with the "consecutive cant be chosen" argument...

Tintarn wrote:

Chinese:杰夫(Jeff)

Tintarn wrote:

Hebrew: Lev

Tintarn wrote:

Vietnam: Minh

For 6(b): Prove there are two lines which their midpoint's intersection are coincident.

Indonesian: Cecep

mahsa wrote: For 6(b): Prove there are two lines which their midpoint's intersection are coincident. Not true

Tintarn wrote:

Tintarn wrote:

Czech: Pepa (the creator of the problem)

Solved with eisirrational, goodbear, Th3Numb3rThr33. Draw a large circle that contains all intersection points, and extend the segments so that they are chords of the circle. [asy][asy] size(5cm); defaultpen(fontsize(10pt)); pair A1,A2,B1,B2,C1,C2,D1,D2,E1,E2; A1=dir(225); A2=dir(60); B1=dir(120); B2=dir(315); C1=dir(80); C2=dir(240); D1=dir(330); D2=dir(210); E1=dir(300); E2=dir(100); filldraw(circle(origin,1),cyan+white+white+white+white,blue); draw(A1--A2,deepcyan); draw(B1--B2,deepcyan); draw(C1--C2,deepcyan); draw(D1--D2,deepcyan); draw(E1--E2,deepcyan); dotfactor *= 1.5; dot(A1,heavygreen); dot(B1,heavygreen); dot(C1,heavygreen); dot(D1,heavygreen); dot(E1,heavygreen); dot(A2,gray); dot(B2,gray); dot(C2,gray); dot(D2,gray); dot(E2,gray); [/asy][/asy] Color green the endpoint of each chord on which the frog starts, and color the other endpoint gray. Claim: Geoff fulfills his wish if and only if, if we traverse the circumference of the circle, we alternate between green and gray endpoints. Proof. Assume this is not true, and two consecutive endpoints $A$, $B$ have the same color. Without loss of generality $A$, $B$ are green (since all frogs starting at the other end produces the same result). Suppose the chords through $A$, $B$ intersect at $C$. Then any chord that intersects segment $AC$ must intersect segment $BC$ as well, and vice versa, so the frogs starting at $A$, $B$ meet at $C$, contradiction. Assume this is true. Let $A$, $B$ be two green endpoints whose chords intersect at $C$. I claim the number of intersection points on segment $AC$ and the number of intersection points on segment $BC$ have different parity, and are thus not equal. Indeed, if $P$ lies on arc $AB$ (contained in $\angle ACB$), then it intersects only one of segment $AC$ and segment $BC$, but if $P$ lies outside of arc $AB$, it either intersects both segment $AC$ and segment $BC$ or neither. Since an odd number of points lie on segment $AB$, the total number of intersection points on segments $AC$, $BC$ is odd, as claimed. $\blacksquare$ If $n$ is odd, the above is clearly possible, but if $n$ is even, then attempting to color the chords as above results in some chord having endpoints the same color. This completes the proof.

Draw a large enough circle to encompass all intersection points, and extend the segments to hit the perimeter of the circle at $2n$ points. It is easy to see that any two points of a segment must be separated along the circle by $n-1$ points. If two points of a segment are on the same side of another segment, then these two segments intersect, which is not possible. Hence each of the other $n-1$ segments have one point on each side of the given segment, as desired. Hence, label the points on the circumcircle as $A_1, A_2, \ldots , A_{2n}$ where $A_iA_{i+n}$ forms a segment, which we label $\ell_i$ for a total of $n$ segments. Consider the following claims: Claim: Frogs that start on $A_i, A_{i+1}$ will collide. Proof: This is not hard. Let $\ell_i \cap \ell_{i+1}$ at $P$. Now for all other $n-2$ segments $\ell_k$, the segment must either intersect both $A_iP$ and $A_{i+1}P$ or neither, hence they have the same number of intersections, as desired. $\square$. Claim: Frogs on $A_i$ and $A_j$ will collide if and only if $i - j \equiv 1\pmod 2$. Proof: Consider the $i - j - 1$ segments $\ell_k$ between $A_i$ and $A_j$. Note that if $i - j - 1 \equiv 0 \pmod 2$ then each new line $\ell_k$ intersects $\ell_i$ and $\ell_j$ at the same number of points. Otherwise, they are different, as desired. $\square$. The problem is killed. If $n$ is even we must put a frog at the end of each segment so some two consecutive points have frogs, which is bad. If $n$ is odd we just place frogs at $A_{2i + 1}$ which works. $\blacksquare$

To prove that even fails, label the segments $l_{1}, l_{2}, \ldots l_{2n}$ with endpoints at $a_{1}, a_{2}, \ldots a_{2n}$, such that $a_{2}, a_{3}, \ldots a_{2n}$ are all on the right side of $l_{1}$, and no $a_{i}$ lies in the region formed by $a_{j-1}, a_{j}, l_{j-1}\cap l_{j}$ (clockwise order). Define the distance of an intersection point $I$ as a pair $(x, y)$, such that $x$ is the smallest number of points from $I$ to an endpoint on the first line, and $y$ is the smallest number of points from $I$ to an endpoint on the second line. Call a intersection point kawaii if $x = y$. If a point is kawaii, then the frogs on the lines going through that point can not be on the same starting side. I claim that the intersection of $l_{i}, l_{i+1}$ are kawaii, and that XOR(points from $a_{i}$ to intersection, poitns from $a_{i+1}$ to intersection) = 0. To prove this, let the intersection of $l_{i}, l_{i+1}$ be $I$. Then, for any line going through these two lines, it must either intersect $Ia_{i}, Ia_{i+1}$, or the opposing segment. If this was not the case, then the line would be in the region defined by $a_{i} a_{i+1} I$, a contradiction due to our definition. Thus, $I$ is kawaii (each line that goes through $l_{i}, l_{i+1}$ will increase $x$ and $y$ by either $1$ or $-1$). Let a array called arr of $Y$'s and $N$'s be such that, for the character on the ith position, it is $Y$ if the frog starts on $a_{i}$ and $N$ otherwise. WLOG, let the first character be $Y$ (we can assume this, since we could just switch the starting point of each frog). Then, since no two frogs intersect, for any two adjacent points, we can't have arr(i) = arr(i-1), or else they will meet on the intersection point, which is kawaii. Thus, the array alternates $YNYN\ldots YNYN$. It ends at $N$ since $2n$ is even. However, let $a_{2n+1}$ be the other endpoint of $l_{1}$. Since $a_{2n+1}$ is adjacent to $a_{2n}$, it must have a $Y$, but since $a_{1}$ is $Y$, $a_{2n+1}$ must be $N$, a contradiction. Thus, even is impossible. To prove that odd is possible, we will use the same labeling scheme. I claim an intersection point of $l_{i}\cap l_{j} = I$ is kawaii only if $2 | j-i$. This is because, for each line that goes on one side of $l_{i}$ and the other side of $l_{j}$ wrt $I$ will either increase the x value by $1$ and decrease the y value of the pair by $1$, or the other way around. Since $x = y$ at the beginning (where there are no lines going through), and each time we count a line that goes between $l_{i}, l_{j}$, it must have it's endpoint in the region $a_{i}Ia_{j}$, there must be an even such number of such lines, or else $y$ is decreased a different number of times that $x$ is decreased implies un-kawaiiness. Then, for odd $n = 2n+1$, we do the same scheme of $YNYN\ldots YN$. Since any pair of points with even distance away will have different characters, even if their intersection point was kawaii, they won't meet becuase they're on different sides. We can't have a point be $(\frac{2n+1}{2}, \frac{2n+1}{2})$ because they're not integers, so there is no case where having $Y, N$ with the intersection point being kawaii will result in the frogs meeting. For each pair of points with the same character, their intersection point is not kawaii, so they won't meet. Thus, this frog placing scheme works, which means all odd $n$ will satisfy Geoff's wishes.

termas wrote: There are $n\ge 2$ line segments in the plane such that every two segments cross and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it facing the other endpoint. Then he will clap his hands $n-1$ times. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time. (a) Prove that Geoff can always fulfill his wish if $n$ is odd. (b) Prove that Geoff can never fulfill his wish if $n$ is even. Part a) Without loss of generality let us say that the endpoint of those segment lie on a circle $\Omega$ and let the lines be $l_1, l_2 \dots l_{2k+1}$. We color these $4k+2$ endpoints by red and blue alternate coloring in clockwise manner such that the endpoint nearest to a endpoint in clockwise direction has a polar or different color than that of the first endpoint taken under consideration. We see that placing frogs at all red points suffices and we'll prove why it suffices. We begin by noticing that given a line segment, the two endpoint have different color. We see that if we place frogs $A$ and $B$ at $P_j$ and $P_{j+2}$ located on segment $S_i, S_{i+2}$ ($S_k$ may periodically repeat), then frogs $A$ and $B$ move to $S_i \cap S_{i+2}$ and $S_{i+1} \cap S_{i+2}$ or $A$ and $B$ move to $S_i \cap S_{i+1}$ and $S_i \cap S_{i+2}$ depending on whether $S_i \cap S_{i+1}$ or $S_i \cap S_{i+2}$ is closer to the blue endpoint of $S_{i+1}$. It can be hence seen that one of the frogs take the previous spot of the other frog and the other frog moves ahead, and similarly we can extend this argument to in fact any two frogs on $S_i$, $S_{i+2m}$ which I'll leave to the reader to decide how that would work. It is a bit messier but a parity argument would work well. For part b), observe that $\exists$ consecutive endpoint with same color. Let $S_j, S_k$ be segment containing these two points and let $K = S_j \cap S_k$. But see that any segment that cuts $S_i$ would also cut $S_j$ and hence the frogs on these segments must meet at $K$, hence Geoff is just sad when number of segments are even.

Instant death by constructing n=5. Very pretty result.

Consider a sufficently large circle, which contains all common points of given segments in the interior, and extend all segments in such way, that their endpoints $P_1,P_2,\dots,P_{2n}$ lies on circle in that order (the numeration is cyclic, we always use anticlockwise orientation). Claim. All $P_iP_{i+n}$ are exactly given segments. Proof. Let $P^*_i$ denotes the second endpoint of segment through $P_i.$ Segment which intersects the arc $P^*_iP^*_{i+1}$ must also intersect $P_iP_{i+1},$ therefore $P^*_i,P^*_{i+1}$ are consecutive. The conclusion easily follows $\Box$ Part a. Let Geoff places frogs to points $P_1,P_3,\dots,P_n;$ we claim that this works. Color red all common points of segments. It's suffice to prove that for $1\leq 2a+1<2b+1\leq n$ and $Q=P_{2a+1}P_{2a+n+1}\cap P_{2b+1}P_{2b+n+1}$ numbers of red points on segments $P_{2a+1}Q,P_{2b+1}Q$ $(\mho)$ has different parity. Indeed, any given segment intersecting arc $P_{2b+1}P_{2a+n+1}$ crosses either none of $(\mho)$ or both, and any of $2(b-a)+1$ segments intersecting arc $P_{2a+1}P_{2b+1}$ crosses exactly one of $(\mho)$ $\blacksquare$ Part b. Assume the opposite and consider a satisfying arrangement of frogs. Define $R_i=P_iP_{i+n}\cap P_{i+1}P_{i+n+1}.$ Notice that any segment intersect sides of exactly one of $\triangle R_iP_iP_{i+1},\triangle R_iP_{i+n}P_{i+n+1},$ therefore exactly one of points $P_i,P_{i+1}$ contains a frog. WLOG $P_1$ contains the frog; then points $P_1,P_{n+2},P_{2n+3}=P_3,P_{n+4},P_{2n+5}=P_5,\dots$ contain frogs - since $n$ is even, there is a point $P_{n+1}$ in this sequence, contradiction $\blacksquare$

Extend the segments to lines (but keep the frogs where they are) and take some massive circle containing every intersection group. Label the segments/lines from $1$ to $n$. If we walk clockwise around the circle and, whenever encountering a line, write down its label, we will write down $1$ to $n$ in some order, and then have the same string repeated. If we have two lines $\ell_i$ and $\ell_j$ intersecting at $X$ which intersect the circle at $P_i$ and $P_j$ (not defined uniquely—these can be either of the two intersections) such that no other line intersects the circle within (minor) arc $P_iP_j$, the part of the plane bounded by rays $\overrightarrow{XP_i}$ and $\overrightarrow{XP_j}$ (including the arc) cannot contain the endpoint of any segment. This is because if such a segment exists, it must intersect both $\ell_i$ and $\ell_j$, but we can clearly see that its corresponding line would then intersect the circle on arc $P_iP_j$. Hence every other segment either intersects both segments $\overline{XP_i}$ and $\overline{XP_j}$ or both $\overline{XP_i'}$ and $\overline{XP_j'}$, where $P_i',P_j'$ are the antipodes of $P_i,P_j$, so there are an equal number of intersections on segment $\overline{XP_i}$ and $\overline{XP_j}$, and the symmetric fact also applies. Thus if our $\ell_i$ and $\ell_j$ frogs both start on the $P_iP_j$ side of $X$, they will occupy $X$ at the same time, and the same is true if they both start on the $P_i'P_j'$ side. Thus they must start on "opposite" sides of $X$. If $n$ is even, then pick some intersection point $P$ on the circle such that the frog starts on the "$P$ side" of its line. For parity reasons, we can find that when we reach the antipode $P'$ of the circle, we find that the frog must start on the "$P'$ side" of its line—but it's the same line, so we arrive at a contradiction. If $n$ is odd, this parity issue will not apply, so we can go around the circle and alternate between "frog starts on this side" and "frog starts on the opposite side". Call former intersection points froggy. Thus between any two froggy points $P_i$ and $P_j$ with antipodes $P_i'$ and $P_j'$ corresponding to lines $\ell_i$ and $\ell_j$ (picking the minor arc), there are an odd number of other points (which may be froggy or not). Every line corresponding to one of these points must intersect $\ell_i$ and $\ell_j$ on "opposite" sides of $\ell_i \cap \ell_j:=X$, i.e. either $XP_i$ and $XP_j'$ or $XP_i'$ and $XP_j$, and every other line must intersect on the "same side", i.e. either $XP_i$ and $XP_j$ or $XP_i'$ and $XP_j'$. Thus the parity of intersection points along $XP_i$ must be different from that of $XP_j$, so the $\ell_i$ and $\ell_j$ frogs will not occupy $X$ at the same time. Since this applies for any froggy points, it follows that Geoff's wish will be fulfilled for $n$ odd with this method. $\blacksquare$

Okay guys, for the first part I have come up with a construction different from any of the above. Please let me know whether it is right or not. Consider far enough line $l$ intersecting with all of the given lines (we could extend the segments to lines). We could add an another statement such that all the intersection points are above the line $l$. We will place the frogs just like shown in the picture. We will count the intersection numbers from $A_{1},A_{2},A_{3}...,A_{n}$. It is sufficient to prove that for any $i,j$ lines: $(1)$ the intersection numbers cannot be the same if $i = j(mod 2)$. $(2)$ the sum of the intersection numbers cannot be equal to $n$ if $i - j = 1(mod 2)$. Then it can be shown that for any $i<k<j$ the $k-th$ line would be intersecting $l$ and exactly one of the sides formed by the lines $i,j$ and $l$. For $(1)$ it is obvious that there is an odd number of lines between $i$ and $j$ so it is impossible to be equal. For $(2)$ it is obvious that there is an even number of lines between $i$ and $j$ so again, it is impossible to be equal to n which is an odd number.

Solved this in my summer day-care program on the 2016 IMO.

One of my favorite combo problems ever Solved with 10% hint The key is to characterize the configuration as follows: Extend the segments to lie on a circle, with all intersection points inside (note that no new intersection points are formed). Then, assigning the points clockwise 0 and 1, Geoff can assign frogs iff the numbers alternate; in particular, if n is odd, the setup is possible, while if n is even, it is not. WLOG all frogs start on the circle on the endpoints of the segment, since next move they move to the first intersection point; our claim immediately implies the wanted result. $\textbf{\textit{Proof.}}$ Note that for any two points A,B on the circle, if C lies in the minor arcs formed between the chords that pass through A,B, then any chord through C passes through exactly 1 of AD,BD, where D is the intersection of those two chords; the analogous is true if C lies outside, it intersects either 0 or 2 of AD,BD. If A and B are consecutive endpoints with WLOG value 0, the frogs starting at A,B will meet at C, since the points the frogs move on are bijected. For the converse, on an arc AB, there are an odd number of points, meaning there are a total of odd number of intersection points on AD,BD (since outside it is 0 mod 2 total, but inside there's an odd number of 1 mod 2). Then, the point D has different parity on AC,BC (where parity is looked at based on what \#th point it is from the center), meaning the frogs don't meet there. This applies globally, and we're done. $\blacksquare$ $\textbf{Remark.}$ The circle extension is well motivated once you see that starting outside the segment, the intersection point D has different parity based on parity of \# of consecutive points ``between" A and B.

Nice problem Solved with cursed_tangent1434. Part (a) Pick some specific line $\ell_1$ such that when oriented horizontally, all intersection occur either above $\ell_1$ or below $\ell_1$. Let the other lines be $\ell_2$, $\ell_3$ and so on in the order that they hit $\ell_1$, from left to right. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -15.873936225323025, xmax = 24.301883969858583, ymin = -14.968254684535735, ymax = 17.37862715266697; /* image dimensions */ pen qqwwzz = rgb(0,0.4,0.6); pen ccwwqq = rgb(0.8,0.4,0); pen cczzqq = rgb(0.8,0.6,0); pen ccqqqq = rgb(0.8,0,0); pen ubqqys = rgb(0.29411764705882354,0,0.5098039215686274); /* draw figures */ draw((-12.393068428802376,0.6195225067150139)--(18.594174100450196,0.4328953407652548), linewidth(0.7) + qqwwzz); draw((1.1029677458066007,9.611414664927114)--(-5.004947755726555,-7.164993239747905), linewidth(0.7) + ccwwqq); draw((-3.765677273710931,8.4773341661935)--(3.9533283131887402,-6.106287886540258), linewidth(0.7) + cczzqq); draw((-10.043825766852592,-1.4056866838722253)--(5.6717975579149185,4.993974358383451), linewidth(0.7) + ccqqqq); draw((15.680526076132399,-5.699093519921933)--(-5.547861362086628,7.586242122335117), linewidth(0.7) + ubqqys); /* dots and labels */ dot((-12.393068428802376,0.6195225067150139),dotstyle); dot((18.594174100450196,0.4328953407652548),dotstyle); dot((1.1029677458066007,9.611414664927114),dotstyle); dot((-5.004947755726555,-7.164993239747905),dotstyle); dot((-3.765677273710931,8.4773341661935),dotstyle); dot((3.9533283131887402,-6.106287886540258),dotstyle); dot((-10.043825766852592,-1.4056866838722253),dotstyle); dot((5.6717975579149185,4.993974358383451),dotstyle); dot((15.680526076132399,-5.699093519921933),dotstyle); dot((-5.547861362086628,7.586242122335117),dotstyle); dot((-5.177248823813003,0.5760637200348956),linewidth(4pt) + dotstyle); dot((-2.193145120167162,0.5580913297331168),linewidth(4pt) + dotstyle); dot((0.43429633156186653,0.542267012633194),linewidth(4pt) + dotstyle); dot((5.758814607419054,0.5101989848010029),linewidth(4pt) + dotstyle); dot((-1.6660346667728456,2.005888041187548),linewidth(4pt) + dotstyle); dot((-0.5754489726422742,2.4499925247156957),linewidth(4pt) + dotstyle); dot((-1.1257901637792933,3.489759608861208),linewidth(4pt) + dotstyle); dot((-0.7317130922894169,4.572157964819876),linewidth(4pt) + dotstyle); dot((1.3841658895884281,3.2479800198651168),linewidth(4pt) + dotstyle); dot((-2.177661243607318,5.477073920752279),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] An example for $n = 5$ is depicted, with $\ell_1$ being blue, $\ell_2$ being red, $\ell_3$ being orange, $\ell_4$ being yellow and $\ell_5$ being purple. Now note that $\ell_1$ splits each $\ell_i$ into two parts, one with an even number of points and one with an odd number of points as depicted in the picture. Then place the frogs $f_i$ as follows. Place $f_1$ on $\ell_1$, at the left endpoint. Place $f_{2k}$ on the endpoint of $\ell_{2k}$ lying on the side with an even number of points, for all $k$. In the case of the diagram for $k = 1$ we would place $f_2$ on the higher endpoint of $\ell_2$. Place $f_{2k+1}$ on the endpoint of $\ell_{2k+1}$ lying on the side with an odd number of points for all $k$. In the case of the diagram for $k = 1$, we would place $f_3$ on the lower endpoint of $\ell_3$. The completed diagram for $n = 5$ would then be, [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -15.56124205000165, xmax = 22.636334344952633, ymin = -14.270373831900477, ymax = 16.483758482324067; /* image dimensions */ pen qqwwzz = rgb(0,0.4,0.6); pen ccwwqq = rgb(0.8,0.4,0); pen cczzqq = rgb(0.8,0.6,0); pen ccqqqq = rgb(0.8,0,0); pen ubqqys = rgb(0.29411764705882354,0,0.5098039215686274); /* draw figures */ draw((-12.393068428802376,0.6195225067150139)--(18.594174100450196,0.4328953407652548), linewidth(0.7) + qqwwzz); draw((1.1029677458066007,9.611414664927114)--(-5.004947755726555,-7.164993239747905), linewidth(0.7) + ccwwqq); draw((-3.765677273710931,8.4773341661935)--(3.9533283131887402,-6.106287886540258), linewidth(0.7) + cczzqq); draw((-10.043825766852592,-1.4056866838722253)--(5.6717975579149185,4.993974358383451), linewidth(0.7) + ccqqqq); draw((15.680526076132399,-5.699093519921933)--(-5.547861362086628,7.586242122335117), linewidth(0.7) + ubqqys); /* dots and labels */ dot((-12.393068428802376,0.6195225067150139),dotstyle); label("$F_1$", (-15.600529953682704,0.6528237845650339), NE * labelscalefactor); dot((18.594174100450196,0.4328953407652548),dotstyle); dot((1.1029677458066007,9.611414664927114),dotstyle); dot((-5.004947755726555,-7.164993239747905),dotstyle); label("$F_3$", (-4.430896219020429,-8.170380645608006), NE * labelscalefactor); dot((-3.765677273710931,8.4773341661935),dotstyle); label("$F_4$", (-4.41423068759579,9.258171315227628), NE * labelscalefactor); dot((3.9533283131887402,-6.106287886540258),dotstyle); dot((-10.043825766852592,-1.4056866838722253),dotstyle); dot((5.6717975579149185,4.993974358383451),dotstyle); label("$F_2$", (6.333376358893249,5.1188902245291645), NE * labelscalefactor); dot((15.680526076132399,-5.699093519921933),dotstyle); label("$F_5$", (16.06431787395765,-6.35490648302096), NE * labelscalefactor); dot((-5.547861362086628,7.586242122335117),dotstyle); dot((-5.177248823813003,0.5760637200348956),linewidth(4pt) + dotstyle); dot((-2.193145120167162,0.5580913297331168),linewidth(4pt) + dotstyle); dot((0.43429633156186653,0.542267012633194),linewidth(4pt) + dotstyle); dot((5.758814607419054,0.5101989848010029),linewidth(4pt) + dotstyle); dot((-1.6660346667728456,2.005888041187548),linewidth(4pt) + dotstyle); dot((-0.5754489726422742,2.4499925247156957),linewidth(4pt) + dotstyle); dot((-1.1257901637792933,3.489759608861208),linewidth(4pt) + dotstyle); dot((-0.7317130922894169,4.572157964819876),linewidth(4pt) + dotstyle); dot((1.3841658895884281,3.2479800198651168),linewidth(4pt) + dotstyle); dot((-2.177661243607318,5.477073920752279),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] To see that this algorithm works consider any two frogs $F_i$ and $F_j$. It suffices to show that they will never meet. We first show that this must hold when $i = 1$. Indeed note that this follows from a simple parity argument. Now take cases. Say $i$ and $j$ are both even. Note that then $F_i$ and $F_j$ both lie above $\ell_1$. Moreover by construction there is an odd number of lines, specifically $\ell_{i+1}$, $\ell_{i+2}$, $\dots$, $\ell_{j-2}$, $\ell_{j-1}$ lying ``between" $\ell_i$ and $\ell_j$. Call these lines special. For example, $\ell_3$ is special with regards to $\ell_2$ and $\ell_4$. Now denote $K$ the intersection points of $\ell_i$ and $\ell_j$. Note that each of the special lines intersects $F_i$ and $F_j$ such that the without loss of generality the number of points between $F_i$ and $K$ increases by one, while the number of points between $F_j$ and $K$ stays constant. Thus the parity of the number of jumps either $F_i$ takes to reach $K$ or $F_j$ takes to reach $K$ changes after adding each special line. As we add an odd number of special lines, it is obvious that the parity of the number of jumps $F_i$ takes to reach $K$ is different than the parity of the number of jumps that $F_j$ takes to reach $K$, and so they will never meet. Note that we may ignore lines not lying between $\ell_i$ and $\ell_j$, such as $\ell_5$ in our diagram, as they either increase the parity of both with regards to number of jumps, or do not change either. A worked example in our case: Working with $F_2$ and $F_4$ we find that $\ell_3$ increases the number of jumps $F_4$ must take to reach $K$, whereas it does not change the number of moves $F_2$ will take. Similarly $\ell_5$ increments the number of jumps both $F_2$ and $F_4$ must take, by $1$. Then $F_2$ requires $2$ move to reach $K$, while $F_4$ requires $3$ moves to reach $K$. Now for $i$ and $j$ odd note that a similar argument functions. There are an odd number of special lines, each of them function the same way as for the $i$, $j$ even case leading to the same contradiction. Finally for the $i$ even and $j$ odd case note that there are an even number of special lines. However, $\ell_1$ forces a parity switch. Namely, $F_i$ and $F_j$ take a different parity of jumps to reach $K$, prior to the addition of any special lines. Each of the special lines changes the parity of exactly $F_i$ or $F_j$. However as there are an even number of special lines, the special lines do not affect the parity. Thus $F_i$ and $F_j$ take a different parity number of jumps to reach $K$ as desired. $\square$ Part (b) Now it suffices to show that even $n$ fail. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -18.29144778672648, xmax = 24.081698815583906, ymin = -13.525421330638132, ymax = 20.590600683512953; /* image dimensions */ pen qqwwzz = rgb(0,0.4,0.6); pen ccqqqq = rgb(0.8,0,0); /* draw figures */ draw((-13.637286141956421,0.7963418858563729)--(19.6813790229995,0.6438537158214208), linewidth(0.7) + qqwwzz); draw((1.1029677458066007,9.611414664927114)--(-5.004947755726555,-7.164993239747905), linewidth(0.7) + qqwwzz); draw((-3.765677273710931,8.4773341661935)--(3.9533283131887402,-6.106287886540258), linewidth(0.7) + qqwwzz); draw((-15.287468493282208,-3.543802093833024)--(5.6717975579149185,4.993974358383451), linewidth(0.7) + ccqqqq); draw((15.680526076132399,-5.699093519921933)--(-5.547861362086628,7.586242122335117), linewidth(0.7) + qqwwzz); draw((-15.026678703103611,-2.1529232133947547)--(21.81621340427814,1.5587827360311337), linewidth(0.7) + ccqqqq); /* dots and labels */ dot((-13.637286141956421,0.7963418858563729),dotstyle); dot((19.6813790229995,0.6438537158214208),dotstyle); dot((1.1029677458066007,9.611414664927114),dotstyle); dot((-5.004947755726555,-7.164993239747905),dotstyle); dot((-3.765677273710931,8.4773341661935),dotstyle); dot((3.9533283131887402,-6.106287886540258),dotstyle); dot((-15.287468493282208,-3.543802093833024),dotstyle); dot((5.6717975579149185,4.993974358383451),dotstyle); dot((15.680526076132399,-5.699093519921933),dotstyle); dot((-5.547861362086628,7.586242122335117),dotstyle); dot((-4.732952479956262,0.7555897867318513),linewidth(4pt) + dotstyle); dot((-2.12558489275113,0.7436567543005418),linewidth(4pt) + dotstyle); dot((0.3336594541460973,0.7324016314356083),linewidth(4pt) + dotstyle); dot((5.441111766411409,0.709026563653563),linewidth(4pt) + dotstyle); dot((-1.6664563459169084,2.004729829138951),linewidth(4pt) + dotstyle); dot((-0.5750832984816489,2.449301651559435),linewidth(4pt) + dotstyle); dot((-1.1257901637792933,3.489759608861208),linewidth(4pt) + dotstyle); dot((-0.7317130922894169,4.572157964819876),linewidth(4pt) + dotstyle); dot((1.3847237747272647,3.247630879293755),linewidth(4pt) + dotstyle); dot((-2.177661243607318,5.477073920752279),linewidth(4pt) + dotstyle); dot((-15.026678703103611,-2.1529232133947547),dotstyle); dot((21.81621340427814,1.5587827360311337),dotstyle); dot((6.5420880631239315,0.020003919867569754),linewidth(4pt) + dotstyle); dot((13.036377645598954,0.6742656214275705),linewidth(4pt) + dotstyle); dot((1.005931706290904,-0.5377314616740991),linewidth(4pt) + dotstyle); dot((-2.7291060445238267,-0.914014675288909),linewidth(4pt) + dotstyle); dot((-10.836797636901897,-1.7308171953470592),linewidth(4pt) + dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] An example for $n = 6$ is depicted. I will use the notion of consecutive chords later to refer to chords such as those colored in red. Assume that some configuration of frogs exist satisfying the problem condition. Consider coloring the endpoints of segments two colors say gold and green. Set each chord to have endpoints of different colors. Note that two ``consecutive" chords exists such that they have ``consecutive" endpoints of the same color. The key claim is that this cannot occur in any valid configuration. Indeed note that in any good arrangement, for any two consecutive chords, their frogs always start on the same color. However this is a clear contradiction. $\square$ Remarks: I found (a) to be pretty quick, simply checking $n = 5$ sufficed. However the argument in (b) was a lot more painful to find. I initially tried a parity argument, but that didn't work because of our lack of control over the actual arrangement of the lines. This motivated looking at more cases, and I eventually noticed that frogs always alternate the endpoints they begin at, which sufficed. The reason the argument in (b) fails for odd $n$ is because we have an odd number of lines, and hence never have two adjacent chords with consecutive colors.

Put the endpoints of the segments in angular order (there are $2n$) and consider two adjacent endpoints, $A$ and $B$. Let the lines they belong to intersect at $P$. Note that any line that intersects segment $PA$ must intersect segment $PB$ so frogs placed on $A$ and $B$ are equal distance away from $P$. Therefore, $A$ and $B$ cannot both have frogs. On the other hand, if there are two endpoints with one more in between there exists one line that must intersect $PA$ or $PB$ but not both so $A$ and $B$ will always be different distance away from $P$. If $n$ is odd, we can take every other endpoint, and if $n$ is even avoiding choosing adjacent endpoints forces us to choose endpoints of the same line.

Construct a circle that contains all intersections and extend the line segments so that each segment is a chord on the circle. Then the problem can be rewritten so that $V_1, V_2, \dots, V_{2n}$(cyclic modulo $2n$) are varying vertices on a circle and $V_iV_{i+n}$ are the chords. Clearly each chord intersects all other chords. Color a vertex green if it contains a frog, and yellow if it doesn't. We first claim that if there are two directly adjacent green vertices $V_g$ and $V_{g+1}$, we will not satisfy Geoff's condition. Let $V_gV_{g+n} \cap V_{g+1}V_{g+n+1} = G$. Clearly the intersections of any chord passing through $V_gV_{g+n}$ and $V_{g+1}V_{g+n+1}$ must be on the same side of $G$, otherwise we have that one of the endpoints of the chord is on minor arcs $V_gV_{g+1}$ or $V_{g+n}V_{g+1+n}$, which contradicts the adjacent-ness. So then it follows that the number of intersection points on $V_gG$ is the same as $V_{g+1}G$ so the two frogs on the chords will land on $G$ at the same time, which is invalid. It follows that every other endpoint on the circle must be green. However if $n$ is even then we will end up with a chord having two green endpoints, absurd. We now follow with proving that all $n$ odd work, by showing that alternating green and yellow vertices works. First we will show that the chords $V_{i}V_{i+n}$ and $V_{i+2m}V_{2m + n}$(once again concurring at $G$) will not have their frogs run into each other. This is done by showing that the difference in parity of the number of intersection points from $V_i$ to $G$ with $V_{i+2m}$ to $G$ is $1$. Clearly there is an odd number of vertices strictly between $V_{i}$ and $V_{i+2m}$, and each of them adds one intersection point on one of the segments $V_iG$ and $V_{i+2m}G$. The rest of the lines that don't have endpoints on minor arc $V_iV_{2m}$ do not change the difference in parity as we have shown earlier, so we are done. Analogously, the difference of parity with segments $V_iG$ and $V_{i+2m+1}$ is even, however $V_{i+2m+1}$ is yellow, and similarly from before we get that the chords with green endpoints $V_i$ and $V_{i+2m+1+n}$ cannot have concurrent frogs, so we're done.

$ $ (Failed to solve; below is OTIS sol)

I got the idea in <10 min, but it took a long time to formalize everything Extend each segment such that each of the endpoints are on a circle (This obviously will not affect anything as the segments are already intersecting each other and it is impossible for two segments to intersect each other twice). Then we can say that two endpoints are adjacent if they are neighboring each other on the circle. We begin by first proving a claim: $\text{Claim 1: }$ Suppose that the endpoints are filled in an alternating pattern. Then if $n$ is even, there are segments with frogs on both of their endpoints, while if $n$ is odd, there are no segments with frogs on both of their endpoints. $\text{Proof: }$ Consider a segment with a frog on its endpoint. Then since every other segment intersects this segment once, there are $\frac{2n-2}{2}=n-1$ endpoints on either side of this segment. If $n$ is even, this number is odd, but since the pattern of frogs is alternating, it follows that the other endpoint of our segment also has a frog. Meanwhile, if $n$ is odd, then $n-1$ is even, so it is impossible for the other endpoint of our segment to also have a frog. $\boxed{}$ (a) Suppose that $n$ is odd. We claim that Geoff can fulfill his wish if he makes the endpoints alternating with frogs/no frogs. By Claim 1, each segment will have exactly one frog. It now suffices to show that no two frogs will ever occupy the same point at the same time. Suppose we had frogs sitting on adjacent points $A$ and $B,$ with corresponding line segments intersecting at $P.$ If there are $k$ endpoints between $A$ and $B,$ clearly $k$ is odd. Then there are $k$ segments "coming out" from the region bounded by arc $AB,$ segment $AP,$ and segment $BP.$ (no two points in between $AB$ can be connected by a segment, as then that segment will not intersect with $AB$). Each of these segments either intersect $AP$ or $BP,$ but because $k$ is odd one of $AP, BP$ will contain an odd amount of intersection points while the other will contain an even amount, hence the number of intersection points is different. Therefore, the frogs will never meet at $P,$ so our construction is valid. (b) Suppose now that $n$ is even. We first show the following claim: $\text{Claim 2: }$ No two adjacent endpoints can have a frog. $\text{Proof: }$ For the sake of a contradiction, assume otherwise: Consider two frogs on adjacent points $A, B.$ Let the segments they lie on be $AA', BB'$ respectively, and suppose that $P$ is their point of intersection. If we had a line segment passing through $BP,$ $A'P,$ this contradicts the assumption that $A$ and $B$ are adjacent. This logic also applies to if the line segment passes through $AP, B'P$ too, so both of these cases are impossible. Therefore, we can only have line segments either intersecting our two segments at $(AP, BP),$ or $(B'P, A'P).$ Hence, the number of points of intersection on $AP$ and $BP$ are equal, so the frogs will eventually occupy $P$ at the same time, a contradiction. $\boxed{}$ Therefore, if $n$ is even Geoff must fill the endpoints in an alternating pattern. But by Claim 1, this is impossible. QED