How Cheenta works to ensure student success?
Explore the Back-Story

IOQM 2022 Problem 2 | Part: B | Combinatorics Problem

Try this beautiful Combinatorics problem with a little Number Theory from IOQM- 2022.

IOQM 2022 B, Problem 2:

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.

Key Concepts

Modular Arithmetic

Permutation

Induction

Suggested Book | Source | Answer

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$

Try with Hints

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.

Try this beautiful Combinatorics problem with a little Number Theory from IOQM- 2022.

IOQM 2022 B, Problem 2:

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.

Key Concepts

Modular Arithmetic

Permutation

Induction

Suggested Book | Source | Answer

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$

Try with Hints

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.