Sabotage of natural numbers
Source: 239 2010 S3
July 29, 2020
combinatorics
Problem Statement
Grisha wrote different natural numbers, the sum of which does not exceed . The saboteur added to each of them a number from the half-interval . The sabotage is successful if there exists two subsets, the sums of the numbers in which differ by no more than . At what minimum can Grisha ensure that the sabotage will definitely not be succeeded?