Try this beautiful Combinatorics problem with a little Number Theory from IOQM- 2022.
Find all natural numbers $n$ for which there exists a permutation $\sigma$ of $1,2, \ldots, 1$ such that
$\sum_{i=1}^{n} \sigma(i)(-2)^{i-1}=0$
Note: A permutation of $1,2, \ldots, n$ is a bijective function from ${1,2, \ldots, n}$ to itself.
Modular Arithmetic
Permutation
Induction
Elementary Number Theory (By David Burton), Excursion in Mathematics
IOQM 2022 Part-B, Problem 2
All natural numbers which are not of the form $3k + 1$
Since $-2 \equiv 1 (\bmod 3)$
$\sum_{i=1}^{n} \sigma(\underset{\sim}{i})(-2)^{i-1} \equiv \sum_{i=1}^{n} \sigma(\underset{\sim}{i})$
=$\frac{n(n+1)}{2}(\bmod 3)$
Now since,
$$
\sum_{i=1}^{n} \sigma(i)(-2)^{i-1}=0
$$
$$\rightarrow \frac{n(n+1)}{2} \equiv 0
(\bmod 3)$$
$\rightarrow n \equiv 0$ or $2 (\bmod 3)$
If $n=2$ then the permutation given by $\sigma(1)=2, \sigma(2)=1$ satisfies the given condition. Similarly, if $n=3$ then the permutation $\sigma(1)=2, \sigma(2)=3, \sigma(3)=1$ satisfies the given condition.
Now, try to use induction and extend the argument for all other valid numbers
Try to define the permutation in a cyclic manner.
Math Olympiad Program at Cheenta
Try this beautiful Combinatorics problem with a little Number Theory from IOQM- 2022.
Find all natural numbers $n$ for which there exists a permutation $\sigma$ of $1,2, \ldots, 1$ such that
$\sum_{i=1}^{n} \sigma(i)(-2)^{i-1}=0$
Note: A permutation of $1,2, \ldots, n$ is a bijective function from ${1,2, \ldots, n}$ to itself.
Modular Arithmetic
Permutation
Induction
Elementary Number Theory (By David Burton), Excursion in Mathematics
IOQM 2022 Part-B, Problem 2
All natural numbers which are not of the form $3k + 1$
Since $-2 \equiv 1 (\bmod 3)$
$\sum_{i=1}^{n} \sigma(\underset{\sim}{i})(-2)^{i-1} \equiv \sum_{i=1}^{n} \sigma(\underset{\sim}{i})$
=$\frac{n(n+1)}{2}(\bmod 3)$
Now since,
$$
\sum_{i=1}^{n} \sigma(i)(-2)^{i-1}=0
$$
$$\rightarrow \frac{n(n+1)}{2} \equiv 0
(\bmod 3)$$
$\rightarrow n \equiv 0$ or $2 (\bmod 3)$
If $n=2$ then the permutation given by $\sigma(1)=2, \sigma(2)=1$ satisfies the given condition. Similarly, if $n=3$ then the permutation $\sigma(1)=2, \sigma(2)=3, \sigma(3)=1$ satisfies the given condition.
Now, try to use induction and extend the argument for all other valid numbers
Try to define the permutation in a cyclic manner.
Math Olympiad Program at Cheenta
