Fotografiar el cielo nocturno estrellado

Question

Por la noche, las estrellas del cielo se ven en diferentes intervalos de tiempo. Supongamos que para cada $k$ estrellas ( $k>1$ ), al menos $2$ de ellos se puede ver en un momento. Prueba que podemos fotografiar $k-1$ imágenes del cielo de forma que cada una de las estrellas mencionadas se vea en al menos una de las imágenes. (El número de estrellas es finito. Define los momentos en los que el $n^{th}$ estrella se ve como $[a_n,b_n]$ que $a_n<b_n$ .)

El problema tiene una buena solución utilizando la inducción en $k$ . Nuestro profesor nos dijo que encontráramos una solución utilizando la inducción sobre el número de estrellas. ¿Puedes ayudarme?

[fuente: 2ª ronda de la Olimpiada Matemática de Irán].

Answer 1

Para el paso de inducción, wlog. $a_n\ge a_i$ para todos $i<n$ . Por hipótesis de inducción, encontrar $k-1$ momentos $t_1<t_2<\ldots< t_{k-1}$ para disparar fotos que resuelvan el problema de la primera $n-1$ estrellas. Wlog. el $t_i$ son lo más tarde posible, es decir, cada $t_i$ es el punto final derecho de la intersección de los intervalos de visibilidad de "sus" estrellas. Esto implica que para cada $i\le k-1$ hay un $j<n$ con $t_i=b_j$ . Esto determina $k-1$ estrellas distintas (en realidad: este desplazamiento puede reducir el número de distintivo veces - pero entonces podemos, de hecho, sustituir $k$ por un número menor). Junto con el $n$ de la estrella, debe haber un momento $\tau$ donde todos estos son visibles. Claramente, $\tau\le t_{k-1}$ y $a_n\le \tau\le b_n$ De ello se desprende que $t_{k-1}\ge a_n$ podemos sustituir $t_{k-1}$ con $a_n$ y la imagen seguirá mostrando al menos las mismas estrellas, pero también las estrellas $n$ .