Problem 1098

We start with showing that for any $k \leqslant n^{2}-n$ there may be no pair of checkpoints linked by both companies. Clearly, it suffices to provide such an example for $k=n^{2}-n$. Let company $A$ connect the pairs of checkpoints of the form $(i, i+1)$, where $n \nmid i$. Then all pairs of checkpoints $(i, j)$ linked by $A$ satisfy $\lceil i / n\rceil=\lceil j / n\rceil$. Let company $B$ connect the pairs of the form $(i, i+n)$, where $1 \leqslant i \leqslant n^{2}-n$. Then pairs of checkpoints $(i, j)$ linked by $B$ satisfy $i \equiv j(\bmod n)$. Clearly, no pair $(i, j)$ satisfies both conditions, so there is no pair linked by both companies. Now we show that for $k=n^{2}-n+1$ there always exist two required checkpoints. Define an $A$-chain as a sequence of checkpoints $a_{1}<a_{2}<\ldots<a_{t}$ such that company $A$ connects $a_{i}$ with $a_{i+1}$ for all $1 \leqslant i \leqslant t-1$, but there is no $A$-car transferring from some checkpoint to $a_{1}$ and no $A$-car transferring from $a_{t}$ to any other checkpoint. Define $B$-chains similarly. Moving forth and back, one easily sees that any checkpoint is included in a unique $A$-chain (possibly consisting of that single checkpoint), as well as in a unique $B$-chain. Now, put each checkpoint into a correspondence to the pair of the $A$-chain and the $B$-chain it belongs to. All finishing points of $A$-cars are distinct, so there are $n^{2}-k=n-1$ checkpoints that are not such finishing points. Each of them is a starting point of a unique $A$-chain, so the number of $A$-chains is $n-1$. Similarly, the number of $B$-chains also equals $n-1$. Hence, there are $(n-1)^{2}$ pairs consisting of an $A$- and a $B$-chain. Therefore, two of the $n^{2}$ checkpoints correspond to the same pair, so that they belong to the same $A$-chain, as well as to the same $B$-chain. This means that they are linked by both companies, as required. Comment 1. The condition that the $i^{\text {th }}$ car starts and finishes lower than the $j^{\text {th }}$ one is used only in the "moving forth and back" argument and in the counting of starting points of the chains. In both cases, the following weaker assumption suffices: No two cars of the same company start at the same checkpoint, and no two such cars finish at the same checkpoint. Thus, the problem conditions could be weakened in this way, with no affect on the solution. Comment 2. If the number of checkpoints were $N$, then the answer would be $N-\lceil\sqrt{N}\rceil+1$. The solution above works verbatim for this generalization.