The answer is $1012$. To show that $k=1012$ works, suppose we are given $1012$ points $p_1,\ldots,p_{1012}$, and WLOG let them be permuted such that the distance $p_1p_{1012}:=D$ is maximal among all $p_ip_j$. Then we can create points $q_1,\ldots,q_{1011}$ such that $q_ip_i$ and $q_ip_{i+1}$ have length $D$ for all $1 \leq i \leq 1011$, since $p_ip_{i+1} \leq 2D$, and the arrangement $p_1,q_1,p_2,\ldots$ works. To show that $k=1013$ fails, place $1013$ points $p_0,\ldots,p_{1012}$ on the $x$-axis at coordinates $0,1,9999+1,9999^2+9999+1,9999^3+9999^2+9999+1,\ldots$ respectively and color them red. Note that the distance $p_ip_{i+1}$ is equal to $9999^i$. If we could add $1010$ blue points to create a carioca sequence, then this carioca sequence would have to contain two consecutive red points, say $p_i$ and $p_j$ where $i<j$. If $j<1012$, then $p_ip_j$ has length at most $2\cdot 9999^{1010}$. But then we need at least $4999$ points to cover the distance between $p_{1012}$ to the closest $p_i$ in the permutation of the $2023$ points that satisfies the equal length property (since $p_ip_{1012}\geq 9999^{1011}$), and this is too many. Otherwise, the common distance is at least $9999^{1011}$. This is greater than $p_0p_{1011}$, so we cannot have any other red points adjacent to each other. But then we clearly need at least $1011$ blue points to be placed in between red points, which is still too many. $\blacksquare$

My problem! IAmTheHazard wrote: To show that $k=1012$ works, suppose we are given $1012$ points $p_1,\ldots,p_{1012}$. Suppose that the distance of the segment $p_ip_{i+1}$ is at most $D>0$. Then we can clearly pick some arbitrary $C>D$ and create points $q_1,\ldots,q_{1011}$ such that for all $1 \leq i \leq 1011$, the segments $p_iq_i$ and $p_{i+1}q_i$ is exactly $C$. I don't think this works exactly as presented - the permutation of the points that you are considering is then $p_1,q_1,p_2,q_2,\ldots, p_{1011},q_{1011},p_{1012}$, I suppose? But then you would need the distance $p_1p_{1012}$ to also equal $C$, which does not necessarily hold.

nunoarala wrote: My problem! IAmTheHazard wrote: To show that $k=1012$ works, suppose we are given $1012$ points $p_1,\ldots,p_{1012}$. Suppose that the distance of the segment $p_ip_{i+1}$ is at most $D>0$. Then we can clearly pick some arbitrary $C>D$ and create points $q_1,\ldots,q_{1011}$ such that for all $1 \leq i \leq 1011$, the segments $p_iq_i$ and $p_{i+1}q_i$ is exactly $C$. I don't think this works exactly as presented - the permutation of the points that you are considering is then $p_1,q_1,p_2,q_2,\ldots, p_{1011},q_{1011},p_{1012}$, I suppose? But then you would need the distance $p_1p_{1012}$ to also equal $C$, which does not necessarily hold. whoops. READ! READ! READ!

To show that $1013$ does not work I think it also suffices to consider on the real line points $2^0,2^1,2^2,\dots,2^{1012}$. It is easy to prove that no two pairs of them are ends of segments of equal length, but if $1013$ points are given this means that $2026$ ends of segments are known and the remaining $2020$ ends of segments are to be determined (by the $1010$ points to be added). Thus at least $3$ out of the $2023$ segments must have both endpoints in the original $1013$ points and those at least $3$ segments must have the same length, which is impossible for the chosen initial $1013$ points.

Another way to prove that $1013$ does not work (which is the way I did it on the exam) is to consider $1012$ equal points $A$ and a different point $B$. Then, since we have $2023$ points and $1012$ of 'em are $A$, then in the segments $P_{a_1}P_{a_2}, ..., P_{a_n}P_{a_1}$ there exists a segment connecting $A$ with $A$... which means that our common distance was $0$ but this implies that all our $2023$ points are the same which in turn contradicts the fact that $A \neq B$.

Claim 1 $k<1013$ Proof Suppose we had $k=1013$. Choose the configuration with 1012 points on a single point (call it $A$) and one placed randomly anywhere but on $A$. Then, whatever $2023-1013=1010$ points we choose, we have $2023$ segments, but since every point on $A$ is paired with another point we must have $1012\leq 1011$ which is false. Thus, this implies that the common distance is 0, but since we chose one point which is not on $A$, this leads to a contradiction. To see that effectively $k=1012$ works, simply connect the points in a way such that they create a poligon. Then, denote the segment with largest distance as $x$. Now choose the 1011 in a way such that on every segment that isn't $x$, we choose a point on the perpendicular bisector such that the distances between the points is the distance of the segment $x$.