Maths Olympiad Prep

Library / /2 of 2

Geometry Difficulty 7.9 National Olympiad, round 2 Prove it Romanian Master of Mathematics (RMM)

Problem:
Given a positive integer nn, determine the largest real number μ\mu satisfying the following condition: for every 4n4n-point configuration CC in an open unit square UU, there exists an open rectangle in UU, whose sides are parallel to those of UU, which contains exactly one point of CC, and has an area greater than or equal to μ\mu.

Solution

Solution:
The required maximum is 12n+2\frac{1}{2n+2}. To show that the condition in the statement is not met if μ>12n+2\mu > \frac{1}{2n+2}, let U=(0,1)×(0,1)U = (0,1) \times (0,1), choose a small enough positive ϵ\epsilon, and consider the configuration CC consisting of the nn four-element clusters of points (in+1±ϵ)×(12±ϵ)\left(\frac{i}{n+1} \pm \epsilon\right) \times \left(\frac{1}{2} \pm \epsilon\right), i=1,,ni = 1, \ldots, n, the four possible sign combinations being considered for each ii. Clearly, every open rectangle in UU, whose sides are parallel to those of UU, which contains exactly one point of CC, has area at most (1n+1+ϵ)(12+ϵ)<μ\left(\frac{1}{n+1} + \epsilon\right) \cdot \left(\frac{1}{2} + \epsilon\right) < \mu if ϵ\epsilon is small enough.

We now show that, given a finite configuration CC of points in an open unit square UU, there always exists an open rectangle in UU, whose sides are parallel to those of UU, which contains exactly one point of CC, and has an area greater than or equal to μ0=2C+4\mu_0 = \frac{2}{|C|+4}.

To prove this, usage will be made of the following two lemmas whose proofs are left at the end of the solution.

Lemma 1. Let kk be a positive integer, and let λ<1k/2+1\lambda < \frac{1}{\lfloor k / 2 \rfloor + 1} be a positive real number. If t1,,tkt_{1}, \ldots, t_{k} are pairwise distinct points in the open unit interval (0,1)(0,1), then some tit_{i} is isolated from the other tjt_{j} by an open subinterval of (0,1)(0,1) whose length is greater than or equal to λ\lambda.

Lemma 2. Given an integer k2k \geq 2 and positive integers m1,,mkm_{1}, \ldots, m_{k},
m12+i=1kmi2+mk2i=1kmik+2 \left\lfloor\frac{m_{1}}{2}\right\rfloor + \sum_{i=1}^{k} \left\lfloor\frac{m_{i}}{2}\right\rfloor + \left\lfloor\frac{m_{k}}{2}\right\rfloor \leq \sum_{i=1}^{k} m_{i} - k + 2

Back to the problem, let U=(0,1)×(0,1)U = (0,1) \times (0,1), project CC orthogonally on the xx-axis to obtain the points x1<<xkx_{1} < \cdots < x_{k} in the open unit interval (0,1)(0,1), let i\ell_{i} be the vertical through xix_{i}, and let mi=Cim_{i} = |C \cap \ell_{i}|, i=1,,ki = 1, \ldots, k.

Setting x0=0x_{0} = 0 and xk+1=1x_{k+1} = 1, assume that xi+1xi1>(mi/2+1)μ0x_{i+1} - x_{i-1} > (\lfloor m_{i} / 2 \rfloor + 1) \mu_0 for some index ii, and apply Lemma 1 to isolate one of the points in CiC \cap \ell_{i} from the other ones by an open subinterval xi×Jx_{i} \times J of xi×(0,1)x_{i} \times (0,1) whose length is greater than or equal to μ0/(xi+1xi1)\mu_0 / (x_{i+1} - x_{i-1}). Consequently, (xi1,xi+1)×J\left(x_{i-1}, x_{i+1}\right) \times J is an open rectangle in UU, whose sides are parallel to those of UU, which contains exactly one point of CC and has an area greater than or equal to μ0\mu_0.

Next, we rule out the case xi+1xi1(mi/2+1)μ0x_{i+1} - x_{i-1} \leq (\lfloor m_{i} / 2 \rfloor + 1) \mu_0 for all indices ii. If this were the case, notice that necessarily k>1k > 1; also, x1x0<x2x0(m1/2+1)μ0x_{1} - x_{0} < x_{2} - x_{0} \leq (\lfloor m_{1} / 2 \rfloor + 1) \mu_0 and xk+1xk<xk+1xk1(mk/2+1)μ0x_{k+1} - x_{k} < x_{k+1} - x_{k-1} \leq (\lfloor m_{k} / 2 \rfloor + 1) \mu_0. With reference to Lemma 2, write
2=2(xk+1x0)=(x1x0)+i=1k(xi+1xi1)+(xk+1xk)<((m12+1)+i=1k(mi2+1)+(mk2+1))μ0(i=1kmi+4)μ0=(C+4)μ0=2 \begin{aligned} 2 = 2(x_{k+1} - x_{0}) & = (x_{1} - x_{0}) + \sum_{i=1}^{k} (x_{i+1} - x_{i-1}) + (x_{k+1} - x_{k}) \\ & < \left( (\lfloor \frac{m_{1}}{2} \rfloor + 1) + \sum_{i=1}^{k} (\lfloor \frac{m_{i}}{2} \rfloor + 1) + (\lfloor \frac{m_{k}}{2} \rfloor + 1) \right) \cdot \mu_0 \\ & \leq (\sum_{i=1}^{k} m_{i} + 4) \mu_0 = (|C| + 4) \mu_0 = 2 \end{aligned}
and thereby reach a contradiction.

Finally, we prove the two lemmas.

Proof of Lemma 1. Suppose, if possible, that no tit_{i} is isolated from the other tjt_{j} by an open subinterval of (0,1)(0,1) whose length is greater than or equal to λ\lambda. Without loss of generality, we may (and will) assume that 0=t0<t1<<tk<tk+1=10 = t_{0} < t_{1} < \cdots < t_{k} < t_{k+1} = 1. Since the open interval (ti1,ti+1)(t_{i-1}, t_{i+1}) isolates tit_{i} from the other tjt_{j}, its length, ti+1ti1t_{i+1} - t_{i-1}, is less than λ\lambda. Consequently, if kk is odd we have 1=i=0(k1)/2(t2i+2t2i)<λ(1+k12)<11 = \sum_{i=0}^{(k-1)/2} (t_{2i+2} - t_{2i}) < \lambda (1 + \frac{k-1}{2}) < 1; if kk is even, we have 1<1+tktk1=i=0k/21(t2i+2t2i)+(tk+1tk1)<λ(1+k2)<11 < 1 + t_{k} - t_{k-1} = \sum_{i=0}^{k/2-1} (t_{2i+2} - t_{2i}) + (t_{k+1} - t_{k-1}) < \lambda (1 + \frac{k}{2}) < 1. A contradiction in either case.

Proof of Lemma 2. Let I0I_{0}, respectively I1I_{1}, be the set of all indices ii in the range 2,,k12, \ldots, k-1 such that mim_{i} is even, respectively odd. Clearly, I0I_{0} and I1I_{1} form a partition of that range. Since mi2m_{i} \geq 2 if ii is in I0I_{0}, and mi1m_{i} \geq 1 if ii is in I1I_{1} (recall that the mim_{i} are positive integers),
i=2k1mi=iI0mi+iI1mi2I0+I1=2(k2)I1,orI12(k2)i=2k1mi \sum_{i=2}^{k-1} m_{i} = \sum_{i \in I_{0}} m_{i} + \sum_{i \in I_{1}} m_{i} \geq 2|I_{0}| + |I_{1}| = 2(k-2) - |I_{1}|, \quad \text{or} \quad |I_{1}| \geq 2(k-2) - \sum_{i=2}^{k-1} m_{i}
Therefore,
m12+i=1kmi2+mk2m1+(i=2k1mi2I12)+mkm1+(12i=2k1mi(k2)+12i=2k1mi)+mk=i=1kmik+2 \begin{aligned} \left\lfloor \frac{m_{1}}{2} \right\rfloor + \sum_{i=1}^{k} \left\lfloor \frac{m_{i}}{2} \right\rfloor + \left\lfloor \frac{m_{k}}{2} \right\rfloor & \leq m_{1} + \left( \sum_{i=2}^{k-1} \frac{m_{i}}{2} - \frac{|I_{1}|}{2} \right) + m_{k} \\ & \leq m_{1} + \left( \frac{1}{2} \sum_{i=2}^{k-1} m_{i} - (k-2) + \frac{1}{2} \sum_{i=2}^{k-1} m_{i} \right) + m_{k} \\ & = \sum_{i=1}^{k} m_{i} - k + 2 \end{aligned}

Remark. In case 4n4n is replaced by a positive integer kk not divisible by 44, we do not yet know the maximal μ\mu satisfying the corresponding condition.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.