Maths Olympiad Prep

Library / /3 of 10

Combinatorics Difficulty 6.2 National olympiad Find the answer

Denote SS as the subset of {1,2,3,,1000}\{1,2,3,\dots,1000\} with the property that none of the sums of two different elements in SS is in SS. Find the maximum number of elements in SS.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Denote S S as a subset of {1,2,3,,1000} \{ 1, 2, 3, \ldots, 1000 \} with the property that no sum of two different elements in S S is itself an element of S S . We wish to find the maximum number of elements in S S .

To address this problem, consider the possibility of selecting elements from {1,2,3,,1000} \{ 1, 2, 3, \ldots, 1000 \} such that adding any two distinct elements never results in another element within the same set. An effective approach to create such a subset involves selecting alternating numbers starting from 1 1 .

Construct S S by including every second integer from the set:
S={1,3,5,7,,999} S = \{ 1, 3, 5, 7, \ldots, 999 \}

To verify that this set satisfies the condition:
- Let a,bS a, b \in S with a<b a < b . The sum a+b a + b will be:
- At least 1+3=4 1 + 3 = 4 ,
- At most 999+997=1996 999 + 997 = 1996 .

Notice that every element a a in S S is odd and any sum a+b a+b of two distinct odd numbers is even. Therefore, no sum of two elements in the constructed set forms another odd number in the sequence. Thus, a+bS a + b \notin S .

Since there are 500 odd numbers in {1,2,3,,999} \{1, 2, 3, \ldots, 999\} , and by the inclusion of 1 as the first odd number, there are 501 numbers in our subset S S .

Therefore, the maximum number of such elements in S S is:
501 \boxed{501}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.