It's easy to get $n \equiv 0,2 \pmod 3$ and then you die for the rest of the contest.

NVT's problem!! This was easily the best problem on the test according to me. Soln. Looking mod 3, we get that $3|n^2+n$ and thus, $n\not\equiv 1 \pmod{3}$. This is kinda a thing that's easy to miss and then struggle for a long while. Now, we show a construction for $m+3$ assuming one for $m$. Let $\sigma$ be the permuation for $m$. Define $\tau(1)=2, \tau(2)=3, \tau(i)=\sigma(i-2)+3$ for $i\in \{3,\cdots m+2\}$ and $\tau(m+3)=1$. We can now verify that this indeed works. This also works out to something quite clean with the first few terms being the 2, 3 mod 3 terms alternating and a bunch of 1 mod 3 terms at the end. Something like 2,3,5,6,8,9,...3k+2, 3k+3, 3k+1, 3k-2, ..., 1 I think which is possible to observe with some attempts on small values.

hellomath010118 wrote: Find all natural numbers $n$ for which there is a permutation $\sigma$ of $\{1,2,\ldots, n\}$ that satisfies: \[ \sum_{i=1}^n \sigma(i)(-2)^{i-1}=0 \] it's 2,3,5,6.... (first group all 2 mod 3 and 0 mod 3) and then 7,4, 1 (all 1 mod 3 in descending) Rg230403 wrote: NVT's problem!!! This was easily the best problem on the test according to me. Soln. Looking mod 3, we get that $3|n^2+n$ and thus, $n\not\equiv 1 \pmod{3}$. This is kinda a thing that's easy to miss and then struggle for a long while. Now, we show a construction for $m+3$ assuming one for $m$. Let $\sigma$ be the permuation for $m$. Define $\tau(1)=2, \tau(2)=3, \tau(i)=\sigma(i-2)+3$ for $i\in \{3,\cdots m+2\}$ and $\tau(m+3)=1$. We can now verify that this indeed works. This also works out to something quite clean with the first few terms being the 2, 3 mod 3 terms alternating and a bunch of 1 mod 3 terms at the end. Something like 2,3,5,6,8,9,...3k+2, 3k+3, 3k+1, 3k-2, ..., 1 I think which is possible to observe with some attempts on small values. how much for just construct?

eek didnt do it cuz i forgot what a bijective function is Rg230403 wrote: NVT's problem!!! This was easily the best problem on the test according to me. Soln. Looking mod 3, we get that $3|n^2+n$ and thus, $n\not\equiv 1 \pmod{3}$. This is kinda a thing that's easy to miss and then struggle for a long while. Now, we show a construction for $m+3$ assuming one for $m$. Let $\sigma$ be the permuation for $m$. Define $\tau(1)=2, \tau(2)=3, \tau(i)=\sigma(i-2)+3$ for $i\in \{3,\cdots m+2\}$ and $\tau(m+3)=1$. We can now verify that this indeed works. This also works out to something quite clean with the first few terms being the 2, 3 mod 3 terms alternating and a bunch of 1 mod 3 terms at the end. Something like 2,3,5,6,8,9,...3k+2, 3k+3, 3k+1, 3k-2, ..., 1 I think which is possible to observe with some attempts on small values.

orz

The way I motivated the same construction is that I am dealing with mod3, I am sleepy, so it has to be n->n+3 and insertion.

in terms of the ideas involved. Solved with $\textbf{Aryan-23}$. $\textbf{Lemma 1:}$ $n \equiv 1 \pmod{3}$ do not work. $\textbf{Proof}$ Assume for the sake of contradiction that some $n \equiv 1 \pmod{3}$ works. Look at the equation $\pmod{3}$, then $$ 0 = \sum_{i=1}^{n} \sigma(i) \cdot (-2)^{i-1} = \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \equiv 1 \pmod{3}$$which is a contradiction. $\blacksquare$ We present the same construction as in #4 with some motivation afterwards. $\textbf{Lemma 2}$ $n \equiv 0,2 \pmod{3}$ work. $\textbf{Proof}$ We induct with base case permutations $(2,1), (2,3,1)$ for $n = 2,3$, respectively. Assume that $(\sigma(1), \cdots, \sigma(n))$ work for some $n \in \mathbb{N}$, $n \equiv 0,2 \pmod{3}$, then take $\sigma_1(1) = 2, \sigma_1(2) = 3, \sigma(m+3) = 1$ and $\sigma_1(i) = \sigma(i-2)+3$ for $i \in \{3, \cdots, n+2\}$ which can be verified to work for $n+3$ as $(\sigma_1(1), \cdots, \sigma_1(n+3))$. $\blacksquare$ Summing up our conclusions from $\textbf{Lemma 1}$ and $\textbf{Lemma 2}$, we can conclude that only $n \equiv 0,2 \pmod{3}$ work.

Rg230403 wrote: This was easily the best problem on the test according to me.

Any ideas on who was the author of the problem? @below say no more

Rg230403 wrote: This was easily the best problem on the test according to me. It was proposed by Tejaswi after all

anantmudgal09 wrote: Rg230403 wrote: This was easily the best problem on the test according to me. It was proposed by Tejaswi after all Even though I failed I am pretty sure this is the best problem of the test.The statement is so beautiful itself.

Clearly by modulo $3$, we need to have $\sum_{i=1}^n i \equiv 0 \pmod{3}$, which means $n \equiv 0,2 \pmod{3}$ For the construction, we create a sequence $a_1, \cdots a_{n-1}$, and define \[ \sigma(1) = 2a_1, \sigma(2) = a_1+2a_2, \sigma(3) = a_2+2a_3, \cdots, \sigma(n-1) = a_{n-2} + 2a_{n-1}, \sigma(n) = a_n \]For $n =3k$, the desired sequence is generated by $1,1,2,2,3,3, ..., k, k, k-1, k-2, ... 1$ For $n =3k-1$, the desired sequence is generated by $1,1,2,3, ... ,k-1,k, k-1,k-1...,3,3,2,2,1,1$

i have shown that $n \equiv 0,2 \mod 3$. But i couldn't find the construction.How much can i get?please reply to this because i am very tensed.

Taking the sum $\mod 3$, we get that $\frac{n^2+n}{2}\equiv 0\mod 3$, so $n\equiv 0,2\mod 3$. Realize that we are essentially representing every number from $1$ to $n$ in the form $1\cdot a+2\cdot b$ such that the $a$ value of $\sigma (i+1)$ is the $b$ value of $\sigma (i)$. Once we do this, and look at small cases (I got for $6$ that the permutation $2,5,6,4,3,1$ works, it seems everyone else go the second value as $3$ somehow) that we have $|a-b|$ as small as possible. We can now inductively construct $n$. Base cases are the permutations $2,1$ and $2,3,1$. If $n=3k$, then our inductive hypothesis is that $3k-1,3k-2$ are consecutive terms in that order, $3k-1$ is represented as $1\cdot (k-1)+2\cdot k$, and $3k-2$ is represented as $1\cdot k +2\cdot (k-1)$. We want to show that $3k$ can fit inside the permutation, with $3k$ being represented as $1\cdot k+2\cdot k$, and $3k-1, 3k$ will be consecutive terms. This just works. If $n=3k+2$, then our inductive hypothesis is that $3k-1,3k$ are consecutive terms in that order, $3k-1$ is represented as $1\cdot (k-1)+2\cdot k$ and $3k$ is represented as $1\cdot k+2\cdot k$. We want to show that $3k+1,3k+2$ are represented as $1\cdot (k+1)+2\cdot k$ and $1\cdot k+2\cdot (k+1)$ respectively, and that they are consecutive in that order. Placing $3k+1,3k+2$ between $3k-1,3k$ works, as desired. For $n=14$ this gives the sequence $2,5,8,11,14,13,12,10,9,7,6,4,3,1$, which I think is the opposite/some sort of inverse of the sequence everyone else has, which starts by alternating $0,2\mod 3$ and then adds the $1\mod 3$ numbers at the end.

Special Thanks to Periwinkle for motivating me to verify the construction. Let $(\sigma(1),\sigma(2),....,\sigma(n))$ be $(a_1,a_2,....,a_n)$. $a_1+a_2+a_3+...a_n$=$\frac{n(n+1)}{2}$ -$(1)$ and $a_1+(-2)a_2+...a_n(-2)^n-1$=$0$------$(2)$, Substracting $(2)$ from $(1)$ gives $n=0,2(mod3)$.

From the construction we can observe that for $n=3k$ we have $(2,3,5,...3k-1,3k,3k-2,...1)$ and for $n=3k+2$ we have $(2,3,5,....3k+2,3k+1,...1)$. Also, note that right sides of $(3k-2)$ and $(3k+1)$ in $n=3k$ and $n=3k+2$ is decreasing by a differnce of $3$. So, if we verify for $n=3k$, somehow $n=3k+2$ has the same way but different procedure. Let the construction for $n=3k$ be like:-$(2,3,5,....3k-1,3k,3k-2,.....1)$ and let $2+3(-2)+....3k-3(-2)^{2k-2}=x$, and $3k-5(-2)^{2k+1} +3k-8(-2)^{2k+2} + ...+(-2)^{3k-1} =y$, Claim 1 $y=(-2)^{2k+1}.(k-1)$

From, $n=3k$, we have , $x+y+ (-2)^{2k+1}.(9k-9)=0$, $x=-y-(-2)^{2k+1} . (9k-9)$, Now, for $n=3k+3$ we have , $x-63(-2)^{2k-2}.(k-1) -8y$ which should be zero. Now, by replacing $x$ we get , $y+8(k-1)(-2)^{2k-2}$ , and from $a$, clearly it is zero. Hence verified , similarily, we can do for $n=3k+2$. So, The problem is completed. If anyone wants to solve with other construction dm me.

Nice problem...literally wasted nearly 2 hours....after seeing the pattern for 9 because I am so idiot that I don't know $28 \times 3 = 84$ and not $54$.Oops!! I wrote as the format $\{n,n-1,...,1\}$ instead of $\{1,2,...,n\}$