Inspired by Division by 3

Number Theory Level 2

Given $n$ is a positive integer divisible by 3, and the list below consists of $n$ sums, how many of the sums are divisible by 3?

$\begin{array}{l} 1 \\ 1 + 2 \\ 1 + 2 + 3 \\ 1 + 2 + 3 + 4 \\ 1 + 2 + 3 + 4 + 5 \\ 1 + 2 + 3 + 4 + 5 + 6 \\ \vdots \\ 1 + 2 + 3 + \cdots + n \\ \end{array}$

\frac{1}{3}n

\frac{1}{2}n

\frac{2}{3}n

\frac{3}{4}n

\frac{5}{6}n

1 solution

Marta Reece
Jun 1, 2017

I will show this by induction. Let's start with the first three numbers:

$1$

$1+2$

$1+2+3$

The first is not divisible by $3$ , the other two are.

Since $n$ is divisible by $3$ , the entire list can be divided into $m=\frac{n}{3}$ groups of three each, the first group being the one above.

I will show that if the sum $S$ of the last line of the $m-1$ triplet is divisible by $3$ , the next triplet repeats the pattern - the first line is not divisible by $3$ and the following two are.

The triplet number $m$ can then be written as:

$S+(n-2)=S+n-2$

$S+(n-2)+(n-1)=S+2n-3$

$S+(n-2)+(n-1)+n=S+3n-3$

Since $S$ and $n$ are both divisible by $3$ , the first line of the triplet is not while the following two are.

Since the entire list can be divided into groups of three, with two out of each group divisible by $3$ , $\boxed{\dfrac23}$ of the entire list is divisible by $3$ .

Inspired by Division by 3

1 solution

0 pending reports