The answer is $n$ even. If $n$ is even, let $P$ and $Q$ be the points very close to perpendicular diameters of a circle with radius $0.6$, so $P_iP_{i+1}\geq1.2-\varepsilon>1$ and $P_iQ_j\leq\frac{1.2}{\sqrt2}+\varepsilon<1$. If $n$ is odd, $Q$ must be in the intersection of the circles with radius $1$ centered at $P_1$ and $P_2$, but then the points $Q$ must alternate which side of $P_1P_2$ the points are on, which is impossible since $n$ is even.

The answer is when $n$ is even. When $n$ is even, take a square $ABCD$ with side length 0.9. Put all odd $P$ points sufficently close to $A$, even $P$ points sufficently close to $C$, odd $Q$ sufficently close to $B$ and even $Q$ sufficently close to $D$, respecting the fact that no three points are collinear. For $n$ odd, the main claim is the following. Claim: $P_iP_{i+1}$ and $Q_jQ_{j+1}$ intersect. Consider cases on the convex hull of the four points. Note that the two segments $P_iP_{i+1}$ and $Q_jQ_{j+1}$ must be the "top 2 longest" (ties allowed) out of the 6 since they are at least 1 while others are at most 1. Case 1: The convex hull is a triangle $ABC$, and $D$ is a point inside it. If the triangle is equilateral, then the top 2 are two sides of the triangle, which doesn't work since they share a vertex. Otherwise, WLOG $BC$ is the longest side tied by at most one other. Then, $BC$ is obviously one of the top 2. This forces the other top 2 to be $AD$. However, in $\triangle ABC$, the furthest point from $A$ is either $B$ or $C$, so at least one of $AC$ and $AB$ are longer than $AD$, contradiction (as this means $BC$ is also longer, so it isn't top 2). Case 2: The convex hull is a quadrilateral $ABCD$. Then, if either of the diagonals is the longest segment, then the other one must be the other diagonal, since they don't share endpoints, and they intersect as desired. Thus, we only need to dispel the case where a side of the quadrilateral is the longest. Suppose WLOG that $CD$ is the longest. We will now show that $AB$ cannot be in the top 2. Claim: $BD>AB$. Suppose FTSOC that $AB\geq BD$. Then, $$\angle ADC>\angle ADB\geq \angle DAB>\angle DAC,$$which means that $AC>CD$, contradiction since we know $CD$ is the longest. Similarly, $AC>AB$. Thus, $AB$ cannot possibly be in the top 2, contradiction. Thus, they intersect. This means that $P_i$ must changes sides of $Q_1Q_2$ every time, so $n$ is even.

Answer is iff $n$ is even. The construction for even $n$ is to take a square $ABCD$ with side length $0.9$ and place all points inside the square as follows: Points $P_1, P_3, \dots, P_{n-1}$ go arbritrarily close to $A$. Points $Q_1, Q_3, \dots, Q_{n-1}$ go arbritrarily close to $B$. Points $P_2, P_4, \dots, P_{n}$ go arbritrarily close to $C$. Points $Q_2, Q_4, \dots, Q_{n}$ go arbritrarily close to $D$. Proof that $n$ must be even: Let the unit circles (including their interior) centered at $Q_1$ and $Q_2$ be $\omega_1$ and $\omega_2$. Each point $P$ must lie in the intersection of $\omega_1$ and $\omega_2$. Clearly, there does not exist any pair of points $A$, $B$ for which: $A$ and $B$ lie in the intersection of $\omega_1$ and $\omega_2$. $A$ and $B$ lie on the same side of line $Q_1 Q_2$. $A$ and $B$ are distinct from $Q_1$ and $Q_2$. $AB \geq 1$. Hence, $P_i P_{i+1}$ intersects $Q_1 Q_2$ for all $i$. Since the sequence $P_1, P_2, \dots, P_n$ keeps switching across line $Q_1 Q_2$, it follows that $n$ is even.

By the way, the first condition is not necessary to show $n$ odd fails. I suppose it might help to motivate the construction for $n$ even, as one way to guarantee no three points are collinear is to place them all on a circle.

The answer if when $2 \mid n$ First, we claim that $P_i$ and $P_{i+1}$ should lie on different sides of $Q_1Q_2$. Draw two circles $\omega_1, \omega_2$ with the center of $Q_1,Q_2$ and a radius of $1$. Since $Q_1Q_2 \ge 1$, $Q_1$ does not lie inside $\omega_2$, and $Q_2$ does not lie inside $\omega_1$. Now, set $A,B$ the intersection of two circles and $C,D$ be the intersection of $Q_1Q_2$ and $\omega_2,\omega_1$. We assume that $P_1$ is more closer to $A$ than $B$. Since $P_1P_2 \ge 1$, if $P_2A \le P_2B$, $P_1P_2 \le AC < 1$, which is a contradiction. Hence, in the same way, $P_i$ and $P_{i+1}$ should lie on different sides of $Q_1Q_2$. If $2 \nmid n$, $P_1$ and $P_n$ should lie on the same side of $Q_1Q_2$, which cannot happen. Therefore, $n$ whould be even. It suffices to show the existence of such points exist in the plane. We can draw a circle $\Omega$ with radius of $r$, where $0.5 < r < \frac{1}{\sqrt{2}}$ Now, let two diameters, perpendicular, as $AB, CD$. When $P_{odd}$ are close to $A$, $P_{even}$ are close to $B$, $Q_{odd}$ are close to $C$, $Q_{even}$ are close to $D$ then they all satisfy the conditions.

The answer is even $n$. I will omit the construction because it is identical to the above ones. We now will prove that $n$ odd fails. Construct two unit circle with centers $Q_1, Q_2$ respectively. Now notice that all points $P_i$ must lie within the intersection of the two circles, and that the maximum area of the intersection will occur when $Q_1Q_2 = 1$, implying that the two unit circles pass through each other's center. Assume that this is the case. Split the intersection region into two equal parts by drawing the segment connecting $Q_1$ and $Q_2$ and color the two equal regions red and blue. A point $P_i$ cannot lie on the line connecting $Q_1$ and $Q_2$ as this will immediately imply $P_iP_{i+1} < 1$. If two points $P_i, P_j$ are of the same color then it is clear that $P_iP_j < 1$. If $P_1$ is blue, then $P_2$ is red, then $P_3$ is blue, on and on until we have $P_n$ is blue. Now $P_1$ and $P_n$ are of the same color implying that $P_1P_n < 1$, which is a contradiction.

It is nontrivial to prove that any two points in either side of $P_1P_2$ My proof is as following: For the largest area case, we have two $60^{\circ}$ arcs on a triangle of side length $1$. Let points $P_1$ and $P_2$ be the vertices of the straight line. Then, for $A$ and $B$ in the region, you need to prove $AB \le 1$. The proof for this is that $A$ and $B$ must be on sides, otherwise drawing line $AB$ gets a longer distance; given this then they must be on the arcs and not the straight line (otherwise, symmetry). Now, WLOG segments $P_1A$ and $P_2B$ intersect at $X$, then $XA + XB \ge AB$ and $XP_1 + XP_2 \ge P_1P_2 = 1$ and $XP_1 = 1-XA$, $XP_2=1-XB$, so $AB \le 2-(XP_1+XP_2) \le 1$. Remark: I believe a lot of people got points off for the reason of not properly proving this step. Remark 2: A proper Releaux citation would likely also suffice here.

DottedCaculator wrote: The answer is $n$ even. If $n$ is even, let $P$ and $Q$ be the points very close to perpendicular diameters of a circle with radius $0.6$, so $P_iP_{i+1}\geq1.2-\varepsilon>1$ and $P_iQ_j\leq\frac{1.2}{\sqrt2}+\varepsilon<1$. If $n$ is odd, $Q$ must be in the intersection of the circles with radius $1$ centered at $P_1$ and $P_2$, but then the points $Q$ must alternate which side of $P_1P_2$ the points are on, which is impossible since $n$ is even. Can you explain it more? I couldn't get it.

ike.chen wrote: By the way, the first condition is not necessary to show $n$ odd fails. I suppose it might help to motivate the construction for $n$ even, as one way to guarantee no three points are collinear is to place them all on a circle. I'm late, but my experience in contest was the exact opposite! For $n$ odd, having no three of the points collinear simplified the argument somewhat, removing a few cases that aren't difficult to deal with but annoying. For $n$ even, I first found the construction with points on a square, and had to think for quite some time before transferring it to a circle (my first thought was parabolic arcs for some reason...)

The answer is even $n$.

hi 170 371

Nice Problem : Sketch: For even $n$ basically alternate $P_i/Q_i$ in a tight zig-zag of suitable size with the $P_i$ and $Q_i$ zig-zag crossing. For odd $n$ use the triangle inequality to show that $Q_iQ_{i+1}$ has to intersect $P_jP_{j+1}$ and then force a parity contradiciton.