How Cheenta works to ensure student success?
Explore the Back-Story
Problems and Solutions from CMI Entrance 2022.  Learn More 

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.

Math Olympiad Program at Cheenta

Subscribe to Cheenta at Youtube


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.

Math Olympiad Program at Cheenta

Subscribe to Cheenta at Youtube


Leave a Reply

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

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
magic-wand