Not a fan of 3

Probability Level 5

How many positive integers $n \leq 1000$ are there which satisfy the following condition:

We can rearrange the positive integers from 1 to $n$ in a row, where the sum of the first $k$ terms is not a multiple of 3, for every $1 \leq k < n$ .

Note: To avoid ambiguity, the integer 1 satisfies the above condition.

The answer is 1000.

2 solutions

Ariel Gershon
Jan 22, 2015

Let $m = \left\lfloor \dfrac{n}{3} \right\rfloor$ .

Then we can arrange the numbers as follows, into the sequence $(a_r)$ : $a_r = \left\{ \begin{array}{lr} 1 & : r = 1\\ \left\lceil\dfrac{3r+1}{2} \right\rceil & : 2 \le r \le n - m-1\\ 3(r-n+m+1) & : n-m \le r \le n - 1\\ 2 & : r = n \end{array}\right.$

It is easily verifiable that this sequence contains each number from $1$ to $n$ exactly once;

Define $S_r = \sum_{i = 1}^{r} a_i$ . Notice that the sequence starts with $1$ , so $S_1 = 1$ . Then this is followed by a sequence which alternates between $1 \pmod{3}$ and $2 \pmod{3}$ . Hence, in this section $S_r$ alternates between $2 \pmod{3}$ and $1 \pmod{3}$ .

The third section contains only multiples of $3$ , so in this section $S_r \equiv 1 \pmod{3}$ . Hence $S_r \not\equiv 0 \pmod{3}$ for $1 \le r < n$ .

Therefore, it is always possible to create such a sequence for all positive integers $n$ .

Nice explanation. (I'm going to use that as an excuse for not writing up my own explanation. :) )

One comment: I think that it would still work if you made $a_k = k+1$ for $1<k<n$ (still keeping $a_1 = 1$ and $a_n = 2$ ). That seems to be the simplest pattern that works, i.e. $1, 3, 4, 5, ..., n, 2.$

Peter Byers - 6 years, 4 months ago

P.S. So the sum of the first $k$ terms, for $k<n$ , is

$(k+1)(k+2)/2-2$

which is equivalent in $\mod 3$ to either $-2$ or $1-2=-1$ as desired.

Peter Byers - 6 years, 4 months ago

Oh you're right, that is simpler :)

Ariel Gershon - 6 years, 4 months ago

Vinay Sipani
Jan 23, 2015

The sequence is

1 2

1 3 2

1 3 4 2

1 3 4 2 5

1 3 4 2 6 5

1 3 4 2 6 7 5

1 3 4 2 6 7 5 8

1 3 4 2 6 7 5 9 8

1 3 4 2 6 7 5 9 10 8

1 3 4 2 6 7 5 9 10 8 11

1 3 4 2 6 7 5 9 10 8 12 11

1 3 4 2 6 7 5 9 10 8 12 13 11

1 3 4 2 6 7 5 9 10 8 12 13 11 14

Not a fan of 3

The answer is 1000.

2 solutions

0 pending reports