Challenge Problem #9 [Olinguito]

  • MHB
  • Thread starter Olinguito
  • Start date
  • Tags
    Challenge
In summary, we are determining the truth or falsity of two assertions regarding the group $S_n$ of permutations of the set $\{1,\ldots,n\}$. The first assertion states that for each permutation $\pi$, the sum of the differences between $\pi(i)$ and $i$ is equal to 0. The second assertion states that the sum of the absolute values of these differences, when replaced with their absolute values, is an even number. It is conjectured that the maximum value of this sum, denoted as $\sigma_\pi$, is equal to $\bigl\lfloor\tfrac{n^2}2\bigr\rfloor$, but this has not been proven.
  • #1
Olinguito
239
0
Let $S_n$ be the group of all permutations of the set $\{1,\ldots,n\}$. Determine whether the following assertions are true or false.

1. For each $\pi\in S_n$,
$$\sum_{i=1}^n\,(\pi(i)-i)\ =\ 0.$$

2. If
$$\sigma_\pi\ =\ \sum_{i=1}^n\,\left|\pi(i)-i\right|$$
for each $\pi\in S_n$, then $\sigma_\pi$ is an even number.

Bonus challenge: Find $\displaystyle\max_{\pi\in S_n}\,\sigma_\pi$.
 
Mathematics news on Phys.org
  • #2
I have solved the first part of the problem.

$$\sum_{i=1}^n\,(\pi(i)-i))\ =\ 0$$
follows from the fact that
$$\sum_{i=1}^n\,\pi(i)\ =\ \sum_{i=1}^n\,i$$
(the terms of the LHS sum are precisely those of the RHS sum in a different order).
 
  • #3
[sp]For the second part, notice that by the first part, the sum of the negative terms in $\sum(\pi(i) - i)$ is the negative of the sum of the positive terms. So when you replace the negative terms by their absolute values, the resulting sum is twice the sum of the positive terms. In other words, it must be an even number.
[/sp]
 
  • #4
Olinguito said:
Bonus challenge: Find $\displaystyle\max_{\pi\in S_n}\,\sigma_\pi$.
[sp]That part looks harder. After experimenting with small values of $n$, I believe that \(\displaystyle \max_{\pi\in S_n}\sigma_\pi = \bigl\lfloor\tfrac{n^2}2\bigr\rfloor\). But I don't have a proof of that.
[/sp]
 
  • #5
Opalg said:
[sp]That part looks harder. After experimenting with small values of $n$, I believe that \(\displaystyle \max_{\pi\in S_n}\sigma_\pi = \bigl\lfloor\tfrac{n^2}2\bigr\rfloor\). But I don't have a proof of that.
[/sp]
It would be $\dfrac{n^2}2$ if $n$ is even and $\dfrac{n^2-1}2$ if $n$ is odd – a simple induction clinches the proof.

Thanks for helping me with the challenge! (Clapping)
 

FAQ: Challenge Problem #9 [Olinguito]

What is an Olinguito?

An Olinguito is a small mammal that belongs to the raccoon family. It was discovered in 2013 and is native to the Andean cloud forests of Colombia and Ecuador.

What makes the Olinguito unique?

The Olinguito is the first new carnivorous mammal species to be discovered in the Western Hemisphere in 35 years. It is also the smallest member of the raccoon family, with a weight of only 2 pounds.

How was the Olinguito discovered?

The Olinguito was discovered by a team of scientists who were studying the genetics of a similar species, the Olingo. They noticed distinct differences in the Olinguito's skull and teeth, which led to further research and the discovery of a new species.

What is the diet of an Olinguito?

Olinguitos are primarily frugivorous, meaning they mainly eat fruit. They also consume insects and nectar, making them omnivores. Their diet is similar to that of other members of the raccoon family.

Is the Olinguito endangered?

The Olinguito is currently classified as "least concern" on the IUCN Red List of Threatened Species. However, their habitat, the Andean cloud forests, is under threat from deforestation and climate change. Conservation efforts are being made to protect this unique species and its habitat.

Similar threads

Back
Top