IMO 3J, Independent Study 2

Consider the $n$ Jujutsushis as $n$ points $A_1, \dots, A_n$, color each point according to its school, and for all $1 \le i < j \le n$, connect $A_iA_j$ with an edge colored with the color of $A_i$. We first prove the following key lemma.

Lemma: For the $i$-th color, there exists $1 \le p \le n$ such that among $A_1, A_2, \dots, A_p$, the number of points of color $i$ is more than $p/2$.

Proof: If not, then there exists $i$ such that for all $1 \le p \le n$, among the first $p$ points there are at most $\lfloor p/2 \rfloor$ points of color $i$. Let $A_{x_1}, A_{x_2}, \dots, A_{x_t}$ be all the points of color $i$, and $A_{y_1}, A_{y_2}, \dots, A_{y_s}$ be all the points not of color $i$, where $x_1 < x_2 < \dots < x_t$, $y_1 < y_2 < \dots < y_s$. Clearly $s + t = n$, and by the assumption for contradiction $t \le \lfloor p/2 \rfloor$. Moreover, note that for $1 \le j \le t$, if $y_j \ge x_j$, then $A_1, A_2, \dots, A_{x_j}$ would have $j$ points of color $i$ and fewer than $j$ points not of color $i$, contradicting the assumption for contradiction, so we must have $y_j < x_j$. But then,
$$A_{x_1}A_{y_1}, A_{y_1x_2}, A_{x_2y_2}, A_{y_2x_3}, \dots, A_{x_ty_t}, A_{y_ty_{t+1}}, \dots, A_{y_{s-1}y_s}$$
would contain no edge of color $i$, a contradiction. Hence the original statement holds.

Now, for the $i$-th color, let $p_i$ be the smallest $p$ satisfying the lemma. Note that for $i \ne j$, if among the first $p_i$ points more than half are of color $i$, then it is impossible for more than half to be of color $j$, so $p_i \ne p_j$, hence we may assume without loss of generality that
$$p_1 < p_2 < \dots < p_k.$$
At this point, when $i \le j$, among the first $p_i$ points there are at least $\lfloor (p_i + 1)/2 \rfloor$ points of color $i$, and hence among the first $p_j$ points there are at least $\lfloor (p_i + 1)/2 \rfloor$ points of color $i$. This means
$$p_j \ge \text{the number of points of the first } j \text{ colors among the first } p_j \text{ points} \ge \sum_{i=1}^{j} \lfloor (p_i + 1)/2 \rfloor.$$
The above can be used recursively to show $p_i \ge 2^i - 1$, and hence $n \ge p_k \ge 2^k - 1$.

Finally, we only need to prove $n \ne 2^k - 1$. If $n = 2^k - 1$, all the equalities above must hold, that is, $p_i = 2^i - 1$ and there are exactly $2^{i-1}$ points of color $i$. But note that the number of points of the first $i-1$ colors is
$$\sum_{j=1}^{i-1} 2^j = 2^{i-1} - 1 = p_{i-1}$$
so all the points of color $i$ can only be the $2^i$ points from $A_{p_{i-1}+1}$ to $A_{p_i}$. But then
$$A_{p_{k-1}+1}A_{p_1}, A_{p_1}A_{p_{k-1}+2}, A_{p_{k-1}+2}A_2, A_2A_{p_{k-1}+3}, \dots, A_{p_{k-1}}A_{p_k}$$
would contain no color $k$, a contradiction. Hence $n \ge 2^k$.