Cheenta
Academy for Gifted Students
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.

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

Your email address will not be published. Required fields are marked *

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
Menu
Trial
Whatsapp
Math Olympiad Program
magic-wandrockethighlight