[I hope this write up makes sense – I wrote it while my kids were watching Lord of the Rings “Two Towers” – so there was a bit of a distraction in the background]
Saw this problem posed on Twitter yesterday:
I like Fenton’s request to share solutions, and actually made a similar request previously with a problem from the Euorpean Girls’ Math Olympiad:
A Challenge / Plea to Math Folks
Having made a similar request, I’m sort of obligated to respond to this one!
There are a couple of different ways to approach Fenton’s problem, and I’d guess that the counting technique of “inclusion / exclusion” would probably be a common choice of how to attack the problem.
However, since the numbers were small enough I thought it would be fun to see if I could count the possibilities directly.
The main ideas I used to approach the problem were these:
(1) I’m going to try to count the arrangements with no songs by the artists next to each other. If I can find the probability of finding such an arrangement then 1 – that probability is the probability of having at least one pair.
(2) Next, I’ll ignore the different songs by different artists and just look for arrangements of the 8 numbers 1,1,2,2,3,3,4,4 with no numbers that are the same next to each other. If I can count these sets, the the arrangements of the number of songs with no songs by the same artist next to each other is just 
(2) For any arrangement of the 8 numbers – say 1,4,3,2,3,4,1,2 – a unique permutation of the numbers 1,2,3,4 will change the arrangement to one in which we encounter the numbers in increasing order. In my example, simply switching 2 and 4 changes the example to 1,2,3,4,3,2,1,4.
For a second example. Consider 3,2,4,3,2,1,4,1. If I map 1 to 3, 2 to 2, 3 to 4, and 4 to 1 I have the new sequence – 1,2,3,1,2,4,3,4 – in which we, again, encounter the numbers in the order 1,2,3,4. So, using this idea, if I can count the number of arrangements with no pairs in which the numbers appear in order, all I need to do is multiply by 4! to get the total number of arrangements of similar patterns.
So, let’s count:
(A) Arrangements of the form 1,2,3,4,_,_,_,_
There are 3 choices for the 5th numbers, and after that choice the remaining 3 numbers can be arranged in any of the 3! ways. So, there are 3*3! arrangements of this form, or 18.
(B) Arrangements of the form 1,2,3,1,_,_,_,_
There are two cases to consider:
Case 1: the 5th number is 4. There are then 2 choices for the 6th number (2 or 3) and 2 ways to arrange the remaining 2 numbers ( 4,2 or 2,4, for example, if the first choice was 3). Thus there are 2*2 = 4 arrangements of this form.
Case 2: The 5th number is 2 or 3. So, there are 2 choices for the 5th number. 4 must be the 6th number otherwise the arrangement would end 4,4 which we don’t want. The final two numbers are then forced. Thus, there are 2 arrangements of this form.
So, a total of 6 arrangements begin 1,2,3,1
(C) Arrangements of the form 1,2,3,2,_,_,_,_
This case is essentially the same as case (B) – so we get 6 more arrangements.
We’ve now covered all of the cases of the form 1,2,3,_,_,_,_,_ and the only other cases begin with 1,2,1 since the numbers must appear in order.
(D) Arrangements of the form 1,2,1,2,_,_,_,_
There is only 1 – which sort of surprised me (!) but the remaining slots are forced to be 3,4,3,4 by the increasing condition and the condition that no numbers appear next to the same number.
(E) Arrangements of the form 1,2,1,3,_,_,_,_
As with (B) above, we have two cases:
Case 1: The 5th number is 2.
Here the arrangement is forced to finish 4,3,4. So, there is only 1 arrangement in this case.
Case 2: The 5th number is 4.
Here we have 2 choices for the 6th number – 2 or 3. For either choice the remaining two numbers can be arranged in any order (4,2 or 2,4 if the choice for the 6th number was 3, for example). Thus there are 4 cases here.
So, part (E) has 5 total cases.
Putting it all together.
So, that’s all the cases, and we end up with 18 + 4 + 2 + 4 + 2 + 1 + 1 + 4 = 36 total arrangements in which (i) the numbers appear in increasing order, and (ii) there are no pairs.
As mentioned at the beginning, when we distinguish between the two 1’s, the two 2’s, the two 3’s, and the two 4’s, the number of arrangements is multiplied by 16. Also, when we no longer require the numbers to appear in order we multiply the number of arrangements by 24.
So, the total number of arrangements with no pairs is 36*16*24. The total number of arrangements is 8!, so the probably of having no pairs is:
(36 * 16 * 24) / 8! = (36 * 16 ) / ( 8 * 7 * 6 * 5) = 12 / 35.
Thus, the probability of having at least one pair is 23 / 35.
Mike's Math Page 