No 3's Allowed!

The key thing to notice here is that what matters is the position of the numbers that are either $1\bmod{3}$ and $2\bmod3$ . We simply want to position them such that the sum is never a multiple of three. Let's first start with the first number.

First, obviously, we can't have the first number as 3 or 6.

Now, what happens when we take a number that is $2\bmod3$ ? Here's the sequence that we get

2 - 2 - 1 - 1 - 1

(I do not include the numbers that are $0\bmod3$ because they do not affect the overall number modulo 3).

It is obvious to see that after the 2, we cannot put a number that is 1 modulo 3, as that leads to a sum that is a multiple of three. Thus, we are forced to put a 2; however, we now only have numbers that are 1 modulo 3 left, and we see that $2 + 2 + 1 + 1 = 6 \equiv 0 \bmod 3$ . Thus, we see that if we start with a number that is $2\bmod3$ , we cannot finish.

Thus, we now only have to deal with 1. Here's the only possible sequence

1-1-2-1-2

We can see this because the first 1 forces another 1, which forces a 2, which forces a 1, which forces a 2 (when I say force, I mean that otherwise you get a number that is a multiple of three).

Now, we have found our sequence. We just need to count the number of ways it can happen. It is obvious to see that there are $3! = 6$ ways to pick the numbers that are $1\bmod3$ and $2! = 2$ for those that are $2\bmod3$ . Thus, there are $12$ overall. However, don't be fooled: we're not done yet! We still have to put the numbers that are $0\bmod3$ in somewhere!

We first write out the sequence again:

1-1-2-1-2.

For the first number, it is evident that we have five spots for it; after the first 1, after the second 1, after the first 2, after the third 1, and after the third 2. Now, here is where we have to be careful. With the second number, we have those 5 spots, but, within the place where the first number was placed, we can either put it before or after. That yields 6 possibilities, so there are $6 * 5 = 30$ total ways to put the numbers that are $0\bmod3$ in.

Finishing up, we have $30 * 12 = \boxed{360}$ ways overall to permute the numbers and make all seven sums not multiples of three.

Since we're only concerned with having the sums not multiples of 3, it makes sense to look at the problem in $\bmod{3}$ first. The integers $1, 2, \cdots 7$ become $0, 0, 1, 1, 1, 2, 2 \pmod{3}$ and we must find permutations of those such that $s_1=p_1 \not\equiv 0 \pmod{3}, s_2=p_1+p_2 \not\equiv 0 \pmod{3}$ , and so on.

Note that if $p_k \equiv 0 \pmod{3}$ , then $s_k\equiv s_{k+1} \pmod{3}$ . Thus, as long as $p_1\not\equiv 0 \pmod{3}$ , it doesn't matter where we place the multiples of 3 in our permutation since they don't change the sums in $\bmod{3}$ .

Let's consider the permutations of $1, 1, 1, 2, 2$ (original set without the multiples of 3) and find those that have no partial sums a multiple of 3.

Case 1: $p_1\equiv 1 \pmod{3}$ .

$p_2 \equiv 1 \pmod{3}$ or else $s_2 \equiv 0 \pmod{3}$ . Likewise for the others, $p_3\equiv 2 \pmod{3}$ or else $s_3 \equiv 0 \pmod{3}$ . $p_4 \equiv 1 \pmod{3}$ or else $s_4 \equiv 0\pmod{3}$ and finally $p_5\equiv2\pmod{3}$ (the remaining element), yielding $(1, 1, 2, 1, 2)$ , which leaves no partial sum a multiple of 3.

Case 2: $p_1\equiv 2 \pmod{3}$ .

Like before, $p_2 \equiv 2 \pmod{3}$ or else $s_2 \equiv 0 \pmod{3}$ . $p_3\equiv 1 \pmod{3}$ or else $s_3 \equiv 0 \pmod{3}$ . $p_4 \equiv 2 \pmod{3}$ or else $s_4 \equiv 0\pmod{3}$ , but there are only two $2$ s in our set, so no valid permutations exist in this case.

Our only valid permutation in $\bmod{3}$ is $(1, 1, 2, 1, 2)$ , so what remains is counting the number of ways we can arrange ${1, 4, 7}$ and ${2, 5}$ in the permutation, and insert ${3, 6}$ anywhere except at the beginning.

There are $3!$ ways to arrange ${1, 4, 7}$ and $2!$ ways to arrange ${2, 5}$ . The $3$ can be inserted immediately after any of the $5$ elements in the permutation and $6$ can be inserted after one of $6$ elements (3 is inserted, so 6 elements).

Our final count is $3!\times 2!\times5\times6=\boxed{360}$ .

Let's think of the numbers 1 through 7 mod 3, so instead of dealing with {1,2,3,4,5,6,7}, we deal with {1,2,0,1,2,0,1}. A permutation of the integers 1-7 will not encounter a multiple of 3 if the same can be said of their mod 3 counterparts! This is because the mod 3 value of a sum is the sum of the mod 3 values.

Thus we only have to count the lists of three 1's, two 2's, and two 0's, that don't encounter a multiple of 3. This task is even made easier by noticing that we can ignore the 0's initially (since they don't change the running sum).

So let's start by listing the three 1's and two 2's. Suppose our list starts with a 1. A moment's reflection should reveal that the next number must be a 1, or else we'd hit a multiple of 3. After that, the next number must be a 2. Continuing this logic, we see that our sequence must be {1,1,2,1,2}. If, on the other hand, our list starts with a 2, we see that we get stuck! Once our list gets to {2,2,1}, we can't continue building without hitting a multiple of 3. Therefore, our 1's and 2's must appear in the order {1,1,2,1,2}.

Next, we observe that the two 0's can go anywhere in between the 1's and 2's except before the first entry (otherwise the first term would be a multiple of 3: zero), and they can both go to the same spot (example: {1,1,2,0,0,1,2} works). A quick counting gives us 15 ways of doing so (5 possible spots, so (5 choose 2)=10 ways for separate spots + 5 ways for same spot). Thus there are exactly 15 possible lists of the 0's, 1's, and 2's.

Now all that is left is to reassign the true integer values. Each integer can be assigned to any spot with its mod 3 counterpart. For example, the 7 (equal to 1 mod 3) can go anywhere we see a 1 in our mod 3 list. To illustrate, one assignment of the integers to the list {1,1,2,0,0,1,2} can be {7,4,5,6,3,1,2}. Therefore, for any fixed {0,1,2}-list, there are 3! ways to choose the spots for the [1 mod 3] numbers, 2! ways to place the [2 mod 3] numbers, and 2! ways to place the [0 mod 3] numbers, for a total of 3!2!2! = 24 ways per list. Multiplying this by the number of {0,1,2}-lists gives a grand total of 24*15 = 360 permutations .

Let $P' = (p'_1,p'_2,...,p'_5)$ be a permutation of the integers $1,2,4,5,7$ , and $S'_n = \sum_{i=1}^n p'_i$ for $n = 1,2,...,5$ . $3 \nmid S'_4 \Rightarrow p'_5 \equiv 2 \pmod{3}$ , $3 \nmid S'_3 \Rightarrow p'_4 \equiv 1 \pmod{3}$ , $3 \nmid S'_2 \Rightarrow p'_3 \equiv 2 \pmod{3}$ , so $p'_1 \equiv p'_2 \equiv 1 \pmod{3}$ . Thus there are $3!*2!$ permutations $P'$ such that $3 \nmid S'_n$ for $n = 1,2,...,5$ . For each such $P'$ , we can insert the numbers $3$ and $6$ anywhere after $p'_1$ and still have the partial sums not multiples of $3$ . There are ${6 \choose 2}*2!$ ways that this can be done, so there are $3!*2!*{6 \choose 2}*2! = 360$ permutations $P$ .

We divide {1,2,...,7} into residue classes mod 3: there are 3 entries with remainder 1, and remainders 0 and 2 each have 2 entries. This is a many-to-one mapping: for each distinct arrangement of these 0s, 1s and 2s having the desired property, there are 3! 2! 2! = 24 corresponding permutations of length 7.

Let us now count such arrangements, which we'll call "valid" if they have the partial sum property. We apply a many-to-one compression to these by deleting all 0s. Any sequence that is valid before deletion obviously retains that property. Conversely, given any valid sequence of three 1s and two 2s, we can insert 0s anywhere except at the front without breaking validity: so for any valid compressed sequence there are exactly C(6,4) = 15 ways to repopulate the 0s.

The number of permutations is thus 24*15 = 360 times the number of valid sequences of three 1s and two 2s. We claim that all valid sequences of 1s and 2s are uniquely determined by their first term: each subsequent term must have a partial sum whose residue class is non-zero (because of the desired property) and different from the previous partial sum (because 1 and 2 are non-zero mod 3), which only ever gives one choice.

Following this argument shows that the only valid sequences of length 5 are 11212 and 22121, of which only the first has the correct inventory of 1s and 2s. Thus the compressed sequence is unique as claimed, and there are only 360 permutations that do the job.

First we "project" everything to modulo 3. Given the set of $(1, -1, 0, 1, -1, 0, 1)$, how many permutations are there such that each cumulative sum is never 0 modulo 3? For example, the sequence $(1,0,1,1,-1,0,-1)$ would be allowed but the sequence $(1,1,0,1,-1,-1,0)$ is not allowed because after four elements, the sum is 3.

Ignoring all the zeros first, how can we arrange 3 ones and 2 -1s so that no cumulative sum is never 0? It's easy to see that the only possibility is $(1,1,-1,1,-1)$, by considering the facts below:

1. The final sum is +1, so it must not start with -1, otherwise at some point it has to "cross" over and be exactly zero.
2. Because it starts with +1, the second one must be +1 as well. From here, the only possibility is +1+1+1-1-1 (wrong after the third element) or +1+1-1-1+1 (wrong after the fourth element) or +1+1-1+1-1.

Now we incorporate the zeros. Remember that the zeros can be put in anywhere and it will not alter the cumulative sums modulo 3. The only place where it cannot be put in is in the beginning, because otherwise we can a cumulative sum of zero immediately.

Imagine 7 slots in a row, where the first slot is permanently taken by +1. From the 2nd to 7th slots, we may choose any two to be occupied by zero, and the rest will be filled out in the following sequence: +1, -1, +1, -1. There are 6C2 = 15 ways to choose.

At this point we have a sequence of 7 numbers whose cumulative sum is never divisible by 3. We need to "unproject" it back to the elements of $P$.

1. The +1s in that sequence could be replaced by 1,4,7 in any order, there are 6 ways to do this

2. The -1s in that sequence could be replaced by 2,5 in any order, there are 2 ways.

3. The 0s in that sequence could be replaced by 3,6 in any order, there are 2 ways to do it.

So the total number of ways is 15.6.2.2 = 360

First, all the numbers can be placed into three groups, 1 mod 3 (3 numbers), 2 mod 3 (2 numbers) and 0 mod 3 (2 numbers). That implies that s1, s2, s3, s4, s5, s6, s7 all must be either 1 mod 3 or 2 mod 3. p1 cannot be from 0 mod 3. Consider this, numbers are chosen in rounds and each time a number is chosen, the total becomes s of the nth round. If the number of numbers from 1 mod 3 is equal to the number of numbers from 2 mod 3, regardless of how many 0 mod 3 numbers, the total will be a multiple of three. Hence, there must be more numbers from 1 mod 3 than from 2 mod 3 at in all rounds (just because there are 3 numbers from 1 mod 3 as opposed to 2 from 2 mod three). If there first number is from 2 mod 3, then eventually, one of the rounds will feature equal number of 1 mod 3 and 2 mod 3 numbers (because by the last round, there must be three 1 mod 3 numbers and two 2 mod 3 numbers). So the possibilities for p1 are 3.

Now we can place the two 0 mod 3 numbers in any position, as it does not alter the total in each round. There are 15 ways of placing the two 0 mod 3 numbers in 6 possible spots.

The remaining four spots can be isolated now. The first of the four is in a round in which the previous total was 1 mod 3, hence, the number must be from 1 mod 3 to ensure that the total for the round is not 0 mod 3. 2 possibilities for the first of four.

The last number mustn't be from 1 mod 3, or else the second of third of four spots will be from 2 mod 3 and the total after the third of four spots will have equal number of 1 mod 3 and 2 mod 3. Thus, there are two possibilities for the last of four positions.

There are now two possibilities to fill the second and third of four spots.

2 2 2 15 3 =360 total permutations.

There are 3 numbers that are $1\pmod 3$ , and two that are $0\pmod 3$ and $2\pmod 3$ . Since 0's do not change the sum, we can put those in at the end.

Then, it we start with 1, we get 1,1,2,1,2. Each term after the first is uniquely defined, since one value 1,2 will give a multiple of 3. This works since we have 3 1's and 2 2's.

If we start with 2, we get 2,2,1,2,1. Again, each term is uniquely defined. This does not work, since we have only 2 2's.

Now, we insert the 0's. By stars and bars , and since $p_1$ cannot be 0, there are $\dbinom{5+2-1}{2}=15$ ways to place the 0's.

Finally, there are $2!$ ways to assign $\{3,6\}$ to the values $0\pmod 3$ , $2!$ ways to assign $\{2,5\}$ to the values $2\pmod 3$ , and $3!$ ways to assign $\{1,4,7\}$ to the values $1\pmod 3$ , so the answer is $2!2!3!\cdot 15=\boxed{360}$

It would be easier to work with remainders to count whether the sums are multiples of $3$ . Notice that $1, 2, 3, 4, 5, 6, 7$ is just $1, 2, 0, 1, 2, 0, 1 \mod{3}$ , respectively.

For this step of the problem, assume that the remainders $1, 1,$ and $1$ and so on are indistinguishable. In order for the sums $S_n$ to not be multiples of $3$ , we must have the remainders excluding $0$ to be $1, 1, 2, 1, 2$ (note that we cannot begin the sequence with $2$ since this would lead to $2, 2, 1, 1, 1$ , which has a multiple of three). We now count the number of ways to insert the two zeros into the sequence $1, 1, 2, 1, 2$ . A zero cannot be in the first position, or else $S_1$ would be a multiple of three. Besides this restriction, the zeros can be placed anywhere. The first zero can be placed into $5$ spots (between the two $1$ 's, $1$ and $2$ , etc., and after the $2$ ). The second zero can be placed into $6$ spots, the same number as the first zero, just can be before or after the first zero. Finally, divide this by $2$ since both zeros are indistinguishable, so $5 \cdot 6 /2=15$ (this also can be verified by listing)

So the total number of permutations is just $15 \cdot 3! \cdot 2! \cdot 2!=\boxed{360}$ , since we have $3!$ ways to arrange the $1$ 's, $2!$ ways to arrange both the $2$ 's and $0$ 's.

We have two numbers equivalent to $0\pmod{3}$ , three equivalent to $1\pmod{3}$ , and two equivalent to $2\pmod{3}$ . So all we have to do is find how many arrangements of $0011122$ exist with this property and multiply by $(2!)(3!)(2!)$ to account for the permutations.

Let's ignore the numbers equivalent to $0\pmod{3}$ , we'll add them in afterwards. Starting with $1$ , we have the arrangement $11212$ , and starting with $2$ , we have $22121$ which is invalid since we only have two $2$ s.

Now we need to find out how many ways we can inject two $0$ s into the arrangement $11212$ . Since we know the first number must be $1$ , we have ${6\choose2}$ ways to do this.

Thus, the total number of ways is ${6\choose2}(2!)(3!)(2!)=\boxed{360}$ ways.

We consider the numbers modulo $3$ : $\{3,6\}$ are $0 \pmod{3}, \{1,4,7\}$ are $1 \pmod{1}, \{2,5\}$ are $2 \pmod{3}$ . So we want $S_i \equiv 0 \pmod{3}$ to never occur. We may start the permutation with a number $1$ or $2$ modulo $3$ . We first avoid including $0$ 's in the permutations as they can be included later, using the fact that if a $0$ is included at position $i$ , then $S_{i-1} \equiv S_i \pmod{3}$ . Consider all sequences mod $3$ hereon.

• Starting by $1$ , we get the sequence (excluding $0$ 's): $1,1,2,1,2$ . Now $0$ can be included between two adjacent numbers or at the end. Thus one multiple of $3$ has $5$ choices, the second multiple has $6$ choices(as inclusion of the former $3$ -multiple adds $1$ more gap) & we can permute numbers which are $1,2 \pmod{3}$ . So total choices here are: $3! \times 2! \times 5 \times 6 = 360$ .

• If we start with $2$ , we end up with: $2,2,1$ . Now next we should place $2$ so that $S \equiv 2 \pmod{3}$ but we don't have another number $2 \pmod{3}$ ,so this sequence can't be completed.

So we have $360$ such permutations possible.

Since we are only concerned with sum mod 3, we can remove the integers 3 and 6 for now since they can appear anywhere in the sequence except for the first number, since $p_1$ is not a multiple of 3.

Similarly, we reduce the numbers to their remainder modulo 3, so we are left with $(1,1,1,2,2)$ .

We cannot start with 2 since the second number has to be 2, which makes the rest of the sequence 1. But $2+2+1+1=6$ is divisible by 3, which makes one of $S_4, S_5,S_6$ a multiple of 3. So the sequence has to start with 1.

Simple case checking shows us that $(1,1,2,1,2)$ is the only possible arrangement. Now, we add 3 and 6 back and restore the numbers to their original value to calculate the number of permutations. There are $3!=6$ ways to arrange $(1,4,7)$ and 2 ways to arrange $(2,5)$ . If 3 and 6 are together, we have $5.2!=10$ ways to arrange them. If they are separated, we have $5.4=20$ ways to arrange them. Altogether, the number of permutations is $6.2.(10+20)=360$ permutations.

+'s denotes number of form 3n+1 -'s denotes a number of form 3n-1

It is obvious that the only possibility is + + - + - I have left out the occurance of zero because if it comes in between then it does not change the multiplicity by 3. Also 0 cannot be the first place

take 2 cases. Both zeroes together: 5 options Both zeros seperately: 5C2 options.

Also there are 3!, 2!, 2! permutations respectively within the +'s , -'s and zeros.

hence (5+10)*3!.2!.2! ways.

It's enough to work modulo $3$ . The requirement is that the running sum $S \not \equiv 0 \pmod 3$ . So it's congruent to either $1$ or $2$ . In each case, we can only add number that is either congruent to $S$ or to $0$ . Disregarding $0$ for a little bit (since it doesn't change the congruence), we are switching congruence classes as we progress in the sum. This implies that the permutation has to start with a number congruent to $1$ (because there are more of them than those congruent to $2$ .

Schematically, the classes of the running sum must be $1 \to 1 \to 2 \to 1 \to 2$ . There are $12$ ways how to order $1, 2, 4, 5, 7$ this way. Returning back to the zero congruences, we are free to put those anywhere after the beginning of the permutation. So there are $6 \cdot 5 = 30$ possibilities. Because these constructions are independent, there is a total of $12 \cdot 30 = {\bf 360 }$ permutations.

I really like this problem. Firstly, we group the seven numbers in three categories: 3 and 6; 1, 4 and 7; 2 and 5 (reminders 0, 1, 2 at division by 3). Two small observations here: p1 couldn't be 3 or 6; p7 couldn't be 1, 4, or 7. All the sums are not multiples of 3 * if an only if * the reminders are in this order (I try and write all the ways, we can not begin with 0 and nor with 2): * 1, 1, 2, 1, 2 * . The reminders zero could be anywhere but not in the first position. And now we can count the allowed permutation. p1 could be 1, 4 or 7, so 3 ways. The two reminders zero, 3 and 6, can be put in 30 ways (2 positions from six available). The last 4 reminders can be arranged in 4 ways (in order 1, 2, 1, 2). Totally, we'll obtain 360 permutations !!!

Python code:

L = range(1,8)

import itertools

A=list(itertools.permutations(L))

def not3(l):

s = 0

for i in range(7):

    s = s + l[i]

    if s % 3 == 0:

        return False

return True

len([i for i in A if not3(i)])

360

The numbers $1,2,3,4,5,6,7 \:mod \:3$ are $1,2,0,1,2,0,1$

If the sums are never a multiples of $3$ then we can see that at any point in the chain, ignoring the $0's$ , every $1$ must be followed by a $1$ , every $2$ must be followed by a $2$ and no three $1's$ can appear consecutively.

Since two $1's$ must come consecutively before they can be followed by a $2$ and since there are three $1's$ , the only way to write the order of the numbers $mod \: 3$ is $1,1,2,2,1$ . The zeroes can come after any of the numbers in the chain as long as they aren't at the front, and so we can see there are $15$ ways to arrange the $0's$ However, because there are two numbers that $= 0 \: mod \: 3$ there are actually $30$ ways to arrange the $0's$ .

There are also $3*2*2*1*1 = 12$ ways to arrange all the other numbers in the given format.

This means that in total there are $12*30 = 360$ permutations.