Difícil Cuestión De La Omi

Question

Deje $a_1,a_2,…,a_n$ ser distintos números enteros positivos y deje $M$ ser un conjunto de $n−1$ enteros positivos que no contengan $s=a_1+a_2+…+a_n$. Un saltamontes es saltar a lo largo del eje real, comienza en el punto de $0$ y fabricación de $n$ salta a la derecha, con longitudes $a_1,a_2,…,a_n$, en un cierto orden. Probar que el orden puede ser elegido de tal manera que el saltamontes nunca aterriza en cualquier punto en $M$.

Es bastante intuitivo, y he tratado de demostrar por inducción, pero fue en vano. Por favor alguien puede darme una pista (o publicar la respuesta, si les gustaría, no me importa)?

Answer 1

Esto es digno de pensar acerca de ti mismo hasta que la unidad de ti mad - que aprendí a resolver ese tipo de cosas. Parecía difícil en el original de la Olimpiada de cuando fue creado, sino que involucra nada realmente complicado.

Una pista:

Primero intente poner el salto más largo en el extremo derecho. Si usted puede saltar a un elemento de $M$ sin aterrizar en un elemento de $M$ tiene una inducción. Si usted no ha conseguido saltar de un elemento a de a $M$ se llevan a cabo en el lado derecho en el elemento de $M$ y el mayor salto. ¿Hasta dónde se puede conseguir ahora, empezando por la izquierda? Poner la mano derecha del elemento de $M$ en el uso y la más larga de salto para evitar ... a rellenar los detalles.