Kvant Math Problem 165
Represent the circle by the additive group $\mathbb R/\mathbb Z$, so that arc lengths are measured as fractions of the circumference.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m21s
Source on kvant.digital
Problem
On a circle there is a set $F$ consisting of 100 arcs. It is known that for any rotation $R$ of the circle, the set $R(F)$ has a common point with $F$. (In other words, for any $\alpha$ from $0^\circ$ to $180^\circ$, one can indicate in the set $F$ two points whose distance apart along the circle is $\alpha$.) What is the smallest possible sum of the lengths of the 100 arcs forming the set $F$? What will the answer be if there are not 100 arcs but $n$?
Yu. P. Lysov
Exploration
Represent the circle by the additive group $\mathbb R/\mathbb Z$, so that arc lengths are measured as fractions of the circumference. Let $A\subset \mathbb R/\mathbb Z$ be the union of the given arcs, and let $m(A)$ be its total length.
The condition says that for every rotation by $t$, the sets $A$ and $A+t$ intersect. Equivalently, for every $t\in\mathbb R/\mathbb Z$ there exist $x,y\in A$ such that $y-x=t$. Thus the difference set
$$A-A={x-y:x,y\in A}$$
is the whole circle.
The problem asks for the smallest possible measure of a union of $n$ arcs whose difference set is the whole circle.
A first guess is $m(A)\ge \frac12$. Indeed, if $m(A)<\frac12$, then
$$m(A-A)\le 2m(A)<1,$$
which would prevent $A-A$ from covering the entire circle. This suggests $\frac12$ as a lower bound.
The next question is whether $\frac12$ can actually be attained with exactly $n$ arcs. For a single arc of length $\frac12$, the difference set is the whole circle, because differences range through an interval of length $1$, which modulo $1$ is all of $\mathbb R/\mathbb Z$.
For several arcs, one may split that semicircle into $n$ disjoint arcs whose total length remains $\frac12$. If the gaps between consecutive pieces are chosen arbitrarily small, the difference set should still be the whole circle? This is not automatic. A safer construction is needed.
Take $n$ disjoint arcs separated by gaps, all lying inside a semicircle and having total length $\frac12$. Then the difference set need not be all of $\mathbb R/\mathbb Z$. The condition is delicate.
A better idea is to distribute the arcs periodically. Let
$$A=\bigcup_{k=0}^{n-1}\left[\frac{k}{n},,\frac{k}{n}+\frac1{2n}\right].$$
The total length is $\frac12$. For any $t$, write
$$t=\frac{m}{n}+u,\qquad 0\le u<\frac1n.$$
Then two arcs whose indices differ by $m$ contribute a difference interval
$$\left[\frac{m}{n}-\frac1{2n},,\frac{m}{n}+\frac1{2n}\right].$$
These intervals for $m=0,\dots,n-1$ cover the whole circle. Hence every $t$ belongs to $A-A$.
Thus $\frac12$ is attainable for every $n$.
The only nontrivial point is the lower bound $m(A)\ge \frac12$. The standard inequality $m(A-A)\le 2m(A)$ is the crucial step. On the circle it follows from the one-dimensional Brunn-Minkowski theorem, or more elementarily from the fact that a measurable subset of the line satisfies $m(X-Y)\le m(X)+m(Y)$ when both sets are intervals approximating $X,Y$. The circle version is obtained by lifting to the line.
Problem Understanding
Let $F$ be a union of $n$ arcs on a circle. The condition says that for every rotation of the circle, the rotated set intersects the original set. Equivalently, every circular distance occurs between two points of $F$.
We seek the smallest possible total length of the arcs forming $F$.
This is a Type C problem. We must determine the minimum possible total length, prove that no smaller value can occur, and construct a configuration attaining that value.
The answer is
$$\frac12$$
of the circumference, independent of $n$.
The intuitive reason is that the condition means the difference set $F-F$ equals the whole circle. A set of length less than $\frac12$ cannot have a difference set of length $1$, while a suitably arranged union of $n$ arcs with total length exactly $\frac12$ can realize every difference.
Proof Architecture
Lemma 1. If $A\subset \mathbb R/\mathbb Z$ satisfies the stated condition, then $A-A=\mathbb R/\mathbb Z$.
The condition directly says that every rotation amount occurs as a difference of two points of $A$.
Lemma 2. For every measurable $A\subset\mathbb R/\mathbb Z$,
$$m(A-A)\le 2m(A).$$
Lift $A$ to an interval of the line and apply the one-dimensional estimate for difference sets.
Lemma 3. Any admissible set satisfies $m(A)\ge \frac12$.
Since $A-A$ is the whole circle, its measure is $1$; combine this with Lemma 2.
Lemma 4. For every positive integer $n$, there exists a union of $n$ arcs of total length $\frac12$ whose difference set is the whole circle.
Use $n$ equally spaced arcs, each of length $\frac1{2n}$.
The hardest part is Lemma 4, because one must verify that every circular displacement actually appears as a difference of two points of the constructed set.
Solution
Normalize the circumference of the circle to be $1$. Let $A$ denote the union of the given $n$ arcs, and let $m(A)$ be its total length.
The condition of the problem states that for every rotation by $t\in\mathbb R/\mathbb Z$, the sets $A$ and $A+t$ have a common point.
A point belongs to both $A$ and $A+t$ precisely when there exists $x\in A$ such that $x-t\in A$. Hence for every $t$ there exist $x,y\in A$ with
$$t=x-y.$$
Therefore
$$A-A=\mathbb R/\mathbb Z.$$
Since the whole circle has measure $1$,
$$m(A-A)=1.$$
We now use the standard one-dimensional estimate
$$m(A-A)\le 2m(A).$$
To justify it, choose a point of the circle outside $A$ and cut the circle there. The set $A$ becomes a measurable subset $\widetilde A$ of an interval of the real line with the same measure. Every element of $A-A$ is represented by a difference of points of $\widetilde A$, so
$$m(A-A)\le m(\widetilde A-\widetilde A).$$
For measurable subsets of the line,
$$m(\widetilde A-\widetilde A)\le m(\widetilde A)+m(-\widetilde A) =2m(\widetilde A) =2m(A).$$
Hence
$$1=m(A-A)\le 2m(A),$$
which gives
$$m(A)\ge \frac12.$$
Thus the total length of the arcs can never be smaller than $\frac12$ of the circumference.
It remains to show that $\frac12$ is attainable for every $n$.
For $k=0,1,\dots,n-1$, define
$$I_k=\left[\frac{k}{n},,\frac{k}{n}+\frac1{2n}\right] \pmod 1,$$
and let
$$A=\bigcup_{k=0}^{n-1} I_k .$$
The set $A$ consists of $n$ arcs, each of length $\frac1{2n}$, so
$$m(A)=n\cdot\frac1{2n}=\frac12.$$
We prove that $A-A=\mathbb R/\mathbb Z$.
Fix any $t\in\mathbb R/\mathbb Z$. There exists an integer $m$, $0\le m\le n-1$, and a number $u$ with
$$-\frac1{2n}\le u\le \frac1{2n}$$
such that
$$t\equiv \frac{m}{n}+u \pmod 1.$$
Choose indices $k$ and $k+m$ modulo $n$. The difference set of the two arcs $I_{k+m}$ and $I_k$ is
$$I_{k+m}-I_k = \left[\frac{m}{n}-\frac1{2n}, \frac{m}{n}+\frac1{2n}\right] \pmod 1.$$
Since $u$ lies in this interval, the number $t$ belongs to $I_{k+m}-I_k$, hence to $A-A$.
Because $t$ was arbitrary,
$$A-A=\mathbb R/\mathbb Z.$$
Consequently the construction satisfies the required condition and has total length $\frac12$.
The minimum possible total length is therefore
$$\boxed{\frac12}$$
of the circumference.
For the original problem with $100$ arcs, the answer is again
$$\boxed{\frac12}.$$
Equality is attained, for example, by $100$ equally spaced arcs each of length $\frac1{200}$.
Verification of Key Steps
The first delicate step is the equivalence between the rotation condition and the identity $A-A=\mathbb R/\mathbb Z$. If $(A+t)\cap A\neq\varnothing$, there exists $x\in A$ with $x\in A+t$. By definition of translation, $x=y+t$ for some $y\in A$, so $t=x-y$. Conversely, if $t=x-y$ with $x,y\in A$, then $x\in A\cap(A+t)$. Thus the two formulations are exactly equivalent.
The second delicate step is the lower bound. Since $A-A$ equals the whole circle, its measure is $1$. The inequality $m(A-A)\le 2m(A)$ yields $1\le 2m(A)$. Any argument producing only $m(A-A)\le 4m(A)$ would lead merely to $m(A)\ge \frac14$, which is insufficient. The factor $2$ is essential.
The third delicate step is the construction. For fixed $m$, the difference of two arcs whose indices differ by $m$ fills precisely
$$\left[\frac{m}{n}-\frac1{2n}, \frac{m}{n}+\frac1{2n}\right].$$
These intervals have length $\frac1n$ and are centered at the points $\frac{m}{n}$. Consecutive intervals meet at endpoints, and the union over $m=0,\dots,n-1$ has total length $1$. Hence they cover the entire circle. This guarantees that every displacement belongs to $A-A$.
Alternative Approaches
Instead of working with difference sets, one may formulate the condition through convolutions. Let $\mathbf 1_A$ be the indicator function of $A$. The quantity
$$(\mathbf 1_A * \mathbf 1_{-A})(t)$$
equals the measure of $A\cap(A+t)$. The hypothesis says that this convolution is positive for every $t$. Integrating over the circle gives
$$m(A)^2 = \int (\mathbf 1_A * \mathbf 1_{-A})(t),dt.$$
A support argument then shows that a function positive on the whole circle must have support of measure $1$, leading again to $m(A)\ge \frac12$ through the estimate that the support of the convolution has measure at most $2m(A)$.
Another approach uses additive combinatorics. The condition is $A-A=\mathbb R/\mathbb Z$. A continuous version of the inequality $m(A-A)\le 2m(A)$ immediately yields the lower bound. The extremal construction arises from taking a subgroup of order $n$ and replacing each point by an interval of length $\frac1{2n}$. This viewpoint makes the equality case particularly transparent.