26
$\begingroup$

Let $n$ be a positive integer. Some integers between $1$ and $n$ (inclusive) are written on a line, where the same integer can appear multiple times. Is it true that we can always divide the line into $n$ parts and assign to each part a label between $1$ and $n$ (inclusive), where each label is used exactly once, so that for any $1\leq i\leq n$, the part labeled $i$ contains at least as many copies of the integer $i$ as any other part?

If $n=1$ then this is trivially true, because we only write $1$s and we do not need to divide the line at all.

If $n=2$ it is also true: Move from the left of the line until at least half of all the $1$s or half of all the $2$s are reached, then stop and divide the line. Say we have reached at least half of all the $1$s. Then label the left part with $1$ and the right part with $2$.

$\endgroup$
4
+50
$\begingroup$

This follows from David Gale's generalization of Knaster–Kuratowski–Mazurkiewicz lemma. See Wikipedia for the formulation of the generalization and the relevant terminology.

To prove the theorem, we first make the problem continuous:

For each $i=0, \dots, L-1$, the unit (open) interval $(i, i+1)$ has color $j$ for some $j \in [n]$. Is it true that we can always divide the interval $[0, L]$ into $n$ disjoint (open) intervals $I_1, \dots, I_n$ (from left to right) of length $x_1, x_2, \dots, x_n$ and find a permutation $\pi\in S_n$ so that for any $i\in[n]$, the total length of color $\pi(i)$ in interval $I_i$ is at least as much as in any other interval?

Once we prove the continuous version, we can "round" each interval in the following way. If the left end point $a$ of interval $I_i$ is colored $\pi(i)$, we round $a$ to $\lfloor a\rfloor$. Similarly, if the right end point $b$ of interval $I_{i}$ is colored by $\pi(i)$, we round $b$ to $\lceil b\rceil$. If there are end points not rounded yet, we round them arbitrarily. One can show that the resulting partition gives a solution to the discrete version.

Finally, we prove the continuous version. Consider the $(n-1)$-simplex $$\Delta := \left\{(x_1, \dots, x_n)\in \mathbb{R}^n:x_1 + x_2 + \dots + x_n = L,x_1, \dots, x_n \ge 0\right\},$$ with vertices $v_i = Le_i$, where $e_1, \dots, e_n$ forms the standard basis of $\mathbb{R}^n$.

For every $x = (x_1, \dots, x_n) \in \Delta$, define the (open) interval $I_i(x) = (x_1+\dots+x_{i-1}, x_1+\dots+x_{i})$ for all $i\in [n]$, and we say $I_i(x)$ is dominant in color $j$ if the total length of color $j$ in interval $I_i(x)$ is at least as much as in the other $I_*(x)$. For every $i \in [n]$ and $j \in [n]$, let $$C_i^j := \{x\in\Delta: I_i(x) \text{ is dominant in color }j\}.$$

One can check that for every $j\in[n]$, $C_1^j, \dots, C_n^j$ is a KKM covering. By David Gale's result, there exists a permutation $\pi$ such that $$\bigcap_{i=1}^n C_i^{\pi(i)}\neq \emptyset.$$

In other words, there is $(x_1, \dots, x_n)\in \Delta$ such that $(x_1, \dots, x_n)\in C_{i}^{\pi(i)}$ for all $i\in[n]$, that is, $I_i(x)$ is dominant in color $\pi(i)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.