For small $ n$, we can check that $ |A_1| = 1$, $ |A_2| = 2$, $ |A_3| = 6$, $ |A_4| = 12$. Suppose $ n \geq 5$. If $ (a_1, \ldots, a_n)$ is a permutation in $ A_n$, then \[ n - 1 \,|\, 2 (a_1 + \cdots + a_{n-1}) = n (n + 1) - 2 a_n = (n + 2)(n - 1) + 2 - 2a_n\] and consequently $ n - 1 \,|\, 2 (a_n - 1)$, from which $ a_n \in \{1, \tfrac{n+1}{2}, n\}$. If $ a_n = \tfrac{n+1}{2}$, then \[ n - 2 \,|\, 2 (a_1 + \cdots + a_{n-2}) = n (n + 1) - n - 1 - 2a_{n-1} = (n - 2) (n + 2) + 3 - 2a_{n-1}\] and consequently $ n - 2 \,|\, 2a_{n-1} - 3$, or $ a_{n-2} = \tfrac{n+1}{2} = a_{n-1}$, contradiction. Therefore, if $ (a_1, \ldots, a_n) \in A_n$, it must be $ a_n = n$ or $ a_n = 1$. There are $ |A_{n-1}|$ permutations of the first kind, and as a permutation $ (a_1, \ldots, a_n)$ of the second kind corresponds bijectively to a permutation of the first kind by $ (a_1, \ldots, a_n) \to (n + 1 - a_1, \ldots, n + 1 - a_n)$, there are $ |A_{n-1}|$ permutations of the second kind. Consequently, for $ n \geq 5$, $ |A_n| = 2 |A_{n-1}|$, which means that $ |A_n| = 3 \cdot 2^{n-2}$ for $ n \geq 3$ and $ |A_1| = 1$, $ |A_2| = 2$.

plz correct Iran's 2002 second round 1st problem.

Let Fn be the number of such permutaions for n.It is easy to see that F1=1,F2=2,F3=6.Now,let n>=4.Now,we easy obtain An can be 1 or n,so we have 2 cases: 1)If An=n,we have that the number of permations in this case is obviously Fn-1(induction on 1,2...,n-1) 2)If An=1,we have that number of permutaions is also Fn-1, 'cause the permutaion A1+1,A2+1,A3+1,...Ak+1 satisfies iff the permutaion A1,A2,...Ak satisfies,so we are done. We conclude that for n>=4 Fn=2*Fn-1 and F3=6,so Fn=2^n-2*3,so we are finished.

For $n = 2, 3$, it's easy to see there are $2, 6$ permutations that work. Otherwise, suppose $n \ge 3$. From $n-1 | 2(a_1+\cdots +a_{n-1})$, we get $n-1 | 2(n(n+1)/2-a_n) = n(n+1)-2a_n$. So \[n^2+n \equiv 2a_n \pmod{n-1}\]\[\Rightarrow 2a_n \equiv 2 \pmod{n-1}\] If $n$ is even, then $a_n \equiv 1\pmod{n-1}$ so $a_n = 1, n$. If $n$ is odd, write $n = 2n_1+1$ to get $s \equiv 1 \pmod{n_1}$, so $s = 1, n_1+1, 2n_1+1$. If $s = n_1+1$, we then have \[n-2 | 2(n(n+1)/2-(n+1)/2-a_{n-1}) = (n-1)(n+1)-2a_{n-1}\]\[\Rightarrow 2a_{n-1} \equiv 3 \pmod {n-2}\]Since $n-2$ is odd, $a_{n-1} \equiv (n+1)/2 \pmod{n-2}$ so $a_{n-1} = (n+1)/2 = a_{n}$. So $a_{n}$ can be $1$ or $n$. But if $a_n = n$, this is just the case for $n-1$ and when $a_n = 1$ we can just subtract $1$ for each $a_i$ and get the case for $n-1$ (this does not affect divisibility as for each $k$ we subtracted off a multiple of $k$). Thus each time we multiply by $2$, and we get $A_n$ has $6*2^{n-3} = 3*2^{n-2}$ elements.

We have \[ n-1 \mid 2\left(\frac{n(n+1)}{2} - a_n\right) = n(n+1) - 2a_n,\]so $2a_n\equiv n(n+1) \equiv 1\cdot 2 =2\pmod{n-1}$. Hence either $a_n= 1, a_n = \tfrac{n+1}{2}, a_n=n$. If $a_n = \tfrac{n+1}{2}$, then \[ n-2 \mid 2(a_1+\cdots+a_{n-2}) = 2\left[\frac{n(n+1)}{2}-\frac{n+1}{2}-a_{n-1}\right] = n^2-1 - 2a_{n-1},\]whence $2a_{n-1} \equiv n^2-1 \equiv 3\pmod{n-2}$. Hence $a_{n-1}=\tfrac{n+1}{2}$, contradiction. Therefore, either $a_n=1$ or $a_n=n$. If $a_n=n$, there are clearly $|A_{n-1}|$ ways to finish. If $a_n=1$, then subtracting 1 from every element also gives $|A_{n-1}|$ ways to finish. Hence, $|A_n| = 2|A_{n-1}|$. Since $|A_3| = 6$, we get $|A_n| = 3\cdot 2^{n-2}$.

We claim the answer is $|A_n| = 3 \cdot 2^{n-2}$, except for the cases of $|A_1| = 1$, $|A_2| = 2$, and $|A_3| = 6$, which are trivial. Take $k = n - 1$. Because we know that $a_1, a_2, \cdots, a_n$ is some rearrangement of $1, 2, \cdots, n$, we can write the divisibility as $$n-1 | 2(a_1 + a_2 + a_3 + \cdots + a_{n - 1}) = 2 \left(\frac{n(n+1)}{2} - a_n \right) = n(n + 1) - 2a_n.$$Subtracting $(n - 1)(n + 2)$ from the right, we end up with $$n - 1 | 2(a_n - 1).$$When $n$ is even, this only has the integer solutions $a_n = 1$, $a_n = n$, but when $n$ is odd, it has the additional solution $a_n = \frac{n+1}{2}$ alongside the other two. We will first handle the $1$ and $n$ cases; observe that for $a_n = n$, this simply reduces to the $A_{n-1}$ case. For $a_n = 1$, observe that we can shift every $a_i$ by a constant without affecting the divisibility. Thus, shift all $a_i$ down by $1$ to reduce to the $A_{n-1}$ case again. For the $a_n = \frac{n + 1}{2}$ case, set $n = 2n' - 1$ which turns $a_n = n'$. Then, we can use the shift trick again by scaling down by $n'$, which gives us the numbers $-(n' - 1), -(n' - 1), \cdots , -1, 1, 2, \cdots, n' - 1$. Now, consider $k = n - 2 = 2n' - 3$. We know that one of the numbers in the previous set must not be present in the sum; however, this directly leads to a contradiction as we can pair every other $a_i$ with another $a_j = - a_i$ to get a zero sum. Since none of the numbers in the set are divisible by $n - 2$, we are done. Our recursion is thus $|A_n| = 2|A_{n-1}|$, which leads to the closed form $|A_n| = 3 \cdot 2^{n-2}$, as desired.

It's easy to see that $|A_1|=1,|A_2|=2,|A_3|=6$. Now, suppose that $n\ge 4$; we claim that $|A_n|=3\cdot 2^{n-2}$. We have $$2(a_1+\ldots +a_n)=n(n+1)\equiv 2\pmod{n-1}$$, and therefore it's necessary that $2a_n\equiv 2\pmod{n-1}$; this is only possible when $a_n=1,n,\frac{n+1}{2}$, with the last case being exclusive to odd $n$. When $a_n=n$, we can reduce the problem down to the $n-1$ case, giving us $|A_{n-1}|$ solutions. When $a_n=1$, note that we can form a bijection between every permutation of this case with every permutation with $n-1$ elements by shifting every element by 1, giving us another $|A_{n-1}|$ solutions. When $a_n=\frac{n+1}{2}$, then we can take mod $n-2$ to get that $$n(n+1)-(n+1)-2a_{n-1}\equiv 0\pmod{n-2}$$, which forces $2a_{n-1}$ to be 3 mod $n-2$ and therefore also equal to $n+1$, contradiction. Now, we have the recursion $|A_n|=2|A_{n-1}|$, which verifies our claim.

mathleticguyyy wrote: When $a_n=\frac{n+1}{2}$, then we can take mod $n-2$ to get that $$n(n+1)-(n+1)-2a_{n-1}\equiv 0\pmod{n-2}$$, which forces $2a_{n-1}$ to be 3 mod $n+2$ and therefore also equal to $n+1$, contradiction. A small typo. It should be $2a_{n-1}$ to be $3$ mod $n-2$ Also why does the recursion stated in all the above solutions not work for $n= 3$ but works for all other $n\geq4$

Combigeontal231 wrote: mathleticguyyy wrote: When $a_n=\frac{n+1}{2}$, then we can take mod $n-2$ to get that $$n(n+1)-(n+1)-2a_{n-1}\equiv 0\pmod{n-2}$$, which forces $2a_{n-1}$ to be 3 mod $n+2$ and therefore also equal to $n+1$, contradiction. A small typo. It should be $2a_{n-1}$ to be $3$ mod $n-2$ Also why does the recursion stated in all the above solutions not work for $n= 3$ but works for all other $n\geq4$ For $n=3$, we have that $n(n+1)$ is 0 mod 2; though, for all $n>3$, $n+1$ cannot be a multiple of $n-1$.

We claim that $|A_1|=1,|A_2|=2,$ and $A_n=3\cdot 2^{n-2}$ for $n>2.$ We can check the first three cases manually, so it suffices to show that $|A_{n}|=2|A_{n-1}|$ for $n\ge 4.$ $\textbf{Case 1: }$ $n$ is even Then, $n-1$ is odd, so $$a_1+a_2+\dots+a_{n-1}=\frac{n(n+1)}{2}-a_n\equiv 1-a_n\pmod{n-1}.$$Hence, $a_n=n$ or $a_n=1.$ If the prior, there are clearly $|A_{n-1}|$ ways to assign the remaining numbers. If the latter, we can biject each working permutation of the remaining numbers to a working permutation of $\{1,2,\dots,n-1\}$ by simply subtracting $1$ from each element. Thus, $|A_n|=2|A_{n-1}|$ in this case. $\textbf{Case 2: }$ $n$ is odd Note that $$a_1+a_2+\dots+a_{n-1}=n\left(\frac{n+1}{2}\right)-a_n\equiv 1-a_n\pmod{(n-1)/2}.$$This implies that $a_n=n,$ $a_n=1,$ or $a_n=\frac{n+1}{2}.$ Using the same reasoning as Case 1, we can show that the first two possibilities yield exactly $2|A_{n-1}|,$ so it suffices to prove that $a_n=\frac{n+1}{2}$ yields no permutations. Indeed, just compute that $$a_1+a_2+\dots+a_{n-2}=\frac{n^2-1}{2}-a_{n-1}\equiv 3\left(\frac{n-1}{2}\right)-a_{n-1}\equiv\frac{n+1}{2}-a_{n-1}\pmod{n-2}.$$Since no remaining number is congruent to $\frac{n+1}{2}$ modulo $n-2,$ we are done.

Sort of similar to the recursive ideas in the above solutions, but praised in terms of an induction. We have that $|A_1|=1, |A_2|=2,$ for $n\geq 3,$ we have that $|A_n|=2^{n-2}\cdot 3$. It is easy to check the base case $n=3$. Suppose the result is true for $n-1$. We prove it is true for $n$ by casework on the parity of $n$. Case 1: $n$ is even If $n$ is even, then $n-1$ is odd, and we must have that $n-1|2(\sum_{i=1}^{n-1}a_i)\implies n-1|\sum_{i=1}^{n-1}a_i$. We have to chose some $k$ to be $a_n,$ and that value of $k$ must satisfy $\frac{n(n+1)} 2 - k\equiv 0\pmod {n-1}$. Since $n-1$ is odd, $2$ has an inverse, so we can do $k\equiv \frac{n(n+1)}{2}\equiv (1\cdot 2)/2\equiv 1\pmod {n-1}$. Therefore, there are $2$ choices for the final element. Notice that the ordering of the rest of the elements degenerates to the case of $n-1,$ and therefore by the inductive hypothesis we are done. Case 2: $n$ is odd. We have that $n-1|2(\sum_{i=1}^{n-1}a_i)$. We choose some $k$ such that $n(n+1)-2k\equiv 0\pmod{n-1}\implies 2k\equiv 2\pmod{n-1}$. $n-1$ is even, so we get that $k\equiv 1\pmod {\frac{n-1}{2}}$. This gives us the possibles of $k$ being $1, \frac{n+1} 2, n$. Clearly, $1$ and $n$ degenerate off to lower cases, so if we can show that $\frac{n+1} 2$ does not work, by the inductive hypothesis we would be done. Using the condition for $n-2$, we get that $\frac{(n-1)(n+1)}{2}-k\equiv 0\mod {n-2}\implies k\equiv \frac{3}{2}\equiv {n+1}{2},$ where many of our manipulation depend on the fact that $n-2$ is odd. It is easy to derive a contradiciton(although we may have to extend the bases so $n+1<2n-4$ to force the number to be unique in the permutation, and we can derive the need contradction. We are done.

We proceed via induction. The base case is trivial. Claim : $a_n=n$ or $1$ Proof : Note that $a_1+a_2+ \dots + a_n= \frac{n(n+1)}{2}$. As we have $n-1 | 2(a_1+a_2+ \dots + a_{n-1}) \implies n-1 | n(n+1)-2a_n \implies n-1|2a_n \implies n-1|2a_n-2$ after a few manipulations. Clearly $a_n \leq n$, so we have the following cases : $2a_n-2=2n-2 \implies a_n=n$ $2a_n-2=n-1 \implies a_n =\frac{n+1}{2}$ $2a_n=2 \implies a_n=1$. If $a_n=\frac{n+1}{2}$, as must have $n-2|a_1+a_2+ \dots + a_{n-2} \implies n-2| n^2-1-2a_{n-1} \implies n-2|2n-1-2a_{n-1}$. Notice that $2n-1-2a_{n-1} =-1$ can be ignored on checking $n=3$. So assume $n^2-1-2a_{n-1} \geq 0$. We clearly see that $2n-1-2a_{n-1} \leq 2n-1$, so we only have three cases to check, from which we deduce that $a_{n-1}=\frac{n+1}{2}$, which is clearly a contradiction. Now that we have our claim proven, we are almost done. Claim : The number of permutations is $3\times2^{n-2}$. Proof : Let it hold true for $n$. We prove it true for $n+1$. Note that $a_{n+1} \in \{1, n+1\}$. It’s easy to see that the two resulting sequences correspond bijectively. So in total, we have $2 \times 3 \times 2^{n-2}$ permutations, as desired.

This is a very cool problem Let $A_n$ instead denote the number of permutations satisfying the condition for some $n$. We claim that $A_1 = 1, A_2 = 2, A_3 = 6$, and $A_n = 3 \cdot 2^{n-2}$ for all $n \geq 4$. Assume from now on that $n \geq 4$. Notice that by setting $k=n-1$, $$0 \equiv 2(a_1+...+a_{n-1}) \equiv 2 \cdot \frac{n(n+1)}{2} - 2a_n \equiv 2(a_n-1) \pmod{n-1}$$Then, unless $n$ is odd and $a_n = \frac{n+1}{2}$, $a_n \in \{1,n\}$ which we will deal with later. $\textbf{Claim:}$ $a_n \neq \frac{n+1}{2}$ $\textbf{Proof)}$ Assume FTSOC that $a_n = \frac{n+1}{2}$ and consequently that $n$ is odd. Then, $$0 \equiv 2(a_1+...+a_{n-2}) \equiv n(n+1) - 2a_{n-1}-2a_n \equiv 6-3 - 2a_{n-1} \equiv 3 - 2a_{n-1} \pmod{n-2}$$Then, $$a_{n-1} \equiv \frac{3}{2} \equiv \frac{n+1}{2} \pmod{n-2} $$using the fact that $n-2$ is odd. Then, as $a_{n-1} \in \{1,..,n\}$ and $a_{n-1} \neq a_n = \frac{n+1}{2}$ we must have that $$\frac{n+1}{2} \equiv 1,2 \pmod{n-2}$$. Then either $n-2 \mid n+1-2 = n-1$ or $n-2 \mid n-3$ neither of which can happen unless $n \leq 3$ which is ultimately a contradiction. $\square$ Now, firstly notice that by taking $a_i \rightarrow n+1-a_i$ for all $i \in \{1,..,n\}$, we have a bijection between permutations such that $a_n = 1$ and $a_n = n$. Moreover, there is clearly a bijection between permutations that satisfy the condition for $n-1$ and permutations satisfying the condition for $n$ such that $a_n = n$. We consequently, have that $$A_n = 2 \cdot A_{n-1} = 3 \cdot 2^{n-2}$$for all $n \geq 4$ and we therefore get the initially desired conclusion. $\blacksquare$

We claim that $p_1=1, p_2=2$, and for $n\geq 3$, we have $p_n = 3\cdot 2^{n-2}$. The $n=1,2$ cases are clear by inspection, and we prove the others with induction. $\textbf{Claim: }$ For all $n\geq 3$, we have $p_n = 3\cdot 2^{n-2}$ $\textbf{Proof: }$ Base case: $n=3$ satisfies $p_3=6$. We now induct to deal with $n\geq 4$. If $n$ is even, then since \[n-1 \mid 2\cdot \left(\frac{n(n+1)}{2}- a_n\right )\]we have that $a_n\equiv 1 \pmod{n-1}$ which means that $a_n=1,n$. Either choice gives $p_{n-1}$ solutions (we can shift all values up by 1 and maintain all conditions). Thus, $p_n = 2\cdot p_{n-1}$ here. If $n$ is odd, then \[\frac{n-1}{2} \mid \left(\frac{n(n+1)}{2}- a_n\right)\]Thus, $a_n \equiv 1 \pmod{\frac{n-1}{2}}$. This gives $a_n = 1, \frac{n+1}{2}, n$. The value of $a_n = \frac{n+1}{2}$ fails because \[n-2 \mid 2\left(\frac{n(n+1)}{2}-a_{n-1}-a_n \right)\]Thus, $a_{n-1} \equiv \frac{n+1}{2} \pmod{n-2}$ since $n-2$ is odd. This is a contradiction because $a_{n-1}\neq \frac{n+1}{2}$ and $\frac{n+1}{2}-(n-2) <1\leq a_n \leq n < \frac{n+1}{2}+(n-2)$ for $n\geq 4$. Thus, the only two choices are once again $a_n=1,n$, so we have $p_n = 2p_{n-1}$ and our induction is complete. $\blacksquare$.

Let $f(n)$ denote the answer. I claim that $f(1)=1,f(2)=2$, and $f(n)=3\cdot 2^{n-2}$ for $n \geq 3$. We can manually inspect $n=1,2,3$. Now, we induct to prove the claim for $n \geq 3$ with the base case being done, so henceforth suppose $n \geq 4$. Note that we must have $n-1 \mid n(n+1)-2a_n \implies n-1 \mid 2a_n-2$, hence $a_n \in \{1,\tfrac{n+1}{2},n\}$. If $a_n=\tfrac{n+1}{2}$, then we must have $n$ odd. Further, we also require $n-2 \mid n(n+1)-2a_n-2a_{n-1}=n^2-1-2a_{n-1} \implies n-2 \mid 2a_{n-1}-3$. Since $n-2$ is odd, this implies that $$a_{n-1} \equiv \frac{3}{2} \equiv \frac{n+1}{2} \pmod{n-2},$$but for $n \geq 4$ odd we have $\tfrac{n+1}{2}-(n-2)<1$ and $\tfrac{n+1}{2}+(n-2)>n$, so we should have $a_{n-1}=\tfrac{n+1}{2}=a_n$: contradiction. Now, note that we can biject any valid permutation ending in $1$ to another valid permutation ending in $n$ by transforming $a_n \to (n+1)-a_n$. Thus $f(n)$ is twice the number of valid permutations of length $n$ with $a_n=n$, which is clearly just $f(n-1)$, completing the induction. $\blacksquare$

Let $f(n)$ be the answer. We have $f(1)=1,f(2)=2,f(3)=6$ Note that $n-1\mid 2(a_1+a_2+\dots+a_{n-1})$ implies $n-1\mid n(n+1)-a_n$ which implies $a_n=1,\tfrac{n+1}{2},$ or $n.$ $~$ If $a_n=\tfrac{n+1}{2}$ we see that $n-2\mid 2(a_1+a_2+\dots+a_{n-2})$ implies $n-2\mid n(n+1)-n-1-a_{n-2}$ and the only solution is $a_{n-2}=\tfrac{n+1}{2}$ contradiction. $~$ If $a_n=n$ then we have that there are $f(n-1)$ ways to order the rest. If $a_n=1$ then note that if $(a_1,a_2,\dots,a_{n-1},n)$ is valid then so is $(n+1-a_1,n+1-a_2,\dots,n+1-a_{n-1},1)$ so the answer is $f(1)=1,f(2)=2,f(n)=3\cdot 2^{n-2},n\ge 3$

Let $X_n$ be the answer. We claim that the answer is $X_1=1$, $X_2=2$, and $X_{i+2}=3 \cdot 2^i$ for $i \ge 1$. We have $X_1=1$, $X_2=2$, and $X_3=6$. We solve the problem for $n \ge 4$. Note that $n|2(a_1+a_2+ \cdots +a_n) = n(n+1)$, so we don't need the condition for $k=n$. We also have that $n-1|2(a_1+ \cdots + a_{n-1}) = n(n+1) - 2a_n$. This means $a_n=1$, $a_n=\frac{n+1}{2}$, or $a_n=n$. If $a_n=\frac{n+1}{2}$, then $n-2|n(n+1) - 2a_{n}-2a_{n-1} = (n-1)(n+1) - 2a_{n-1} \implies n-1| 2a_{n-1} -3$. This means $n-1=2a_{n-1}-3 \implies a_{n-1} = \frac{n+1}{2}$, a contradiction. If $a_n=n$, we have there is $f(n-1)$ ways to order $\{a_1,a_2 , \cdots , a_{n-1}\}$. If $a_n=1$, note we can choose $a_i=b_i+1$ where $(b_1,b_2, \cdots , b_{n-1})$ is a working solution. This means $f(n)=2f(n-1)$ for $n \ge 4$ as desired.

Let the answer be $b_n$. Manually check that $b_1=1$, $b_2=2$, and $b_3=6$. Claim. $b_{n+1}=2b_n$ for all positive integers $n\ge 3$. Proof. Casework on $a_{n+1}$. It has to be $1$, $n+1$, or $\frac{n+2}{2}$(if this is an integer) so that $k=n$ works. If it is $n+1$, this immediately reduces to the $b_n$ case, and if it is $1$, this is the $b_n$ case except everything is shifted up by one. So it suffices to prove that $a_{n+1}\ne\frac{n+2}{2}$. Now consider when $k=n-1$. Since $2\mid n+2$, $n-1$ is odd, so we must have \[a_n+\frac{n+2}{2}=a_n+a_{n+1}\equiv 1+2+\dots+(n+1)=\frac{(n+1)(n+2)}{2}\equiv 3\pmod{n-1}\rightarrow a_n\equiv\frac{n+2}{2}\pmod{n-1}\rightarrow a_n=\frac{n+2}{2},\]contradiction. So the answer is $b_1=1$, $b_2=2$, and $b_n=3\cdot 2^{n-2}$ for all positive integers $n\ge 3$.

oops 2am solve Let $f(n)$ denote the answer for $n$. We can manually compute $f(1)=1,f(2)=2,f(3)=6,f(4)=12.$ Claim: For $n\geq4$, $f(n+1)=2f(n)$. Consider $a_{n+1}$. We must have $$n|(n+1)(n+2)-2a_{n+1}$$$$n|2-2a_{n+1},$$so we have either $$a_{n+1}=1,a_{n+1}=1+\frac{n}{2},a_{n+1}=n+1.$$ Case 1: $a_{n+1}=1$. Then, note that increasing each element of a permutation by 1 does not do anything. Thus, this permutation works if and only if the permutation formed by decrementing each of the first $n$ elements by 1 works, so there are $f(n)$ ways here. Case 2: $a_{n+1}=n+1$. Then, simply this permutation works if and only if the permutation formed by the first $n$ elements works, so there are also $f(n)$ ways here. Case 3: $a_{n+1}=1+n/2$. Since we already have $2f(n)$ cases, we want to show that there are 0 cases here. Clearly, there are 0 cases when $n$ is odd, so assume $n$ is even and let $n=2m$. Then, consider mod $2m-1$. By the condition, the sum of the first $2m-1$ terms is a multiple of $2m-1$ since it is odd. Then, we know that the final term is $m+1$. However, the sum of all terms is $$(2m+1)(m+1)=2m^2+3m+1\equiv 3\pmod{2k-1}.$$Hence, $$a_{2m}=3-(m+1)\equiv m+1\pmod{2m-1}.$$For $m\geq2$, the only number between 1 and $2m+1$ that is equivalent to $m+1\pmod{2m-1}$ is $m+1$. However, $m+1$ is already taken by $a_{2m+1}$, contradiction, so there are 0 cases here. Hence, $f(n+1)=2f(n)$ for $n\geq4$, so our answer is $f(1)=1,f(2)=2,$ and for $n\geq3$, $$f(n)=3\cdot2^{n-2}.$$

\[A(n)=\begin{cases} 1\quad\text{ for } n=1\\ 2\quad \text{ for } n=2\\ 3\cdot2^{n-2}\quad \text{ for } n\ge 3\end{cases}\] For the small $n$-s we can check by hand. Let $f(n)=\mid A_n\mid$ Now we will prove that $f(n)=2\cdot f(n-1)$. $\blacksquare$ $n$ is even. Let we see that $n-1$ divides $2(a_1+a_2\ldots+a_{n-1})=n(n+1)-2a_n$ we have $a_n\equiv 1\pmod{n-1}$. So $a_n$ is either $n$, for which we have $f(n-1)$ permutations, or $1$, for which we too have $f(n)$ permutations (from each one we add $1$ to the numbers). So $f(n)=2\cdot f(n-1)$ $\blacksquare$ If $n$ is odd we get that $a_n\equiv 1\pmod{\frac{n-1}2}$. So $a_n\in\{1;\frac{n+1}{2};n\}$. We will prove that $a=\frac{n+1}{2}$ is impossible. \[n-2\mid2(a_1+\ldots+a_{n-2}=n(n+1_-2(a_n+a_{n-1})\] So we get that $a_{n-1}\equiv\frac{n+1}{2}\pmod{n-2}$, so for $n\ge 5$ we get that $a_{n-1}=\frac{n+1}{2}$, but $a_n=a_{n-1}$ is impossible. So really $f(n)=2\cdot f(n-1)$

Define $f$ as \begin{align*} f(x)= \begin{cases} 1 & \text{if } x=1\\ 2 & \text{if } x=2\\ 3\cdot2^{n-2} & \text{if } x\geq 3 \\ \end{cases} \end{align*} We claim that the number of permutations for $a_{1}, \cdots, a_{n}$ of $\{1, \cdots, n\}$ that satisfy the given condition is $f(n)$. We use induction with base case $3$. Clearly all permutations of $\{1, 2, 3\}$ work with the given condition which gives us $3! = 3\cdot 2^{3-2}$. Now we assume that there are $3\cdot2^{k-3}$ permutations that work for $n=k-1$. Note that \[k-1 \mid 2\biggl(\frac{(k)(k+1)}{2}-a_{k}\biggr) \implies 2a_{k}\equiv 2 \pmod{k-1}\]This implies that $a_{k}\in\{1, \frac{k+1}{2}, k-1\}$. We claim that it is impossible for $a_{k} = \frac{k+1}{2}$. For the sake of contradiction, assume that $a_{k} = \frac{k+1}{2}$. \[k-2 \mid 2\biggl(\frac{(k)(k+1)}{2}-\frac{k+1}{2}-a_{k-1}\biggr) \implies 2a_{k-1} \equiv 3 \pmod{k-2}\]This is only possible if $a_{k-1} = \frac{k+1}{2}$, contradiction. When $a_{k} = k$, we just have $3\cdot 2^{k-3}$ choices for the rest with no restrictions. When $a_{k} = 1$, we also have $3\cdot 2^{k-3}$ because we can simply subtract $1$ from every single number which forms a bijection. Thus, the total is $\boxed{3\cdot2^{k-2}}$

We will show that the answer is $1$ for $n=1,$ $2$ for $n=2$ and $3 \cdot 2^{n-2}$ for $n \ge 3.$ First, notice that the problem is trivial for $n=1,2,3.$ Now we use induction. Suppose $n \ge 3$ is odd and we have $A_n=3 \cdot 2^{n-2}.$ Consider a valid permutation of $\{1,2, \dots, n+1\}$ that satisfies $n \mid 2(a_1+ \dots + a_n).$ Then we must have $a_{n+1} \equiv 1 \pmod{n}$ so $a_{n+1}=1$ or $n+1.$ If we have $a_{n+1}=n+1$ then we can have $a_1, \dots, a_n$ be any valid permutation of $\{1,2,\dots,n\}$ in $3 \cdot 2^{n-2}$ ways. If we have $a_{n+1}=1$ then notice that $a_1-1,a_2-1, \dots, a_n-1$ is a permutation of $1,2,\dots,n,$ and $a_1+\dots+a_k \equiv (a_1-1)+\dots+(a_k-1) \pmod{k}$ so $a_1,\dots,a_n$ is part of a valid permutation if and only if $a_1-1,\dots,a_k-1$ is a valid permutation, which can happen in $3 \cdot 2^{n-2}$ ways, so in this case we have that $A_{n+1}=3 \cdot 2^{(n+1)-2}.$ Now, suppose $n \ge 3$ is even and we have $A_n=3 \cdot 2^{n-2}.$ Consider a valid permutation as before. Then we must have $a_{n+1} \equiv 1 \pmod{\tfrac{n}{2}}$ so $a_{n+1}=1, n+1$ or $\tfrac{n}{2}+1.$ If $a_{n+1}=1$ or $n+1$ these give us the same $3 \cdot 2^{(n+1)-2}$ elements as before. Now, suppose $a_{n+1}=\tfrac{n}{2}+1.$ We have $a_1+\dots+a_n=\frac{n^2+2n}{2} \equiv \tfrac{n}{2}+1 \pmod{n-1},$ so in order to have a valid sequence we must have $a_n \equiv \tfrac{n}{2}+1 \pmod{n-1}.$ However, we have $a_{n+1}=\tfrac{n}{2}+1,$ so we must have $a_n \ge \tfrac{3n}{2},$ but for $n \ge 3$ we have $\tfrac{3n}{2}>n+1,$ so there are no valid permutations in this case, so we get the same $3 \cdot 2^{(n+1)-2}$ elements, completing the induction, so we are done.

Let $f$ be the function giving the number of such permutations for an integer $n$. We claim that $f(1) = 1$, $f(2) = 2$, and $f(n) = 3 \cdot 2^{n-2}$ for $n \geq 3$. We can obviously see the first two cases. We claim that $a_n = 1, n$. Notice that the sum is $\binom{n+1}{2}$. And for $k = n-1$ we must have $2\binom{n+1}{2} - 2x \equiv 0 \pmod{n-1}$ for some integer $x \in \{1, \dots , n\}$. This means that $x = 1, n$ for $n \geq 3$. Now notice that if we have $a_n = 1$ then we have just increased all of the terms in $f(n-1)$. Thus, we have $f(n-1)$ values for this case. Now notive that when we have $a_n =n$ then we have thfe exact same numbers as before so this also has $f(n-1)$ cases. Thus we get the recurrence relation $f(n) = 2f(n-1)$. $\blacksquare$

Greatest MEP of international editors collabing with an Indian editor, on a bollywood song! Xenoz really understood the assignment :smirk: . Chammak Challo MEP with Retuurn, Xenoz, Oxime and more. Also, is it just me, or does this problem feel totally NT and 0 combi? Now let's get to the solution. For the base cases, we can check $n=1$, $2$, $3$ by hand. This gives $|A_1| = 1$, $|A_2| = 2$ and $|A_3| = 6$. Now we proceed by induction. For the base case, assume that we know the value of $|A_n|$ for some $n\ge 3$, and so, we want to find the value of $|A_{n+1}|$. We divide this into cases. $\textbf{CASE 1: }$ $n$ is odd. Solution: In this case, if the last digit of the tuple is $n+1$ itself, then we simply get $|A_n|$ cases by using induction. This is because the sum of all the numbers is clearly divisible by $n+1$, so we have to deal with only the first $n$ numbers. Now if the last digit is not $n+1$, then we represent it by some $f$. Then note that by using $k=n$, we get, \[ n\mid 2\left(\dfrac{(n+1)(n+2)}{2} - f\right) \equiv 2-2k = 2(1-f). \]Now since $n$ is odd, we can simply ignore the $2$ from which we get $f\equiv 1\pmod{n}$. But then this must mean that $f=1$. So the first $n$ elements of the tuple are just a rearrangement of $(2,3,\ldots , n+1)$. Now note that even if we decrease all the $(a_1,a_2,\ldots , a_n)$ by $1$, the problem condition stays equivalent due to divisibility. Thus we can decrease all the first $n$ elements by $1$ which gives us a rearrangement of $(1,2,\ldots ,n)$. The number of such tuples is just $|A_n|$ again. So in total, we get $|A_{n+1}| = 2|A_n|$ when $n$ is odd. $\textbf{CASE 2: }$ $n$ is even. Solution: In this case, if the final digit is $n+1$, we get $|A_n|$ tuples in a similar fashion as seen previously. Otherwise similarly, we again get $n \mid 2(1-f)$. But this time, we cannot ignore the $2$ anymore. So in this case, we get $k\equiv 1\pmod{\frac{n}{2}}$. Now if the final element is $1$, we again get that there are $|A_n|$ such tuples. The only other case that remains is when the final element is $\dfrac{n}{2} + 1 = \dfrac{n+2}{2}$. Let the second last element be $g$. Now we set $k=n-1$ to get, \[ n-1\mid 2\left(\dfrac{(n+1)(n+2)}{2} - \left(\dfrac{n+2}{2}\right) + g\right) \equiv 2\cdot 3 - 3 - 2g = 3 - 2g. \]This gives us that $2g\equiv 3 \pmod{n-1}$. Thus in this case we have $2g = (n-1)x + 3$ for some integer $x$. Due to parity, this forces $x$ to be odd. Now if $x\ge 3$, then $g = \dfrac{(n-1)x+3}{2}\ge \dfrac{(n-1)\cdot 3 + 3}{2}=\dfrac{3n}{2}$. But $\dfrac{3n}{2}>n+1$ for all $n>2$ which gives a contradiction. Thus we now get $x=1$ which gives $g=\dfrac{n+2}{2}$. But this gives a further contradiction as our final element was $\dfrac{n+2}{2}$ itself. Thus there are no possible tuples when the final element is $\dfrac{n+2}{2}$. So in total, this case also gives us $|A_{n+1}|=2|A_n|$ when $n$ is even. Combining these two cases, we get that $|A{n+1}|=2|A_n|$ for all $n\ge 3$. Thus our final answer looks like $|A_1| = 1$, $|A_2| = 2$ and $|A_n| = 3\cdot 2^{n-2}$ for all $n \ge 3$.

The answer is $3 \cdot 2^{n-2}.$ Let $f(n)$ denote the number of sequences $(a_1, \dots, a_n).$ Consider $a_n$. We have $$n(n+1) \equiv 2 \equiv 2a_{n} \pmod{n-1},$$so the only possible values of $a_n$ are $1, n,$ and $\frac{n+1}{2}.$ If $a_n = \frac{n+1}{2},$ we repeat to get $a_{n-1} = \frac{n+1}{2},$ contradiction. Thus, the only possible values of $a_n$ are $1$ and $2.$ In both cases, the number of ways to choose $(a_1, \dots, a_{n-1})$ is $f(n-1)$, so for $n \geq 4,$ $$f(n) = 2f(n-1).$$When $n = 3$, $f(3) = 3$. Therefore, $f(n) = 3 \cdot 2^{n-2}.$

We claim the answers are $1$, $2$ and $6$ for $n=1$, $2$ and $3$ respectively, and $3\cdot 2^{n-2}$ for every $n\ge 4$. Let $f(n)$ be the number of such permutations. It can easily be seen that $f$ indeed takes $1$, $2$ and $6$ as its three first values, and it suffices to show that $f(n)=2f(n-1)$ for $n\ge 4$ after which remains a simple induction. Let $(a_1,a_2,\ldots,a_n)$ be such a permutation. The idea is to look at the sequence backwards, i.e. we look at $a_n$ : \[n-1\mid 2\times \sum_{i=1}^{n-1}a_i=n(n+1)-2a_n\]\[\implies n-1\mid 2(a_n-1)\]In particular, since $2(a_n-1)\le 2(n-1)$, we must have $a_n\in \{1,\frac{n+1}{2},n\}$. $\triangleright$ If $a_n=n$, then there are $f(n-1)$ valid permutations for the remaining $n-1$ $a_i$'s. $\triangleright$ If $a_n=1$, then $(a_1,a_2,\ldots,a_{n-1})$ must form a valid permutation of $(2,3,\ldots,n)$. Shifting every $a_i$ by $1$ clearly gives a one to one correspondence with the valid permutations of $(1,2,\ldots,n-1)$. Again, there are $f(n-1)$ of them. $\triangleright$ Finally, if $a_n=\frac{n+1}{2}$ (note that this is only possible if $n$ is odd), then we look one step further : \[n-2\mid 2\times \sum_{i=1}^{n-2}a_i=2\times \sum_{i=1}^{n-1}a_i-2a_{n-1}=(n-1)(n+1)-2a_{n-1}\]\[\implies n-2\mid 2a_{n-1}-3\]Note that $2a_{n-1}-3$ is non zero and $2a_{n-1}-3\le 2n-3<3(n-2)$. Furthermore, since $n-2\ge 2$, we can't have $a_{n-1}=1$ (only case in which $2a_{n-1}-3$ is negative). Finally, since $2a_{n-1}-3$ is odd, we can't have $2a_{n-1}-3=2(n-2)$. Therefore, we must have $2a_{n-1}-3=n-2$, i.e. $a_{n-1}=\frac{n+1}{2}=a_n$, which obviously cannot hold. Summing up the three cases yields $f(n)=2f(n-1)$, as desired. $\square$

Let $s_n=|A_n|$ for convenience. Also, to remove the factor of $2$, just consider permutations $(b_1,\dots,b_n)$ of the set $\{2,\dots,2n\}$. Consider $n\ge 4$. Work backwards. The sum of all elements is $n(n+1)$. Hence $b_n\equiv 2\pmod {n-1}$. Thus $b_n\in \{2,n+1,2n\}$. If $b_n=2$ then we reduce to the set $\{4,\dots,2n\}$. Decrease all values by $2$, which does not change the answer. This provides $s_{n-1}$ to the count. If $b_n=2n$ then we reduce to the set $\{2,\dots,2n-2\}$. This provides $s_{n-1}$ to the count. If $b_n=n+1$ then $n$ is odd. This is the final case. Now we resolve this last case. The sum is now $n^2-1$. Hence $b_{n-1}\equiv 3\pmod {n-2}$. Then $b_{n-1}\in \{3,n+1,2n-1\}$. Note $3n-3>2n$. But now clearly $b_{n-1}=n+1$, a contradiction. This proves $s_n=2s_{n-1}$ for $n\ge 4$. Now calculation yields $s_1=1$, $s_2=2$, and $s_3=6$. The answer for $s_n$ with $n\ge 4$ is then $6\cdot 2^{n-3}$. $\blacksquare$

Answer is $6 \cdot 2^{n-3}$ for all $n \geq 3$, and for $n = 1$, $2$ we have $1$, $2$ as our answers for each respectively. We first note that $n(n+1) - 2a_n$ must be divisible by $n - 1$, so $a_n = 1$, $n$, or(if $n$ is odd) $\frac{n+1}{2}$. However, if $a_n = \frac{n+1}{2}$ then $n - 2 \mid n^2 - 1 - 2a_{n-1} \implies 2a_{n-1} = 3$, $n + 1$, $2n - 1$, absurd. So then $a_n = 1$ or $n$. In both cases we can simply induct from $n$ to $n-1$, so $A_n = 2A_{n-1}$ if $n \geq 4$. Since $A_3 = 6$, we have our answer to be $6 \cdot 2^{n-3}$.

Let $f(n)$ denote the number of permutations for the set ${1,2,\dots,n}$. Now we start with two cases: i) $a_n=n$: then we have that the number of permutations is equal to $f(n-1)$. ii) $a_n \neq n$: then looking at $k=n-1$ we see that, the only $a_n$ that works is $1$ and $\frac{n+1}{2}$ (if $n$ is odd). If $a_n=1$ then we get $f(n-1)$ permutations. Now if we have $a_n=\frac{n+1}{2}$, then we can see that it’s not possible. Hence the $f(n)=2f(n-1)$. Which implies $f(n)= 3\cdot 2^{n-2}$ and hence we are done.

Let $f(n)$ denote our desired permutation count. We claim our answer is \[\boxed{f(1) = 1, f(2) = 2, f(3) = 6, f(n) = 6 \cdot 2^{n-3}}.\] The key claim is that $a_n$ must equal 1 or $n$ for all $n > 3$, which would give the desired recurrence $f(n) = 2f(n-1)$: If $n$ is even, we must have \[a_n \equiv \frac{n(n+1)}{2} \equiv 1 \pmod{n-1} \implies a_n = 1, n.\] If $n$ is odd, we must have \[a_n \equiv \frac{n(n+1)}{2} \equiv 1 \pmod{\tfrac{n-1}{2}} \implies a_n = 1, \tfrac{n-1}{2}, n.\] However, if $a_n = \tfrac{n-1}{2}$, we find that \[a_{n-1} + a_n \equiv \frac{n(n+1)}{2} \equiv 3 \pmod{n-2} \implies a_{n-1} \equiv \tfrac{n-1}{2} \pmod{n-2}.\] This results in $a_{n-1} = a_n$ when $n>3$, contradiction. Our permutation count in the case of $a_n = n$ is clearly just $f(n-1)$. But notice that we have a bijection between the desired permutations of $\{2, \ldots, n\}$ and $\{1, \ldots, n-1\}$, so the case of $a_n = 1$ also has $f(n-1)$ solution, from summing gives our claimed recurrence. $\blacksquare$

The answer is $3\times 2^{n-2}.$ Claim : $a_n=1$ or $a_n=n$ for all positive integers $n.$ Proof : For $k=n-1:$ $$n-1\mid 2(a_1+a_2+\cdots+a_{n-1})=2(1+2+\cdots n) - 2a_{n} \equiv 2-2a_n \pmod{n-1}. $$which means that $a_n\equiv 1 \pmod {n-1}\iff a_n\in\{1,n\}$ or $a_n=\frac{n-1}{2}+1.$ [0.2cm] Suppose that $a_n=\frac{n-1}{2}+1$ which happens only if $n$ is odd, then $k=n-2$ gives : \[n-2\mid 2(a_1+\cdots a_{n-2}) = 2(1+2+\cdots +n) -2(a_n+a_{n-1}) \equiv 6-3-2a_n \pmod {n-2}\]Which implies : \[2a_{n-1}\equiv 3 \equiv 2a_{n}\pmod{n-2} \]However, $n-2$ is odd so $a_{n-1}\equiv a_n \implies a_n=a_{n-1}$ which is a contradiction. Let $F(n)$ be the answer for $n$ and call a sequence good if it satisfies the problem. If $a_n=n,$ then $(a_1,\cdots a_{n-1})$ is good and there are $F(n-1)$ such ones. Otherwise, $a_n=1$ and $(a_1-1,a_2-1,\cdots a_{n-1}-1)$ is good. Again, there are $F(n-1)$ good sequences for $n-1.$ Indeed, $k\mid 2(a_1+\cdots a_k) \iff k\mid 2(a_1+\cdots a_k) -2k = 2(a_1-1+\cdots a_k-1).$ The formula of $F(n)$ is then obvious by induction.