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 \]
Problem
Source: INMO 2022 Problem 2
Tags: INMO, INMO 2022, combinatorics, algebra
06.03.2022 11:27
It's easy to get $n \equiv 0,2 \pmod 3$ and then you die for the rest of the contest.
06.03.2022 12:12
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.
06.03.2022 12:20
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?
06.03.2022 12:24
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
06.03.2022 13:26
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.
06.03.2022 13:31
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.
06.03.2022 13:38
Rg230403 wrote: This was easily the best problem on the test according to me.
06.03.2022 14:54
Any ideas on who was the author of the problem? @below say no more
06.03.2022 14:54
Rg230403 wrote: This was easily the best problem on the test according to me. It was proposed by Tejaswi after all
06.03.2022 15:19
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.
06.03.2022 16:41
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$
06.03.2022 17:24
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.
07.03.2022 05:38
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.
01.05.2022 03:40
23.05.2022 09:50
21.09.2022 20:20
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.
18.01.2024 18:30
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\}$