Math combination puzzle

[pulykamell]

This could just as well go into MPSIMS, but this has factual answers and a GQ attached to it.

The following problem was forwarded to me. How does one go about solving it:

http://hilltop.bradley.edu/~delgado/potw/p195.html

I’m not going to use spoilers, so if anyone want to try solving the problem on their own without my influence, please don’t read on.

Usually with combination and permutation problems, I start with smaller sets and try to find a pattern that develops. I write set of 1, 2, 3, 4, 5 and then extrapolate up to the number I need, because I can never remember the formulas, since I don’t use them all that often.

Anyhow, according to the rules of the problem, each chart must be unique, songs cannot climb the charts once they’ve fallen, and I assume this means any given song can stay in the same position, as long as there is movement elsewhere in the chart.

With 1 item, I have one possibilty satisfying the parameters: A
With 2 there’s two: AB and BA
With 3 there’s four: ABC, BAC, BCA, CBA
With 4 there’s seven: ABCD, BACD, BCAD, CBAD, CBDA, CDBA, DCBA
With 5, I found 11 (won’t list them all.)

If this pattern extends to 20, there should be 191 charts that satisfy the requirements.

Of course, there is much that can go wrong with my intuitive approach. I may have missed some chart sequences that satisfy the problem’s requirements. Perhaps the pattern doesn’t follow the rule I’m applying to it. Thirdly, there must be some mathematical way of arriving at the answer, but I can’t see it.

My solution seems very sloppy, but for a quick back-of-the-envelope guess, I don’t think it’s too shabby.

So what is the answer, and what is the method?

[TJdude825]

I kind of like your way, but they way I did it (or, the way I thought about it, before trying to find the answer) was more like this:

http://hilltop.bradley.edu/~delgado/potw/s195.htmlLet’s look at the initial and the final weeks of the rankings. During this time, the song initially in the top position can drop at most 19 spots to position 20; the second ranked song can drop at most 18 spots to position 19, and so on. This can take at most 19 + 18 + … + 2 + 1 = 190 weeks. Therefore there are at most 191 weeks in which the same songs can appear on the charts. You can achieve this maximum, by switching only two songs each week.

[erislover]

[spoiler]The first song, #1, can move down 19 times before it reaches position 20, moving each song up a position as it does so. #2 is now #1, and it can move down 18 times (if it moved one more, a song would have to regain lost popularity). Song #3 is now song number one. So what you have is
1, the original configuration, plus
19, song number 1 moving down, plus
18, song number 2 moving down after originally moving up, plus
…
1.

Which I calculate to be 191 as well.

1+SIGMA of r[sub]1[/sub][sup]N-1/sup
Which is r going from 1 to N-1, being
1+ (19+18+…+1)[/spoiler]I forget what the formula for such sums are, but it is easy to generalize mathematically.

[erislover]

Arithmetic series. Duh. Mathworld link.

[erislover]

So, for completeness’s sake, which if I don’t post will irritate me, the answer for any N songs on the top N list is:

1 + (N[sup]2[/sup]-N)/2

[pulykamell]

Holy crap, my method worked. :eek: I knew there must be a more logical way of approaching this other than brute force. Thanks for the info.

[Little_Nemo]

I think there may be a false assumption in some of these solutions. A song cannot rise in the charts once it’s begun its descent. But a song that began at the #20 spot can rise up to #1 and then work its way back down to #20.

[pulykamell]

@Little Nemo

I think there may be a false assumption in some of these solutions. A song cannot rise in the charts once it’s begun its descent. But a song that began at the #20 spot can rise up to #1 and then work its way back down to #20.

It can, but it has no room to do so. That is, all the combinations are exhausted once the #20 song reaches #1. If it were to fall, then a song below it would have to rise in the chart to give it place to fall to, violating our rule that a song once fallen cannot rise.

[erislover]

@Little Nemo

I think there may be a false assumption in some of these solutions. A song cannot rise in the charts once it’s begun its descent. But a song that began at the #20 spot can rise up to #1 and then work its way back down to #20.

If song 1 moves down to the bottom, then song 20 had to have moved up one to make room, yes?

[erislover]

Ah, I see what you mean. Our OP has it, though: for it to move back down, something else that already moved down would have to move up.

[rjk]

From the Mathworld page:

This is the trick Gauss Eric Weisstein’s World of Biography used as a schoolboy to solve the problem of summing the integers from 1 to 100 given as busy-work by his teacher. While his classmates toiled away doing the addition longhand, Gauss wrote a single number, the correct answer

I remembered the story and the idea behind the formula, but not who did it.

[rjk]

Damn! Should I preview next time? Mods, can this be fixed please?