1st Centromerican 1999 Problem B3 S ⊆ {1, 2, 3, ... , 1000} is such that if m and n are distinct elements of S, then m+n does not belong to S. What is the largest possible number of elements in S?
501 eg {500, 501, ... , 1000} Solution We show by induction that the largest possible subset of {1, 2, ... , 2n} has n+1 elements. It is obvious for n = 1. Now suppose it is true for n. If we do not include 2n-1 or 2n in the subset, then by induction it can have at most n elements. If we include 2n, then we can include at most one from each of the pairs (1,2n-1), (2,2n-2), ... , (n-1,n+1). So with n and 2n, that gives at most n+1 in all. If we include 2n-1 but not 2n, then we can include at most one from each of the pairs (1,2n-2), (2,2n-3), ... , (n-1,n), so at most n in all. 1st OMCC 1999 © John Scholes jscholes@kalva.demon.co.uk 26 November 2003 Last corrected/updated 26 Nov 03