Let be a subset of such that no two elements of have a sum divisible by 37. Find the maximum number of elements that can have.
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.
Let A k denote the set of numbers from 1 to 2 0 1 7 whose remainder is k upon division by 3 7 .
Since 2 0 1 7 is not a multiple of 3 7 , these sets are not all the same size; A k has 5 5 elements when 1 ≤ k ≤ 1 9 , and 5 4 elements otherwise.
S can contain at most one element of A 0 .
S can have as many elements from A 1 as we want, as long as it doesn't have any element from A 3 6 , and so on; we can choose to have elements from A k or A 3 7 − k , but not both. Clearly we want to pick elements from the bigger sets when we can; these are A 1 , … , A 1 8 (we could pick A 1 9 instead of A 1 8 , but it doesn't change the total).
The maximum number of elements is therefore 1 + 1 8 × 5 5 = 9 9 1 .
I've seen this problem or variants of it before - does anyone know if it has a name?