$100$ red points divide a blue circle into $100$ arcs such that their lengths are all positive integers from $1$ to $100$ in an arbitrary order. Prove that there exist two perpendicular chords with red endpoints.
Problem
Source:
Tags: points, combinatorial geometry, combinatorics, circle
29.05.2021 05:39
Solution from Twitch Solves ISL: We will assume no two red points are diametrically opposite, otherwise, the problem is trivial. Claim: If there exist two intervals which have sum of lengths $2525$, and it is not the case that the intervals share an endpoint; and one interval contains the other then the problem is solved. Proof. If two of the endpoints coincide, but the intervals are disjoint, then we have diametrically opposite red points, a contradiction. So assume we have four distinct red points in play. If the intervals are disjoint, then we get two chords which are perpendicular inside the circle; if they are nested, we get two chords perpendicular outside the circle. $\blacksquare$ For every red point $R$, we define its two attached arcs to be the two maximal-by-inclusion arcs with endpoint $R$ and total length at most $2525$. See figure below with two attached arcs drawn. [asy][asy] dotfactor *= 2; size(6cm); draw(unitcircle); dot("$R$", dir(180), dir(45), red); label("$-R$", dir(0), dir(0)); dot(dir(0), grey); draw(arc(origin, dir(20)*1.1, dir(180)*1.1), deepgreen+1.4); draw(arc(origin, dir(180)*0.9, dir(330)*0.9), deepcyan+1.4); dot(dir(20), red); dot(dir(330), red); [/asy][/asy] Then, of these two, we pick the one with longest length and call it the main arc of $R$. A main arc $\Gamma$ always has length $2525-x$ for some $0 < x \le 50$. We refer to the given arc of length $x$ as the killer of $\Gamma$. Now, the problem is solved unless we are in a situation where for every main arc $\Gamma$, its killer is contained in $\Gamma$ and shares an endpoint with it. Claim: If there exists any main arc with $x=50$, we are done. Proof. It means the two attached arcs both have length exactly $2475$, and that the segment of length $100$ is split exactly by the antipode of $R$. So the segment of length $50$ can't be killers of both. $\blacksquare$ Claim: If any arc of length $x < 50$ is the killer of two different main arcs, we are done. Proof. If it was the killer of two attached arcs, then we have the following picture. [asy][asy] size(6cm); draw(unitcircle); draw(arc(origin, dir(80), dir(100)), red+1.8); draw(arc(origin, dir(80)*1.1, dir(240)*1.1), deepgreen+1.4); draw(arc(origin, dir(-60)*0.9, dir(100)*0.9), deepcyan+1.4); draw(arc(origin, dir(240), dir(300)), grey+1.8); label("$x$", dir(90)*0.9, dir(-90), red); label("$2525-x$", dir(160)*1.1, dir(160), deepgreen); label("$2525-x$", dir(20)*0.9, -dir(20), deepgreen); label("$3x$", dir(270)*1.1, grey); dotfactor *= 2; dot(dir(80), red); dot(dir(100), red); dot(dir(240), red); dot(dir(300), red); label("$B$", dir(80), dir(45), red); label("$A$", dir(100), dir(225), red); label("$C$", dir(240), -dir(240), red); label("$D$", dir(300), dir(310), red); [/asy][/asy] Since $2x < 100$, we can consider the arc of length $2x$. Both arcs $AC$ and $BD$ have length $2525-2x$. The arc of length $2x$ can't share an endpoint with both at once. $\blacksquare$ Finally, note that there are at least $50$ main arcs (each choice of $R$ generates one, and each main arc appears at most twice this way), but only $49$ possible killers. So this solves the problem.
30.12.2022 00:26
Sketch: This problem can be reduced to proving the existence of two arcs with sum $2525$ such that one arc does not share an endpoint AND is included in the other arc. Assume FTSOC there does not exist two such chords. For every red point $R_i$, there exists an arc with $R_i$ as an endpoint and length at least $2475$ (this can be done by extremal principle/taking two longest arcs). Yet, if equality occurs, there is a contradiction as there must be two arcs from $R_i$ with length $2475$, and the primitive arc of length $50$ cannot share an endpoint and be included in both arcs. So we can extend the bound to at least $2476$. There are at least $\frac{100}{2}=50$ such arcs, as each red point is the endpoint of one, and every such arc is counted at most twice by its two endpoints. By Pigeonhole, there exists two such arcs with the same length, say $2525-x$, where $1 \le x \le 50$. The only possible configuration is if the intersection of the two arcs is $x$ primitive arc. This proves the existence of two disjoint $2525-2x$ arcs. Yet, the $2x$ primitive arc then cannot share an endpoint and be included in both $2525-2x$ arcs, contradiction.
14.09.2024 19:00
Note that if two points are antipodal we can simply choose another point and then the chords from both ends of the diameter to the third point make a $90$ degree angle. Thus we assume this is not the case. The problem then becomes showing that there are two arcs that sum to $2525.$ Let the "Canon" arc of a point be the longest arc that has a length of less than $2525$ in either direction. Then the "anti-canon" arc is the arc with the length of the differece between the canon arc and $2525.$ If the anti-canon arc doesn't share any endpoint with the canon arc or isn't inside the canon arc, then we're done. Note that this means the canon arc has a minimum length of $2476,$ because if the anti canon arc was $50$ long then one endpoint would be antipodal with the other arc of length $2475.$ Therefore the anticanon arc has max length $49.$ Now, note that if an arc of length $a$ is the anti-canon of two different canon arcs, then we have two disjoint arcs of length $2525-2x,$ where the distance between the endpoints are $x,3x,$ which guarantees one of those arc's anti-arcs are outside the arc. However as we have $49$ anti-canons and at least $50$ canon arcs, we're done$.\blacksquare$
06.10.2024 12:40
Cleary we can find for each point an arc starting at that point with length $\geq 2475\leq 2525$, let the arc length be $2525-k$, suppose we have no antipodes, if the arc with length $k$ is not inside and sharing an endpoint with this arc it forms perpendicular chords. If it is always adjacent to the end point and inside, suppose we have two arcs of length $2475$, if this is the case from the way they are set up we in fact have $4$ arcs of that length which is a contradiction as at least 2 of them do not have the arc of length $50$ inside and adjacent. Thus we can have at most one arc of length $2525-50$, so we have at least $3$ arcs of length $2525-k$ for some fixed $k$, thus we must have an arc that does not contain the arc of length $k$ and have that arc and the arc of length $k$ are perpendicular.
27.12.2024 04:25
Surprisingly tricky. Let $N = 2525$. We call the dominant arc at a red point $P_i$ on the circle the arc with one endpoint at $P_i$ and another endpoint at $P_j$ (without loss of generality going in the positive indexed direction), such that $\widehat{P_iP_j} \leq N$ and $\widehat{P_iP_{j+1}} > N$. (In other words, the dominant arc is the longest arc possible that is shorter than $N$ from $P_i$). We call the maximal arcs at $P_i$ the two equivalently defined arcs if we restrict them in the counterclockwise and clockwise directions, respectively. Assume for the sake of contradiction that no two perpendicular chords with red points exist. Claim: For each maximal arc $\widehat{P_iP_j}$ of length $N - r$, either $\widehat{P_iP_{i+1}} = k$ or $\widehat{P_{j-1}P_j} = k$. Proof: Suppose otherwise. Then either the arc $\widehat{P_kP_{k+1}}$ with length $r$ is disjoint from $\widehat{P_iP_j}$, from where $\overline{P_iP_k}$ and $\widehat{P_jP_{k+1}}$ intersect at right angles, or $\widehat{P_kP_{k+1}}$ lies within $\widehat{P_iP_j}$, from where the same two arcs intersect perpendicularly (this time outside the circle). We have a contradiction in both cases. $\blacksquare$ Note that $N-50 \leq \widehat{P_iP_j} \leq N$ for any dominant arc as the two maximal-length arcs from $P_i$ in the counterclockwise and clockwise directions have union length $2N - r$ where $r \leq 100$. Claim: [Key Claim] No two disjoint dominant arcs have the same length. Proof: By the previous claim, any such two disjoint dominant arcs of identical length $N - r$ can be written as $\widehat{P_iP_{k+1}}$ and $\widehat{P_kP_j}$ where $\widehat{P_kP_{k+1}} = r$. It follows that $\widehat{P_jP_i} = 3r$. But now $\widehat{P_iP_k} = N - 2r$ and $\widehat{P_{k+1}P_j} = N-2r$ are both maximal arcs, and no arc of length $2r$ can satisfy the claim for both arcs, contradiction. $\blacksquare$ Now observe that if a dominant arc at $P_i$ has length $N - 50$, it follows that both maximal arcs at $P_i$ have length $N-50$. Then we can remove the arc of length $50$ contained by it and append the remaining arc of length $100$, creating a union of length $N$. Thus there are only $49$ possible lengths of dominant arcs and thus $49$ dominant arcs. But any given arc can only serve as the dominant arc for two different points $P_i$, hence contradiction. Remark: This problem is subtly difficult: the idea of considering a ``dominant" arc rather than just looking at maximal arcs is critical because it allows the forcing with an $N-2r$-length arc in the second claim.