Question

Let $S=\{1,2,3,....,40\}$ and let $A$ be a subset of $S$ such that no two elements in $A$ have their sum divisible by $5$. What is the maximum number of elements possible in $A$?

• A. $10$
• B. $13$
• C. $17$
• D. $20$

Answer 1

The correct option is C $17$

Given

$S$ $=$ { $1,2,3,....,40$ }

Construct subsets $S_1$, $S_2$, $S_3$, $S_3$, $S_4$, $S_5$ of ${}^{\prime }{S}^{\prime }$ such that

$S_1$ $=$ { $5n$ $+$ $1$ $|$ $0$ $\le$ $n$ $\le$ $7$ }

$S_2$ $=$ { $5n$ $+$ $2$ $|$ $0$ $\le$ $n$ $\le$ $7$ }

$S_3$ $=$ { $5n$ $+$ $3$ $|$ $0$ $\le$ $n$ $\le$ $7$ }

$S_4$ $=$ { $5n$ $+$ $4$ $|$ $0$ $\le$ $n$ $\le$ $7$ }

$S_5$ $=$ { $5n$ $+$ $5$ $|$ $0$ $\le$ $n$ $\le$ $7$ }

To construct a set $A$(subset of $S$) such that no two elements in $A$ have their sum divisible by $5$,

Initialize $A$ $=$ { }

Select the set $S_1$,

As all the elements in $S_1$ are of the form $(5n$ $+$ $1)$, we have to not select any element which is of the form $(5n$ $+$ $4)$, as that makes the sum divisible by $5$.

So, $A$ $=$ $A$ $\cup$ $S_1$ $=$ $S_1$ and $A$ cannot contain $S_4$.

Now, add the elements of $S_2$ to $A$, as sum of any two elements from $S_1$ $\cup$ $S_2$ is not divisible by $5$,

$A$ $=$ $A$ $\cup$ $S_2$ $=$ $S_1$ $\cup$ $S_2$

But, as all the elements in $S_2$ are of the form $(5n$ $+$ $2)$, we have to not select any element which is of the form $(5n$ $+$ $3)$, as that makes the sum divisible by $5$.

So,$A$ cannot contain $S_3$.

We cannot take all the elements of $S_5$ to $A$ as the sum of any two elements of $S_5$ is divisible by $5$,

But we can add one and only one element of $S_5$ into $A$ as sum of that element and any element chosen from $S_1$ $\cup$ $S_2$ is not divisible by $5$. Let the element be $k_5$.

Therefore, $A$ $=$ $S_1$ $\cup$ $S_2$ $\cup$ { $k_5$ }

Number of elements in $A$ $=$ (Number of elements in $S_1$) $+$ (Number of elements in $S_2$) $+$ $1$

$=$ $8$ $+$ $8$ $+$ $1$

$=$ $17$

Therefore, Maximum number of elements possible in $A$ is ${}^{\prime }{17}^{\prime }$.