Problem

Source: 239 2010 S3

Tags: combinatorics



Grisha wrote $n$ different natural numbers, the sum of which does not exceed $S$. The saboteur added to each of them a number from the half-interval $[0, 1)$. The sabotage is successful if there exists two subsets, the sums of the numbers in which differ by no more than $1$. At what minimum $S$ can Grisha ensure that the sabotage will definitely not be succeeded?