OIM

Beto juega con su computadora al siguiente juego: inicialmente su computadora elige al azar $30$ números de $1$ a $2015$, y Beto los escribe en un pizarrón (puede haber números repetidos); en cada paso, Beto elige un entero positivo $k$ y algunos de los números escritos en el pizarrón, y le resta a cada uno de ellos el número $k$, con la condición de que los números resultantes sigan siendo no negativos. El objetivo del juego es lograr que en algún momento los $30$ números resultantes sean iguales a $0$, en cuyo caso el juego termina. Determine el menor número $n$ tal que, independientemente de los números que inicialmente eligió su computadora, Beto pueda terminar el juego en a lo sumo $n$ pasos.