Let be an ascending sequence of number. If swapping the and position is considered as one step for , then determine the least number of steps needed to reorder the sequence to be a descending one ().Β How can you be sure that your number is indeed the least number of steps?

P.S. Even though this problem looks like a toy problem, it definitely isn’t. This is a dumbing down version of a real problem I’ve solved in using a computer program before. I really saved a lot of time by solving this problem π

Advertisements

wow, interesting! π

I’ll find the answer…

let me count it first

I got it π

the answer is (n^2-n)/2 isn’t it??

Ahaha.. you are indeed correct

CMIIW, you are Marisa’s sister aren’t you?

Have you thought of an argument of why it is indeed the answer? That’s the real challenge π

I used “ordinary generating function” coz as I know it is one way to solve that kind of problem…

btw how did you know that I’m Marisa’s sister??