HMMT 十一月 2015 · GEN 赛 · 第 5 题
HMMT November 2015 — GEN Round — Problem 5
题目详情
- Let S be a subset of the set { 1 , 2 , 3 , . . . , 2015 } such that for any two elements a, b ∈ S , the difference a − b does not divide the sum a + b . Find the maximum possible size of S .
解析
- Let S be a subset of the set { 1 , 2 , 3 , . . . , 2015 } such that for any two elements a, b ∈ S , the difference a − b does not divide the sum a + b . Find the maximum possible size of S . Proposed by: Sam Korsky Answer: 672 From each of the sets { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } , . . . at most 1 element can be in S . This leads to an ⌈ ⌉ 2015 upper bound of = 672 which we can obtain with the set { 1 , 4 , 7 , . . . , 2014 } . 3