Maths Olympiad Prep

Library / /17 of 37

Geometry Difficulty 8.0 Shortlist Find the answer

Find a real number tt such that for any set of 120 points P1,P120P_1, \ldots P_{120} on the boundary of a unit square, there exists a point QQ on this boundary with P1Q+P2Q++P120Q=t|P_1Q| + |P_2Q| + \cdots + |P_{120}Q| = t.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We need to find a real number t t such that for any set of 120 points P1,,P120 P_1, \ldots, P_{120} on the boundary of a unit square, there exists a point Q Q on this boundary with P1Q+P2Q++P120Q=t |P_1Q| + |P_2Q| + \cdots + |P_{120}Q| = t .

Define U\mathcal{U} to be a set of points P1,,P120 P_1, \ldots, P_{120} on the boundary of a unit square. Define gU(Q)=i=1120QPi g_{\mathcal{U}}(Q) = \sum_{i=1}^{120} |QP_i| .

Lemma 1: The set {gU(Q):QU}\{g_{\mathcal{U}}(Q) : Q \in \mathcal{U}\} is a closed interval IU I_{\mathcal{U}} .

*Proof:* Clearly, gU(Q) g_{\mathcal{U}}(Q) is bounded above and below over QU Q \in \mathcal{U} , and it is continuous in both x x and y y coordinates if we place it in the Cartesian plane. Combining these two implies the set of values is an interval. \blacksquare

Lemma 2: Given a finite set of closed intervals, they all intersect if and only if every two intersect.

We want to show that the intervals IU I_{\mathcal{U}} all intersect over all sets of 120 points U\mathcal{U}. By Lemma 2, it suffices to check that every two intersect. Suppose for the sake of contradiction that there exists some U={P1,,P120}\mathcal{U} = \{P_1, \ldots, P_{120}\} and U={P1,,P120}\mathcal{U}' = \{P_1', \ldots, P_{120}'\} such that IU I_{\mathcal{U}} is entirely before IU I_{\mathcal{U}'} . The key is that now
gU(Q)<gU(Q)for all QU and QU(). g_{\mathcal{U}}(Q) < g_{\mathcal{U}'}(Q') \quad \text{for all } Q \in \mathcal{U} \text{ and } Q' \in \mathcal{U}' \quad (\spadesuit).
Let C1,C2,C3,C4 C_1, C_2, C_3, C_4 be the corners of the unit square U\mathcal{U} and M1,M2,M3,M4 M_1', M_2', M_3', M_4' the midpoints of the four sides of the unit square U\mathcal{U}'. Summing four bounds appearing from ()(\spadesuit):
gU(C1)++gU(C4)<gU(M1)++gU(M4)(). g_{\mathcal{U}}(C_1) + \cdots + g_{\mathcal{U}}(C_4) < g_{\mathcal{U}'}(M_1) + \cdots + g_{\mathcal{U}'}(M_4) \quad (\clubsuit).
The key is that we can compute and bound each of the above since they become sums of functions of a single point Pi P_i relative to the fixed unit square, instead of about the entire set of Pi P_i 's. In particular,
gU(C1)++gU(C4)=j=14i=1120CjPi=i=1120C1Pi+C2Pi+C3Pi+C4Pii=1120(1+5)=120(1+5). \begin{align*} g_{\mathcal{U}}(C_1) + \cdots + g_{\mathcal{U}}(C_4) &= \sum_{j=1}^4 \sum_{i=1}^{120} |C_jP_i| \\ &= \sum_{i=1}^{120} |C_1P_i| + |C_2P_i| + |C_3P_i| + |C_4P_i| \\ &\ge \sum_{i=1}^{120} (1 + \sqrt{5}) \\ &= 120(1 + \sqrt{5}). \end{align*}
The second step above followed by switching the order of summation. The third step since we can confirm with coordinates that the minimum C1P+C2P+C3P+C4P |C_1P| + |C_2P| + |C_3P| + |C_4P| over P P on the boundary occurs is 1+5 1 + \sqrt{5} , and occurs when P P is the midpoint of a side. Now similarly,
gU(M1)++gU(M4)=j=14i=1120MjPi=i=1120M1Pi+M2Pi+M3Pi+M4Pii=1120(1+5)=120(1+5). \begin{align*} g_{\mathcal{U}}(M_1') + \cdots + g_{\mathcal{U}}(M_4') &= \sum_{j=1}^4 \sum_{i=1}^{120} |M_j'P_i'| \\ &= \sum_{i=1}^{120} |M_1'P_i'| + |M_2'P_i'| + |M_3'P_i'| + |M_4'P_i'| \\ &\le \sum_{i=1}^{120} (1 + \sqrt{5}) \\ &= 120(1 + \sqrt{5}). \end{align*}
The third step since we can confirm with coordinates that the maximum M1P+M2P+M3P+M4P |M_1P| + |M_2P| + |M_3P| + |M_4P| over P P on the boundary is 1+5 1 + \sqrt{5} , and occurs when P P is a corner.

However, combining these two bounds contradicts ()(\clubsuit)! Therefore, such a t t exists. In particular, we can show t=30(1+5) t = 30(1 + \sqrt{5}) by proving that t<30(1+5) t < 30(1 + \sqrt{5}) fails from the corners bound and t>30(1+5) t > 30(1 + \sqrt{5}) fails from the midpoints bound; now, since we have shown at least one valid t t exists, it must be the claimed value.

The answer is: 30(1+5)\boxed{30(1 + \sqrt{5})}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.