2
$\begingroup$

This question already has an answer here:

I imagined a system of $n$ "things" that are ordered: each "thing" has a specific place. Also, the $n$th thing is the last thing in the system, meaning that there is always a "thing" to which number $1$ is assigned. Given such a system, we can "mess it up" — put things in wrong order. Now we must put them back. Like so (an example):

enter image description here

We see that in this case, we have a system $n = 5$. If all the "things" are in their spots, then the output of the function I wanted to deduce (but failed) is $0$. But if they are not, my "function" adds $1$ to its output for each place a misplaced "thing" must travel to get to its original location. In the above case, the output of function in order to "clean up the mess" is $8$.

The question is: for some system $n$ (where $n \in \mathbb{N}$), what is the maximum of the function $f$?

I already found $f_{\text{max}}$ for $n = 1$ ($f_{\text{max}}(1) = 0$), $n = 2$ ($f_{\text{max}}(2) = 2$) and $n = 3$ ($f_{\text{max}}(3) = 4$). But it is quite clear that this problem needs a different approach; bruteforce won't do any good. So, my main interest is to know what a formula for $f_{\text{max}}(n)$.

I am very eager to see the answer. I tackled a few hard problems, but this one (and the strange thing is that I made it up myself) is one tough cookie, at least for me.

$\endgroup$

marked as duplicate by Rahul, Community Dec 2 '17 at 18:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I seem to have had my comment deleted? $\endgroup$ – Paul Aljabar Dec 2 '17 at 18:24
  • $\begingroup$ @PaulAljabar What? I have no idea how this happened! $\endgroup$ – Gregor Perčič Dec 2 '17 at 18:44
1
$\begingroup$

It seems clear that the maximum occurs when you reverse the sequence. Consider the cases $n$ odd and $n$ even separately, and add up the number of positions each item has to move. For example for $n$ odd, the sum is $2(2+4+\,...+\,n-1)$ and for $n$ even it is $2(1+3+5+\,...\,+n-1)$. Work it out to show that for $n$ odd $$f_{odd}(n)={1\over2}(n^2-1)$$ and for $n$ even, $$f_{even}(n)={1\over2}n^2$$

$\endgroup$
  • $\begingroup$ This is a duplicate of this question - see also the good blog post here $\endgroup$ – Paul Aljabar Dec 2 '17 at 20:21
  • $\begingroup$ Actually, the two results are the same. In the answer you refer to, the notation is different (it is not expressed in terms of $n$). Do the substitution and you will find the results agree. (This comment was for a previous version of Paul's comment where he claimed this answer is incorrect). $\endgroup$ – Dean Dec 2 '17 at 20:22
  • $\begingroup$ Yes, I got that. Just wanted to make it clear that it is a duplicate. $\endgroup$ – Paul Aljabar Dec 2 '17 at 20:24
3
$\begingroup$

I think (one) most messed up configuration is given by $n,n-1,n-2,\ldots, 1$. $1$ and $n$ have to travel $n-1$ positions, $2$ and $n-1$ have to travel $n-3$ positions and so on. So I think if $n$ is even you have maximal $2*((n-1)+(n-3)+\ldots +1)=2*(n/2)^2$. Please correct me if i am wrong.

$\endgroup$
  • $\begingroup$ Fair enough. I hoped that this semantical problem would be integrated into an algebra ring, or something. Your reasoning is interesting, but I'm looking for a comprehensive answer. And the real problem are still odd $n$s (I expected that $f_{\text{max}}$ for them would be WAY harder in comparison). $\endgroup$ – Gregor Perčič Dec 2 '17 at 18:07
  • $\begingroup$ The "most messed up" configuration is not unique: You can also move the first half of the things to the end, like cutting a deck of cards; this also gives $f=n^2/2$. $\endgroup$ – Rahul Dec 2 '17 at 18:08
  • $\begingroup$ @Rahul that's why I wrote "one". $\endgroup$ – Nightgap Dec 2 '17 at 23:31
  • $\begingroup$ Sorry, I wasn't correcting you, just offering a concrete example of non-uniqueness. $\endgroup$ – Rahul Dec 2 '17 at 23:58
  • $\begingroup$ @Gregor Perčič note that the same argumentation can be applied if $n$ is odd. Then you have $2*(2+4+\ldots+(n-1))=4*(1+\ldots+(n-1)/2)=4*\frac{\frac{n-1}{2}\left(\frac{n-1}{2}+1\right)}{2}=\frac{1}{2}(n^2-1)$. $\endgroup$ – Nightgap Dec 3 '17 at 0:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.