Find a real number t such that for any set of 120 points P1,…P120 on the boundary of a unit square, there exists a point Q on this boundary with ∣P1Q∣+∣P2Q∣+⋯+∣P120Q∣=t.
A number or a short expression. Spacing and $ signs are ignored.
Solution
We need to find a real number t such that for any set of 120 points P1,…,P120 on the boundary of a unit square, there exists a point Q on this boundary with ∣P1Q∣+∣P2Q∣+⋯+∣P120Q∣=t.
Define U to be a set of points P1,…,P120 on the boundary of a unit square. Define gU(Q)=∑i=1120∣QPi∣.
Lemma 1: The set {gU(Q):Q∈U} is a closed interval IU.
*Proof:* Clearly, gU(Q) is bounded above and below over Q∈U, and it is continuous in both x and y coordinates if we place it in the Cartesian plane. Combining these two implies the set of values is an interval. ■
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 all intersect over all sets of 120 points 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} and U′={P1′,…,P120′} such that IU is entirely before IU′. The key is that now gU(Q)<gU′(Q′)for all Q∈U and Q′∈U′(♠). Let C1,C2,C3,C4 be the corners of the unit square U and M1′,M2′,M3′,M4′ the midpoints of the four sides of the unit square U′. Summing four bounds appearing from (♠): gU(C1)+⋯+gU(C4)<gU′(M1)+⋯+gU′(M4)(♣). The key is that we can compute and bound each of the above since they become sums of functions of a single point Pi relative to the fixed unit square, instead of about the entire set of Pi's. In particular, gU(C1)+⋯+gU(C4)=j=1∑4i=1∑120∣CjPi∣=i=1∑120∣C1Pi∣+∣C2Pi∣+∣C3Pi∣+∣C4Pi∣≥i=1∑120(1+5)=120(1+5). 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∣ over P on the boundary occurs is 1+5, and occurs when P is the midpoint of a side. Now similarly, gU(M1′)+⋯+gU(M4′)=j=1∑4i=1∑120∣Mj′Pi′∣=i=1∑120∣M1′Pi′∣+∣M2′Pi′∣+∣M3′Pi′∣+∣M4′Pi′∣≤i=1∑120(1+5)=120(1+5). The third step since we can confirm with coordinates that the maximum ∣M1P∣+∣M2P∣+∣M3P∣+∣M4P∣ over P on the boundary is 1+5, and occurs when P is a corner.
However, combining these two bounds contradicts (♣)! Therefore, such a t exists. In particular, we can show t=30(1+5) by proving that t<30(1+5) fails from the corners bound and t>30(1+5) fails from the midpoints bound; now, since we have shown at least one valid t exists, it must be the claimed value.
The answer is: 30(1+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.