Let S be the set {1, 2, 3, . . . , n} consisting of the first n positive integers.
What is the maximum value of n for which every 100-element subset of
S contains two integers which differ by 25 ?	Pick one:
A) 171
B) 172
C) 173
D) 174
E) 175
Let n be as large as possible so that every 100-element subset of S contains two integers   differing by 25. Observe that the set   A = {1, 2, . . . , 25} [ {51, 52, . . . , 75} [ {101, 102, . . . , 125} [ {151, 152, . . . , 175}   has 100 elements no two of which differ by 25. So n 174. We show now that S = {1, 2, . . . , 174}   has the property that every 100-element subset of S contains two integers differing by 25. For   0 j 24, let Tj be the subset of S consisting of the integers from S that have a remainder of j   when we divide by 25. The sets Tj have no common elements. If S0 is a subset of S consisting of   exactly 100 elements, then there are exactly 74 elements of S not in S0. These must lie in the 25   sets Tj . One of the sets Tj contains at most 2 of these 74 elements of S not in S0 (by the pigeon-hole   principle). Fix such a j. Since Tj contains at least 6 elements, the intersection Tj \S0 contains two   consecutive elements of Tj , that is two elements of Tj that differ by 25. Thus, S has the property   that every 100-element subset of S contains two integers differing by 25   correct answer 174
<result>D</result>
Let S be the set {1, 2, 3, . . . , n} consisting of the first n positive integers.
What is the maximum value of n for which every 100-element subset of
S contains two integers which differ by 25 ?