IMO Team Selection Contest

A path $O{X}_1\dots X_{k-1}A$ is suitable if it is a shortest allowed path from $O$ to $A$ and $X_{1}A\le X_{1}B$. Similarly, a path $O{Y}_1\dots Y_{k-1}B$ is suitable if it is the shortest allowed path from $O$ to $B$ and $Y_{1}B\le Y_{1}A$. Let us show that for $n=2$ it is possible to choose points $A$, $B$, $O$, $K_1$, $L_1$, $K_2$, $L_2$ such that no shortest path from point $O$ to point $A$, nor one from point $O$ to point $B$ is suitable. Take $A=(2;2)$, $B=(-2;-2)$, $K_1=(-2;1)$, $L_1=(5;1)$, $K_2=(2;-1)$, and $L_2=(-5;-1)$ (Fig. 43).

If $O=(0;0)$, then the only shortest paths from point $O$ to points $A$ and $B$ are respectively $O{K}_{1}A$ and $O{K}_{2}B$, whereas $K_{1}A>K_{1}B$ and $K_{2}B>K_{2}A$, and hence they are not suitable. The collinearity of three points can be avoided by shifting $O$ slightly while leaving the situation unchanged.

We will show that for $n=1$ there exists at least one suitable path from point $O$ to point $A$ or point $B$. If the segment $OA$ or segment $OB$ does not contain any red points, then it is suitable. Therefore, assume that both segments $OA$ and $OB$ contain red points. W.l.o.g., $K_{1}A\le K_{1}B$ (can change $A$ and $B$). If $O{K}_{1}A$ is a shortest path from point $O$ to point $A$, then it is suitable. Otherwise, $O{L}_{1}A$ is the only shortest path from point $O$ to point $A$. It is suitable if $L_{1}A\le L_{1}B$. Let us further assume that $L_{1}A>L_{1}B$. If $O{L}_{1}B$ is a shortest path from point $O$ to point $B$, then it is suitable. Otherwise, $O{K}_{1}B$ is the only shortest path from point $O$ to point $B$. Then $O{L}_1+L_{1}A+O{K}_1+K_{1}B<O{K}_1+K_{1}A+O{L}_1+L_{1}B$. This simplifies to $K_{1}B+L_{1}A<K_{1}A+L_{1}B$. However, adding the inequalities $K_{1}B\ge K_{1}A$ and $L_{1}A>L_{1}B$ gives $K_{1}B+L_{1}A>K_{1}A+L_{1}B$. The contradiction shows that at least one suitable path from point $O$ to point $A$ or $B$ exists.