30 integers on a chalkboard
Source: Iberoamerican 2015 #6
November 11, 2015
combinatorics
Problem Statement
Beto plays the following game with his computer: initially the computer randomly picks integers from to , and Beto writes them on a chalkboard (there may be repeated numbers). On each turn, Beto chooses a positive integer and some if the numbers written on the chalkboard, and subtracts from each of the chosen numbers, with the condition that the resulting numbers remain non-negative. The objective of the game is to reduce all numbers to , in which case the game ends. Find the minimal number such that, regardless of which numbers the computer chooses, Beto can end the game in at most turns.