A subset of 2017 elements

Let S S be a subset of { 1 , 2 , , 2017 } \{1,2,\ldots ,2017\} such that no two elements of S S have a sum divisible by 37. Find the maximum number of elements that S S can have.

991 992 989 994 990 995 993

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Chris Lewis
May 23, 2019

Let A k A_k denote the set of numbers from 1 1 to 2017 2017 whose remainder is k k upon division by 37 37 .

Since 2017 2017 is not a multiple of 37 37 , these sets are not all the same size; A k A_k has 55 55 elements when 1 k 19 1 \le k \le 19 , and 54 54 elements otherwise.

S S can contain at most one element of A 0 A_0 .

S S can have as many elements from A 1 A_1 as we want, as long as it doesn't have any element from A 36 A_{36} , and so on; we can choose to have elements from A k A_k or A 37 k A_{37-k} , but not both. Clearly we want to pick elements from the bigger sets when we can; these are A 1 , , A 18 A_1,\ldots,A_{18} (we could pick A 19 A_{19} instead of A 18 A_{18} , but it doesn't change the total).

The maximum number of elements is therefore 1 + 18 × 55 = 991 1+18\times 55=\boxed{991} .

I've seen this problem or variants of it before - does anyone know if it has a name?

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...