Japan Final Round, 2013

Let for $k = 1, 2, \dots, n$ $A_k = P_{4k-3}$, $B_k = P_{4k-2}$, $C_k = P_{4k-1}$, $D_k = P_{4k}$. Also, let $A_{n+1} = A_1$ and $B_{n+1} = B_1$. From now on let us say that the directed line segments $A_iB_i, B_iC_i, C_iD_i, D_iA_{i+1}$ are leftward, downward, rightward, upward segments, respectively. Furthermore, let us say a bent line segment $A_iB_iC_i$ is leftdown type for each $i = 1, 2, \dots, n$, and define similarly, downright, rightup, upleft type bent segments.

Then the point of intersection (different from their end-points) of a leftward segment and a downward segment can be regarded as the intersection of two leftdown type bent segments. The same statement can be made for intersections of other types of directed segments. Therefore, to get the answer to the problem, it suffices to find the maximum possible value for the sum of the number of intersections of two leftdown type bent segments, that of two downright bent segments, that of two rightup bent segments and that of two upleft bent segments.

Let us say the pair $(i, j)$ where $1 \le i \ne j \le n$ is a good pair if for all of the four pairs of bent segments $A_iB_iC_i$ and $A_jB_jC_j$, $B_iC_iD_i$ and $B_jC_jD_j$, $C_iD_iA_{i+1}$ and $C_jD_jA_{j+1}$, $D_iA_{i+1}B_i$ and $D_jA_{j+1}B_j$, two bent segments intersect each other.

We note that if $(i, j)$ is a good pair and if $A_i$ lies above $A_j$, then $B_i$ lies to the right of $B_j$, $C_i$ lies below $C_j$, $D_i$ lies to the left of $D_j$ and $A_{i+1}$ lies below $A_{j+1}$.

Lemma. For any non-empty proper subset $X$ of the set $\{1, 2, \dots, n\}$, let $Y = X^c$, the complement of $X$. Then, there exist $x \in X$ and $y \in Y$ such that the pair $(x, y)$ is not a good pair.

Proof. For $x \in \{1, 2, \dots, n\}$, let us define
$$x^+ = \begin{cases} x+1 & (\text{if } 1 \le x \le n-1) \\ 1 & (\text{if } x=n), \end{cases}$$
$$x^- = \begin{cases} x-1 & (\text{if } 2 \le x \le n) \\ n & (\text{if } x=1). \end{cases}$$
Now suppose for every choice of $x \in X$ and $y \in Y$ the pair $(x, y)$ is a good pair. Define $f(k) = i$ and $f^{-1}(i) = k$ if $A_k$ is located at the $i$-th position from the top among $A_1, A_2, \dots, A_n$. We show that for each $k, 1 \le k \le n$, the number of points among $f(1), f(2), \dots, f(k)$ which belong to $X$ and the number of points among $f(1)^-, f(2)^-, \dots, f(k)^-$ which belong to $X$ must coincide.

In order to show this, let us suppose the number for the former is larger than the number for the latter. Then, there exists $x \in X$ for which both $f^{-1}(x) \le k$ and $f^{-1}(x^+) > k$ hold. Furthermore, there must exist $y \in Y$ which satisfies both $f^{-1}(y) > k$ and $f^{-1}(y^+) \le k$, since the number of points in the set $\{f(k+1), f(k+2), \dots, f(n)\}$ which belong to $Y$ is more than the number of points in the set $\{f(k+1)^-, f(k+2)^-, \dots, f(n)^-\}$ which belong to $Y$. But this implies that the pair $(x, y)$ is not a good pair contradicting our assumption. Similarly, we arrive at a contradiction also if we assume that the number for the former case is smaller than the number for the latter. Therefore, we conclude that the number for the former equals the number for the latter.

By comparing this fact for the case $k = \ell$ and for the case $k = \ell - 1$, we arrive at the conclusion that
$$f(\ell) \in X \iff f(\ell)^- \in X.$$
This means that for any $x \in \{1, 2, \dots, n\}$ we have
$$x \in X \iff x^- \in X.$$
But this contradicts our assumption that $X$ is a non-empty proper subset of $\{1, 2, \dots, n\}$, and this proves the Lemma.

Now, in order to arrive at the answer to the problem, suppose that the number of $(x, y)$, which is not a good pair is at most $n-2$. Then, among the elements of $\{1, 2, \dots, n\}$, the number of those which can be reached from the element 1 by going through the string of not-good pairs can be at most $n-1$. So, let $X$ be the subset consisting of those elements accessible from 1 in this way and let $Y$ be the complement of $X$. Then, we arrive at a situation contradicting the conclusion of the Lemma. So, we must have at least $n-1$ not-good pairs among $\{1, 2, \dots, n\}$. Therefore, the maximum number of pairs $(i, j)$ satisfying the requirement of the problem is at most $4 \times {}_nC_2 - (n-1) = (2n-1)(n-1)$.

On the other hand, as indicated in the diagram below, if we start by placing $A_1, A_2, \dots, A_n$ in turn with $A_1$ at a left-top position and going down-right direction, and placing $C_n, C_{n-1}, \dots, C_1$ in turn with $C_n$ at a left-top position and going down-right direction, and finally placing $B_1, B_2, \dots, B_n$ and $D_1, D_2, \dots, D_n$ by following the rule specified in the problem, we can arrive at a situation where the number of relevant intersection points is exactly $(2n-1)(n-1)$. Therefore, the answer we seek for the problem is $(2n-1)(n-1)$.