Problem 1854

A path $OX_1\ldots X_{k-1}A$ is suitable if it is a shortest allowed path from $O$ to $A$ and $X_1A \le X_1B$. Similarly, a path $OY_1\ldots Y_{k-1}B$ is suitable if it is the shortest allowed path from $O$ to $B$ and $Y_1B \le Y_1A$. 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 $OK_1A$ and $OK_2B$, whereas $K_1A > K_1B$ and $K_2B > K_2A$, 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_1A \le K_1B$ (can change $A$ and $B$). If $OK_1A$ is a shortest path from point $O$ to point $A$, then it is suitable. Otherwise, $OL_1A$ is the only shortest path from point $O$ to point $A$. It is suitable if $L_1A \le L_1B$. Let us further assume that $L_1A > L_1B$. If $OL_1B$ is a shortest path from point $O$ to point $B$, then it is suitable. Otherwise, $OK_1B$ is the only shortest path from point $O$ to point $B$. Then $OL_1 + L_1A + OK_1 + K_1B < OK_1 + K_1A + OL_1 + L_1B$. This simplifies to $K_1B + L_1A < K_1A + L_1B$. However, adding the inequalities $K_1B \ge K_1A$ and $L_1A > L_1B$ gives $K_1B + L_1A > K_1A + L_1B$. The contradiction shows that at least one suitable path from point $O$ to point $A$ or $B$ exists.