Question

Number of ways of selecting three integers from $\{1,2,3,...,n\}$, if their sum is divisible by $3$ is

• A. $3\left({}^{n/3}{C}_3\right)+{\left(\frac{n}{3}\right)}^3$ if $n=3k,kϵN$
• B. $2\left({}^{(n-1)/3}{C}_3\right)+\left({}^{(n+2)/3}{C}_3\right)+{\left(\frac{n-1}{3}\right)}^2\left(\frac{n+2}{3}\right)$, if $n=3k+1,kϵN$
• C. $2\left({}^{(n+1)/3}{C}_3\right)+\left({}^{(n-2)/3}{C}_3\right)+{\left(\frac{n+1}{3}\right)}^2\left(\frac{n-2}{3}\right)$, if $n=3k+2,kϵN$
• D. Independent of $n$

Answer 1

Answer: (A), (B), (C)

The correct options are
A $3\left({}^{n/3}{C}_3\right)+{\left(\frac{n}{3}\right)}^3$ if $n=3k,kϵN$
B $2\left({}^{(n-1)/3}{C}_3\right)+\left({}^{(n+2)/3}{C}_3\right)+{\left(\frac{n-1}{3}\right)}^2\left(\frac{n+2}{3}\right)$, if $n=3k+1,kϵN$
C $2\left({}^{(n+1)/3}{C}_3\right)+\left({}^{(n-2)/3}{C}_3\right)+{\left(\frac{n+1}{3}\right)}^2\left(\frac{n-2}{3}\right)$, if $n=3k+2,kϵN$

When $n=3k$, there are exactly $n/3$ integers of each type $3p,3p+1,3p+2$.
Now, sum of three selected integers is divisible by $3$. Then either all the integers are of the same type $3p,3p+1$ or $3p+2$ or one-one integer from each type.
Then number of selection ways is
${}^{n/3}{C}_3{+}^{n/3}{C}_3{+}^{n/3}{C}_3+{(}^{n/3}{C}_1\left){(}^{n/3}{C}_1\right){(}^{n/3}{C}_1)=3{(}^{n/3}{C}_3)+(n/3{)}^3$
If $n=3k+1$, then there are $\frac{n-1}{3}$ integers of the type $3p,3p+2,$ and $\frac{n+2}{3}$ integers of the type $3p+1$. Then number of selection ways is
$2\left({}^{(n-1)/3}{C}_3\right)+\left({}^{(n+2)/3}{C}_3\right)+{\left(\frac{n-1}{3}\right)}^2\left(\frac{n+2}{3}\right)$
When $n=3k+2$, then there are $\frac{n+1}{3}$ integers of the type $3p,3p+2,$ and
$\frac{n-2}{3}$ integers of the type $3p+1$. Then number of
selection ways is
$2\left({}^{(n+1)/3}{C}_3\right)+\left({}^{(n-2)/3}{C}_3\right)+{\left(\frac{n+1}{3}\right)}^2\left(\frac{n-2}{3}\right)$.