Calcular el tamaño mínimo de una intersección (problema de la Olimpiada)... ¿alguna pista o solución? Por favor,

Question

PROBLEMA: Una persona tiene una capa de área $1$ compuesto por cinco parches posiblemente superpuestos. El área de cada parche es de al menos $\frac{1}{2}$ . Demostrar que existen dos parches cuya superposición tiene un área de al menos $\frac{1}{5}$ .

IDEAS QUE ME HAN VENIDO A LA MENTE:

-Utilizar el principio de inclusión-exclusión para tener una igualdad que implique las intersecciones de los parches

-Intentar argumentar por contradicción (suponiendo que la intersección de dos cualesquiera es menor que $\frac{1}{5}$ ). He descubierto que la suma de las áreas de los parches debe estar entre $\frac{5}{2}$ y $\frac{6}{2}$ .

Answer 1

(Nota: este argumento se reconstruye a partir de la escritura del problema como un programa lineal en $2^5$ variables, resolver el dual y luego interpretar la solución del dual).

---

Definir $P_i$ para $1 \le i \le 5$ para ser el tamaño del parche $i$ y $P_{ij}$ para $1 \le i < j \le 5$ para ser el tamaño del solapamiento entre parches $i$ y $j$ . Medimos en unidades de abrigos, por lo que $\frac12$ es la mitad de la superficie del abrigo.

Dejemos que $z = \max_{i,j} P_{ij}$ el tamaño del mayor solapamiento. Dado que $P_i \ge \frac12$ para todos $i$ y $P_{ij} \le z$ para todos $i$ y $j$ tenemos $$\frac15 \sum_i P_i - \frac1{10} \sum_{i<j} P_{ij} \ge \frac12 - z.\tag{$ \N - La estrella $}$$

Ahora miramos cuánto contribuye cada trozo de abrigo al lado izquierdo de $(\star)$ . (Por "trozo de abrigo" podemos entender una parte del abrigo especificada por los parches en los que se encuentra).

Si el trozo de abrigo está en $k$ parches, está contenida en $\binom{k}{2}$ solapamientos, por lo que contribuye $\frac15 k - \frac1{10}\binom{k}{2} = \frac{k(5-k)}{20}$ de su área, que se maximiza en $k=2$ o $k=3$ por $\frac{3}{10}$ . Si el lado izquierdo de $(\star)$ cuenta cada bit de capa con un multiplicador de como máximo $\frac{3}{10}$ entonces su valor puede ser como máximo $\frac{3}{10}$ de la superficie total del abrigo.

Por lo tanto, $(\star)$ nos dice que $\frac{3}{10} \ge \frac12 - z$ o $z \ge \frac15$ y ya está. (De hecho, el tamaño medio de un solapamiento, no sólo el máximo, debe ser al menos $\frac15$ .)

---

La solución primaria del mismo programa lineal muestra que este límite es ajustado. Dividir la capa en $10$ regiones $\{R_1, R_2, \dots, R_{10}\}$ de igual tamaño. Sea $$\begin{align} A &= R_1 \cup R_2 \cup R_6 \cup R_7 \cup R_8 \\ B &= R_3 \cup R_4 \cup R_6 \cup R_7 \cup R_9 \\ C &= R_1 \cup R_3 \cup R_8 \cup R_9 \cup R_{10} \\ D &= R_4 \cup R_5 \cup R_6 \cup R_8 \cup R_{10} \\ E &= R_2 \cup R_5 \cup R_7 \cup R_9 \cup R_{10} \end{align}$$ sean los cinco parches, y se puede comprobar que cada parche tiene área $\frac12$ pero se cruza con cualquier otro parche en dos regiones, por lo que cada solapamiento tiene un área $\frac15$ .