Question

Find the minimum value of m such that any m-element subset of the set of integers {1,2,3...,2016} contains at least 2 numbers a and b such that |a-b| is smaller than or equal to 3.

Answer 1

Divide the set $\{1,\ 2,\ 3,\,\dots\,,\ 2016\}$ into 4 equivalent subsets consisting of 504 elements, in which each element is in AP of common difference 4, as the following.

$\longrightarrow\{1,\ 2,\ 3,\,\dots\,,\ 2016\}=A\cup B\cup C\cup D$

where,

• $A=\{1,\ 5,\ 9,\,\dots\,,\ 2013\}$

• $B=\{2,\ 6,\ 10,\,\dots\,,\ 2014\}$

• $C=\{3,\ 7,\ 11,\,\dots\,,\ 2015\}$

• $D=\{4,\ 8,\ 12,\,\dots\,,\ 2016\}$

Consider any one set among these 4 sets. If we include atleast one element from any among the other three, say if we include an element $a$ from any among the other three, then there should be atleast one element in the first considered set, say if there exists $b,$ such that $|a-b|\leq 3.$

For example, consider the set $A.$ Include the element $10\in B$ in the set $A,$ then we see $9\in A$ and $13\in A$ such that $|9-10|=1<3$ and $|13-10|=3.$

As if we replace any few elements in the considered set, say if an element $c$ is replaced by $a,$ there should exist $b$ in the considered set such that $|a-b|\leq3.$

For example, in the set $A$ if $9\in A$ is replaced by $11\in C,$ then we see $13\in A$ such that $|11-13|=2<3.$

So the minimum value of $m$ is equal to 1 added to the cardinality of $A$ or $B$ or $C$ or $D,$ i.e.,

$\longrightarrow m=504+1$

$\longrightarrow\underline{\underline{m=505}}$

Hence 505 is the answer.