Subscribe via feed.

Blockbuster

Posted by Chris on April 19, 2013 – 5:46 pm

Here’s a repost from many years ago. I have no idea how to do it or what the answer is.

A boy has four red blocks and eight blue blocks. He arranges the twelve blocks uniformly randomly, in a ring.

What is the probability that no two red blocks are next to each other?

As I strongly suspect that combinations are involved, use C(n,r) = n! / ((n-r)! r!) for consistent notation.


This post is under “Logic, MathsChallenge” and has 36 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

36 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    I’m hopeless at combinatorials, so here’s a stab in the dark for your amusement.

    Assume the blocks arranged in a ring correspond to the numbers 1 to 12 on a clock. Then we have C(8,4) = 495 arrangements of red and blue blocks around the clock. If this is wrong then everything that follows is garbage.

    Put a red block in position 1 and tabulate the possible arrangements around the clock which don’t have adjacent red blocks, i.e. 1357, 1358, etc. I get 18 such combinations with the first red block in position 1, and another 18 with the first red bloak in position 2. So each starting position round the clock gives us 18 combinations, so we have 12 * 18 = 216 combinations.

    However, some of these are duplicates. The question is, how many? I would say three quarters of them. This is based on the fact that each combination will be repeated three times starting with each of the other positions in that combinstion. So, for example, 1357 will be repeated as 3571, 5713 and 7135.

    So, divide our 216 by 4 to get 54 unique distributions of non-adjacent red blocks. So, the probability of non-adjacent red blocks is 54/495 = 6/55 or 10.91%.

  2. 2. Chris Said:

    Hi Wiz. You’ve done the counting wrong. You should have got 15 for the 13xx case.

    After that you take a wrong turn and give yourself a difficult problem to crack. Try 14xx as your next step.

    I’ll be kind and let you know that the 495 combinations is correct and that each is equally likely (you won’t believe how long I took to check that). Because we’re using combinations rather than permutations, 1357 is the same as 5371 etc. i.e. the chronological order of placement is irrelevant.

    You should be able to do this one, you’re closer than you might realise.

  3. 3. Wizard of Oz Said:

    Hi Chris,

    Counting is another thing I’m not very good at.

    I got 18 for 1xxx in my first post. In fact I now get 56, rather a large difference.

    My count for 13xx is now 21, not 15 as you state. Putting A for 10, B for 11 and C for 12 we have the following combinations: 1357, 1358, 1359, 135A, 135B, 135C, 1368, 1369, 136A, 136B, 136C, 1379, 137A, 137B, 137C, 138A, 138B, 138C, 139B, 139C, 13AC, i.e. 21 in all.

    Likewise, for 14xx we have 15, for 15xx we have 10, for 16xx we have 6, for 17xx we have 3, and for 18xx we have just the one. Total 56 for all of 1xxx.

    I get the feeling that we should be able to derive this mathematically instead of by counting.

    Incidentally, we’re counting combinations only in a clockwise direction so as to eliminate permutations.

    Proceeding as before we have 12 * 56 = 672 combinations with non-adjacent red blocks around the clock. Eliminating three quarters of these as replicates we end up with 156 unique combinations out of a total of 495, i.e. 56/165 or 33.94%, or just over one third.

    Is this any better?

  4. 4. Chris Said:

    Hi Wiz. Me to, I had to repeat the counting a few times myself. You can’t include C because the C (12 o’clock) is next to the 1 (o’clock).

    I have to count on my fingers, at least to start with. I have started on a slightly generalised version of the problem.

    When you do your counting right you get 15 ways for 13xx, 10 ways for 14xx, 6 for 15xx, 3 for 16xx, and 1 for 17xx. You cannot do 18xx. For 18xx you can do 18A but you can’t put the last brick in at C.

    Holy Mackerel – Pascal’s triangle stuff. 15,10,6,3,1 are all on Pascal’s triangle – and on the same diagonal. The sum of that lot is 15+10+6+3+1 = 35. You’ll find 35 is also on Pascal’s triangle. If you draw it, you’ll be able to see a kind of hockey stick pattern – the 35 being the hitting end.

    There is an identity regarding that pattern. I think it’s called the (or Pascal’s) Hockey Stick Identity. By inspection, you can turn that 35 into the C(n,r) form, and working out n and r isn’t too hard.

    Counting anticlockwise would cause duplications, but not full blown permutations – by that I mean that while there is only 1 combination of WXYZ, there are 4! = 24 permutations.

    Aaargh. You’re right, we can’t simply multiply 35 by 12 – you do get duplicates. e.g. B135 => 1357 by moving round two hours.

    I’ll look at that and see if your 3/4 rule is correct.

  5. 5. Chris Said:

    Sadly, I’ve got to knock off now – I need sleep.

    The way I was going to do it was to start with a ring RBRBRBRB, then insert the extra 4 B’s into it. I haven’t actually started to do that.

    I’m also wondering if it may be easier to count all the cases where 2 or more reds touch.

    For what it’s worth, Rajesh Lal posted this problem way back in the early days of ToM. Nobody made any serious attempt at cracking it, and Rajesh didn’t post the solution. Either that or it’s vaporised. A lot of Cam’s stuff (using Anon) has disappeared. I’m sure he gave a very nice modulo arithmetic based solution to http://trickofmind.com/?p=1653 when it was posted on the old ToM site.

  6. 6. Chris Said:

    Here’s my (experimental) proof that 495 really is the number of combinations and that they are equally likely. It also sheds some light on “3/4″ rule that Wiz has conjectured.

    I started with a simpler version of the problem. This one has 2 blue and 2 red blocks only, and that’s the only difference. The prediction is that there are C(4,2) = 4! / ((4-2)! 2!) = 6 possible arrangements, and behold:

      R          B          B          R          R          B
    B 1 R      B 2 R      R 3 B      R 4 B      B 5 B      R 6 R
      B          R          R          B          R          B
    

    Note that any rotation of the first 4 patterns simply produces one of the first four patterns, but not one of the last two patterns and vice-versa. I’ve labelled the patterns as 1,2,3,4,5,6. Clearly 1,2,3,4 are of a different type to 5,6 based on the rotation idea.

    If I swap the first (at 12 o’clock) and second (at 3 o’clock) over I get:

      R          R          B          B          B          R
    B 1 R      B 5 B      R 3 B      R 6 R      B 2 R      R 4 B
      B          R          R          B          R          B
    

    that’s the same set of patterns, but in a different order. 123456 has changed to 153624

    The operation has left 1 and 3 untouched, and exchanged 2 and 4 from the original two subsets into 5 and 6 from the other original subset.

    If instead I swap the first and the third over I get:

      B          R          R          B          R          B
    B 2 R      B 1 R      R 4 B      R 3 B      B 5 B      R 6 R
      R          B          B          R          R          B
    

    which again is the original set in a different order. But this time the elements have stayed in the same subsets as they started with. i.e. 1234 -> 2143 and 56 -> 56 (i.e. the second subset was unaffected by the operation).

    Sadly, this tells me that group theory is going to be involved to fully analyse the problem. Worse, that suggests to me that Lagrange’s theorem (and that is as far as I have ever studied group theory) is going to enter the analysis. And that might make making a general analysis impractical. The prime numbers will make themselves apparent. As 495 = 3*3*5*11, there’s potential for a lot of sub-groups to be involved.

    However, I have done a similar “study” with 3 blue and 2 red blocks and found that indeed there are exactly C(5,2) = C(5,3) = 10 unique patterns. Exchanging any pairs of blocks in the same way as above simply shuffles the “elements” about in much the same way as above.

    Because I can exchange any pair of elements without destroying the “original” set as often as I like, It seems obviousthat I can randomise the set without changing its elements and that therefore each pattern is equally likely.

    With hindsight, it is pretty obvious that could have been seen immediately. In fact I only really started drawing the pictures to check that C(12,4) = C(12,8) = 495 really was the number of combinations for the ring. I then got carried away.

    So the good news is that there are exactly 495 patterns and they are all equally likely.

    So for the case of 2 red and 2 blues, the required probability is 2/6 = 1/3. For the case of 2 red and 3 blue, there are 10 patterns and it turns out that 5 of them have non-adjacent red blocks. So the probability is 5/10 = 1/2. So I don’t expect to have an easy time with the full 12 blocks problem.

    I’ve got a feeling that there’s a really sneaky way of doing this. I have some faint recollection of solving a problem that involved something like gluing two (or more) blue bricks together as an aid to counting the possibilities.

  7. 7. Wizard of Oz Said:

    Hi Chris,

    You’re right in post 4 above: 13xx should be 15 and 1xxx should be 35.

    Assuming that the 3/4 rule still holds, the number of combinations with non-adjacent reds should be 35 * 12 / 4 = 105. So, with 495 total combinations of blocks, my latest answer to the original question is 105/495 = 7/33 = 21.21%.

    Following on from your suggestion that 35 can be put into C(m,n) form, this could be C(b-1,r-1) where b and r are the numbers of red and blue balls.

    This leads to a general formula for the number of combinations:
    C(b-1,r-1) * (b+r) / r.

    Dividing this by C(b+r,r) leads to the probability of non-adjacent reds being
    (b-1)!b! / ((b-r)!(b+r-1)!)

    Of course, this is only guessed at by generalising from one specific case (4 red, 8 blue) and throwing in a couple of assumptions. Actually proving it is another matter entirely.

  8. 8. Chris Said:

    Hi Wiz. I’m temporarily abandoning the counting method that we’ve been using. I will go back to it in a later post (if you don’t beat me to it).

    Here’s another approach – it’s the one I was intending to use before I adopted your method. Consider the following starting point:

       RB
    B      R
    R      B
       BR
    

    Regard the R and B as pairs (glued together). I got that by starting with the 4 red blocks and inserting the minimum 1 blue block between each pair.

    That leaves 4 loose blue blocks, and we simply have to count how many ways we can insert them between those indivisible RB pairs. When we’re done, we double that number to allow for starting with BR pairs instead.

    Now 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1, that’s 5 unique ways we can divide up 4 blocks. Guess what, there is a number theory function, the partition function, that is precisely about how many ways you can split up an integer in that fashion. It is a very hard function to play with. By pure coincidence, I recently saw a lecture about it by Ken Ono, and I have downloaded a copy of his paper on the topic. It’s ground-breaking stuff. I’ve even seen a suggestion that he might win the Field’s medal due to the work. Hardy and Ramanujan jointly derived an asymptotic approximation to the partition function. Hardy was stunned by Ramanujan’s contribution. Fortunately, it’ll turn out that the partition function is irrelevant.

    Now list all the ways to insert the 4 blocks.
    4000,0400,0040,0004
    3001,3010,3100, 0301,0310,1300, 0031,0130,1030, 0013,0103,1003
    2200,2020,2002, 0202,0220, 0022
    2110,2101,2011, 0211,1201,1210, 1120,0121,1021, 0112,1012,1102
    1111

    That’s 4 + 12 + 6 + 12 + 1 = 35 ways. Add another 35 = C(7,3) = C(7,4) for the shifted case give 70 ways altogether.

    That’s surprised me. So much so that I’m having some doubt about my “proof” of equal likelihood of the 495 combinations and strong doubts about the assumed equal likelihood of the above combinations. I normally assume that all these combinations are equally likely – but that’s substantially an act of faith, and at the moment I’m a non-believer. I’m experiencing cognitive dissonance. Half of me thinks the 70 is correct and half of me says it’s wrong.

    OTOH, I suspect that I’ve made a serious blunder in my assumptions about how the previous clock counting method was going to proceed. In fact I rather suspect that the 35 case previously found is simply to be doubled by advancing the clock by one hour. All other counts will be duplicates of previous ones. In fact, if you think of it as we counted all the cases with a red block at the one o’clock position, we then merely have to count all the cases with a blue block at the one o’clock position. I assert that moving the clock forward one hour does precisely that (but I’m not very confident about it).

    So, I think there are 70 arrangements with non-adjacent red blocks, and so the probability sought after is 70/495 = 0.141414…

    I’ll post this now and re-examine the previous method with more care – I think I can see how to do it nicely.

  9. 9. Chris Said:

    Re my last post. The main part of what I did is OK, i.e. up to counting the 35 ways. But I should have noticed that corresponded to e.g. the topmost red block being at 1 o’clock and that the doubling is caused by it being moved to 2 o’clock. Even then I’m still not happy. i.e. I have very serious doubts about 70 being the right number. I’m pretty sure it should be bigger.

    Just for the heck of it, I note that there are 22 partitions of 8
    8 = 7 + 1 = 6 + 2 = 6 + 1 + 1
    = 5 + 3 = 5 + 2 + 1 = 5 + 1 + 1 + 1
    = 4 + 4 = 4 + 3 + 1 = 4 + 2 + 2 = 4 + 2 + 1 + 1 = 4 + 1 + 1 + 1 + 1
    = 3 + 3 + 2 = 3 + 3 + 1 + 1 = 3 + 2 + 2 + 1 = 3 + 2 +1+1+1 = 3 +1+1+1+1+1
    = 2 + 2 + 2 + 2 = 2 + 2 + 2 + 1 + 1 = 2 + 2 + 1 + 1 + 1 + 1 = 2 +1+1+1+1+1+1
    = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

    However, we’re only interested in partitions with exactly 4 addends, that leaves us with

    5 + 1 + 1 + 1, 4 + 2 + 1 + 1, 3 + 3 + 1 + 1, 3 + 2 + 2 + 1, 2 + 2 + 2 + 2

    5+1+1+1 can be arranged in 4!/(1! 3!) = 4 ways
    4+2+1+1 can be arranged in 4!/(1! 1! 2!) = 12 ways
    3+2+2+1 can be arranged in 4!/(1! 2! 1!) = 12 ways
    3+3+1+1 can be arranged in 4!/(2! 2!) = 6 ways
    2+2+2+2 can be arranged in 4!/4! = 1 ways

    Altogether that’s 35 ways, yet again (but I had expected that). I don’t know what I’m doing anymore :(

  10. 10. Chris Said:

    Just to add to the fun. Consider the four glued up pairs as one kind of object and the four loose blue blocks as the other kind, the number of ways of combining them is 8! / (4! 4!) = 70.

    Maybe 70 is the right number.

  11. 11. Chris Said:

    I’ve found a serious error in my glued together blocks method. I don’t know the fix. There are definitely are more than 70 arrangements. My cognitive dissonance has been mutated into another form.

  12. 12. Chris Said:

    Hi Wiz. I’ve now carefully counted the combinations with non-adjacent red blocks – 105 it is. So the 3/4 rule is correct.

    I am having difficulties cross checking the that result, but I think that’s down to being tired.

    I re-read your argument for 3/4 and realise that I’d completely misread what you said about 1357 being replicated as 3571, 5713 and 7135. I’m sorry about that – you probably thought my response was peculiar.

  13. 13. Wizard of Oz Said:

    Hi Chris,

    Does this mean that we’re agreed on the answer to the original question being 7/33 or 21.21%?

    I tried out the general formula that I dreamed up in post 7 with a couple of smaller combinations of red and blue. It seems to work so far. However, not even a million such confirmations constitute a proof. No doubt someone somewhere has already done this.

  14. 14. Chris Said:

    Hi WIz. Would you trust the opinion of a man who has made such a mess of this stuff ;) I can’t believe that I hadn’t taken in the full impact of your 3/4 rule. Of course it’s right. It’s exactly the sort of clear logical reasoning that you demonstrated the very first time you visited this site.

    Yep, I’m convinced the answer is 105/495 = 7/33 = 0.21212…

    I’m quite sure that all of your general formulae are correct. I also expect that the argument you gave for the “3/4″ rule is that which could be given in a lecture to engineering students. In fact, except for the initial counting errors, I think the whole analysis is substantially what could be given to engineering students (unless there is a shortcut).

    e.g. when you started the “clock” counting, the first step involved 5+4+3+2+1. The 5 is really (b+r) – (2(r-1) +1) = b-r+1. It would then be noted that the subsequent counts would be 4+3+2+1, 3+2+1, 2+1 and 1. Then no doubt Pascal’s triangle and the hockey stick identity (or some equivalent argument) would have been employed to end up with C(b-1,r-1), = 35 in our problem. It might be that the C(b-1,r-1) term could be found more directly.

    Aside. S = 1 + 2 + … + n = n(n+1)/2 => the 5+4+3+2+1 would be (1+(b-r+1))(b-r+1)/2. Quick check: b = 8, r= 4 => (1+5)5/2 = 15.

    Here’s how I got the 105. We’d considered all the cases with a red block at 1 o’clock and found 35 of them. We now consider all the cases with a blue block at 1 o’clock and a red block at 2 o’clock, then all cases with blue blocks at 1 and 2 o’clock and a red block at 3 o’clock, then blue blocks at 1-3 o’clock and a red block at 4 o’clock, then blue blocks at 1-4 o’clock and a red block at 5 o’clock and finally blue blocks at 1-5 o’clock and a red block at 6 o’clock. We don’t consider blue blocks at 1-6 o’clock or more, as then there is no way to avoid pairs of red blocks. Note that this means that no matter where our starting red block is, the last available position is 12 o’clock (11 o’clock on the first round). Other than that, the counting proceeds in an identical fashion to how you did it earlier. The results:

    (B at 12), R at 1 => 35; B at 1, R at 2 => 35; B at 1&2, R at 3 => 20;
    B at 1-3, R at 4 => 10; B at 1-4, R at 5 => 4; B at 1-6, R at 5 => 1

    Altogether that’s 35 + 35 + 20 + 10 + 4 + 1 = 105 possibilities.

    I’m pretty sure that you’ll find that every location ends up having had a red block exactly 35 times. But I kept making mistakes in actually checking that was the case, but got 35 most of the time.

    You’ve also cured my cognitive dissonance. Thank you. I might yet be able to find the C(b-1,r-1) term more directly.

  15. 15. Chris Said:

    I’ve realised why my glued together blocks trick failed. They are oriented, so could have BR:RB. Now I realise that, I might be able to compensate for it. But there again, probably not.

  16. 16. Chris Said:

    I’ve started trying to prove the C(b-1,r-1) term, but have found that that I hadn’t fully apppreciated just why all those 5+4+3+2+1, 4+3+2+1, etc. expressions came about. We were lucky in that they always went down to 1.

    So although I believe that by experiment that that expression is correct, I do see that it needs to be proven. At the moment I’m amazed that it’s so simple. If it’s right, I’m amazed that you seem to have discovered it, apparently without much diffculty.

    — Later. I have started trying to prove the C(b-1,r-1), and will be posting the analysis soon. I half expect that it’ll confirm it. I’m curious about if you mentally did what I’m painstakingly writing up.

  17. 17. Chris Said:

    Hi Wiz. When I started writing the following, I thought it was quite gratuitous – that is until I actually got underway. I’d thought that no matter what, if you started with e.g. 8+7+6+5+4+3+2+1, you’d just keep on forming the sub-sums ending with 2+1 and 1. That’s wrong.

    The overall strategy starts by fixing one red block and finding how many ways we can position the remaing red blocks. When we’ve done that, the total number of combinations is whatever the result was (35 in the case of the posted problem) multiplied by (b+r)/r. i.e. the fixed red block is almost treated as if it were distinct from the other red blocks, until the very last moment.

    In the posted problem, our counting started at 5. That’s because after removing the dead space due to blocks at positions 1,3,5 (which meant that the positions 12 o’clock through to 6 o’clock were unavailable for use by the 4 th red block). The 4 th red block could be positioned at 7 o’clock through to 11 o’clock. That’s 1+1+1+1+1 = 5 positions.

    With b blue blocks and r red blocks, it’s easy to see that the “last” red block could be moved through n = b-r+1 positions. In our case b = 8, r = 4 so n = 8 – 4 + 1 = 5. No matter how many red or blue blocks there are, I’ll reserve n for the start count in all that follows.

    If there are only 2 red blocks, then the 2nd one can only move through n positions. Then we’re done.

    If there are 3 red blocks, then the last block will move through n positions. But then we move the 2nd red block forward one position, then the 3rd red block can be move through n-1 positions. Then we advance the second red block one more position etc. Altogether we’ll get the sum n + (n-1) + (n-2) + … + 2 + 1.

    With 4 red blocks, we add another layer. The 4th and 3rd blocks will produce the sum n + (n-1) + (n-2) + … + 2 + 1, as before. But then we move the 2nd red block forwards one step and repeat the whole process. Then we get the extra sum (n-1) + (n-2) + … + 2 + 1). The we advance the 2nd red block forward again to get the extra sum (n-2) + (n-3) + … + 1) and so on all the way down to the extra sum of 1.

    I’m not even going to attempt to describe the 5 red block case in that fashion. Fortunately, Pascal’s triangle is the key to dealing with that lot, and it does it very nicely, courtesy of what’s known as the hockey stick identity.

    Here’s the top of Pascal’s triangle:

    0                 1
    1               1   1
    2             1   2   1
    3           1   3   3   1
    4         1   4   6   4   1
    5       1   5  10  10   5   1
    6     1   6  15  20  15   6   1
    7   1   7  21  35  35  21   7   1
    

    I’ll take it as well known that most of what I say has been established with full mathematical rigour. Indexing the rows and the diaganols from 0 i.e. the leftmost 1’s diagonal is diagonal 0, the leftmost 1,2,3,4,5… diagonal is diagonal 1. I have indicated the row indexes at the extreme LHS of the diagram. In fact you can use the row number index column to label the diagonals as well. It is a fact that the number at row r, diagonal d = C(r,d) = r!/((r-d)! d!).

    So C(r,0) = 1, c(r,1) = r etc. Now, if you follow down any diagonal, d, to row r, and add the terms, the sum will be found at (d+1,r+1). e.g. 1+3+6+10 = 20. It even proves that 1+1 = 2. That’s a graphical description of the hockey stick identity. Algebraically it’s
    C(r+1,d+1) = C(r,d) + C(r-1,d) + C(r-2,d) + … + C(d+1,d) + C(d,d)
    We’re traversing up the diagonal as we move from left to right.
    NB C(d,d) = 1, C(d+1,d) = d, after that it’s messier.

    With only two bricks and n = 5 say, then the count would simply be 5 (or 1+1+1+1+1 if you prefer). So the formula is C(n,1). With three red bricks (and n = 5), we’d get 5+4+3+2+1 = 15 and that implies C(n+1,2). With four red bricks, we already know to go to C(7,3) and of course that corresponds to C(n+2,3). The pattern is obvious – with r red bricks, we get C(n+r-2,r-1). Substituting for n = b-r+1, we get Wiz’s formula (phew), C(b-1,r-1).

    I don’t recall previous knowledge of this hockey stick behaviour. If I had known of it before, I certainly wasn’t aware of the nested behaviour. I think it’s quite beautiful.

  18. 18. Chris Said:

    I don’t know that I’ll follow it through (I’m not that masochistic), but I expect that a generalisation to e.g. no three red bricks adjacent may not be too hard. I’m not sure how hard it would be come to extend it to no touching red bricks and no touching blue bricks. Either might be easy or hard.

    Rajesh has only had to wait 5 years to get his problem answered. Wiz, you are the man.

  19. 19. Chris Said:

    I probably won’t post it until tomorrow, but I’m very close to the shortcut to the result. Just to tantalise you:

    C(b-1,r-1)*(b+r)/r = C(b,r)*(b+r)/b.

    I found it because I realised that if b >> r, that by removing the minimum one blue block between the red blocks, and allowing the red blocks to touch, that the number of combinations must be almost the same as for the constrained case with all of the blue blocks present. i.e. the approximate answer is C(b,r). In fact it was suddenly obvious that the exact answer almost certainly has to have C(b,r) as a factor. The other factor is because simply removing r blue guard blocks is naive – there must be one guard block between each pair of neighbouring red blocks. I’ve simply got to show that is why there is a factor of (b+r)/r to go. Anyway, I realised that I could use your equation to confirm my conjecture – it is no longer a conjecture.

  20. 20. Wizard of Oz Said:

    Hi Chris,

    I haven’t worked through all your reasoning but it looks like you’ve nailed the proof.

    As you say, C(b-1,r-1) is the key. You were kind enough in post 16 to give me credit for discovering it. In fact, I didn’t – you did. In post 4 you said:

    “There is an identity regarding that pattern. I think it’s called the (or Pascal’s) Hockey Stick Identity. By inspection, you can turn that 35 into the C(n,r) form, and working out n and r isn’t too hard”.

    You’re right – it wasn’t too hard!

  21. 21. Chris Said:

    Hi Wiz. After a careful think, I accept that I had taken you closer to the
    C(b-1,r-1) result than I had remembered. All the same, I didn’t complete the argument.

    Strangely, I had forgotten that I had seen the nesting behaviour of the hockey stick when writing post 17. I certainly hadn’t fully appreciated the way the depth of the nesting depended on the number of red blocks (until post 17).

    However, it was your counting method that obtained the number 35 and in such a way that I was able to see that hockey stick was involved. It was also your reasoning that produced the (b+r)/r factor. I didn’t even recognise that that factor was correct until at least a day had passed after you published it.

    So, in my opinion, you were by far the main contributor – I merely assisted you.

    Just for the heck of it, the final probability may be written as:

       C(b,r) / b   
    C(b+r,r) / (b+r)
    

    I think that that’s quite sweet.

    Sadly, I still haven’t come up with the shortcut. That’s quite gutting, especially as I’m now certain that there is one. Even more so as, whatever it is, it is a cousin to my failed glued together blocks attempt.

  22. 22. Chris Said:

    Although I haven’t succeeded in getting the shortcut to the C(b-1,r-1) formula, I’ve decided that the following is sufficiently interesting to post it anyway. Perhaps it’ll nudge some bright spark into completing the argument.

    The quantity C(b-1,r-1) is the number of ways or combining b blue and r red blocks subject to the constraints that no two red blocks can touch and that one of the red blocks is in a fixed position. The latter implies that there must be a sequence BRB that’s in a fixed position.

    I now want to transform this into the simpler problem where we have B blue blocks and R red blocks, which have no constraints. For such a problem, the number of combinations is C(B+R,R).

    So we need B + R = b – 1 and R = r – 1 => B = b – r. This formally suggests that r blue blocks are being used solely to prevent the red blocks from touching, and that the fixed red block isn’t contributing to the number of distinct arrangements. Superficially, that makes sense. But there’s more going on than meets the eye. There must be some self-cancelling dynamics present. Specifically, I can’t see how to use a simple argument to directly see how to do the transformation.

    This stuff is highly suggestive, but I don’t know the next move, so I’ll stop here.

  23. 23. Chris Said:

    Here’s another tidbit/waffle. If remove the RB or BR from the fixed BRB sequence, then the remaining fixed B guarantess that the two nearest red blocks cannot touch on their sides nearest to the fixed B.

    I also note that in terms of forming the C(B+R,R) (labelled) system, that as I must remove at least two blue guard blocks (as there must be at least two red blocks for the problem), I might as well remove the two fixed ones in the fixed BRB sequence (altogether I can remove the BRB sequence). Then there is no actual fixed blue block. But that’s sneaky. I can’t argue that the remaining guarding blue blocks are fixed – although on average they seem to behave as if they were.

    That reminds me of the problem that slavy posed regards the probability of an acute (or was it oblique) triangle in a circle.

    However, unless I can show by very direct means that that is “obviously” true, I haven’t really made any progress. There is little point in replacing the complex hockey stick argument with a similarly complex alternative.

  24. 24. Chris Said:

    I’ve cracked it. Yeeehah! (’bout bloody time too).

    The reason that I’ve been making such a hash of this is that I’m stupid and haven’t been properly distinguishing between a ring and a straight line. I’ll deal with that first. Wiz had in fact got it. I’ve only just caught on.

    Let there be a total of n elements. Let t of the elements be of type T. To deal with a ring, fix (the position of) one of the elements with property T, and do the analysis, subject to any required constraints, with the remaining n-1 non-fixed elements.

    You might find it helpful to think of the fixed T type element as being distinct from the other T types.

    Let C be the number of “combinations” found. To compensate for fixing the element, we must now let it move through all the, n, available positions in the ring. Obviously that boils down to multiplying by n. But we will have then have moved all t of the T type elements through all the positions around the ring as well, and so we’ll have overcounted by a factor of t. Altogether we end up with C*n/t combinations.

    That rule is perfectly general. It doesn’t matter what constraints you have or how many different types of elements you have. It’s obvious (LOL).

    — now for the shortcut answer

    Now that’s out of the way, I can finally give the quick answer to the generalised version of the posted problem.

    Start with just the b blue blocks in a ring. Between each pair of blue blocks there is a latent gap that is allowed to take at most one red block. The number of ways that we can insert the red blocks into those latent gaps is precisely equivalent to the number of ways that we can choose r gaps from b gaps, and that is C(b,r) ways.

    Because this is a ring problem, we must regard one of the blocks as being fixed (if you like, it is distinct from the other blue blocks). Then we get the final result by multiplying by (b+r)/b.

    Altogether that gives C(b,r)*(b+r)/b and I think that that is as close to a shortcut as I’m going to get.

    The unconstrained number of combinations is C(b+r,r). See next post (25) for a proof. So the desired probability is

    C(b,r) * (b+r)
    C(b+r,r) * b

    With b = 8, r = 4, we get
    (70*12)/(495*8) = 105/495 = 7/33 = 0.212121…


    Now I’ve done that, I’ll say with my usual arrogance, that that’s the way it would have been done in a lecture to engineering students.

    What I love about maths is things like this. I’ve just found using a fairly straightforward argument a result. But I know from the hockey stick version, that I have also found a really easy way to do all those nested sums of sums of sums …

    It is well known that S = 1+2+3+…+n = n(n+1)/2. And usually an anecdote involving Gauss is associated with it. By direct manipulation or the hockey stick argument, we can see that S = C(n+1,2).

  25. 25. Chris Said:

    I want to show that the apparently simple bit about the arrangements of b blue and r red blocks is indeed C(b+r,r) = 495 in the original problem. I had resorted to experiment when I was was satisfying myself that it was correct.

    Fix a particular red block. That will leave C(b+r-1,r-1) combinations. Now multiply by (b+r)/r to get (b+r)(b+r-1)!/(b! r(r-1)!) = (b+r)! / (b! r!) = C(b+r,r)

    OR fix a blue instead. That will leave C(b+r-1,r) combinations. Now multiply by (b+r)/b to get (b+r)(b+r-1)!/(b (b-1)! r!) = (b+r)! / (b! r!) = C(b+r,r) yet again.

    I’m convinced.

  26. 26. Wizard of Oz Said:

    Hi Chris,

    Nice work. I’ve been trying what I thought might bt a more direct approach: arrange r reds and blues alternately in a circle then work out how many ways the remaining b-r blues can be fitted into the r available spaces. This should come to C(b-1,r-1) but I can’t make it work.

  27. 27. Chris Said:

    Hi Wiz. Thanks. Your derivation of (b+r)/r factor (aka the 3/4 rule) was of the greatest assistance to me. In fact the way you approached the problem (especially the fixed red block) was key to getting my understanding to its present level. So, I thank you sir.

    You posted while I was re-editing post 24. I’ve improved it dramatically. If you read it again, I think that you might decide to cease further investigations.

    You’re trying to do what I had been trying. Obviously it can be done, but I know that it’s painfully difficult to do. I practically guarantee that you’d end up invoking the hockey stick rule or some similarly involved maths before you’d finished.

    Even before my revision, the breakthrough was almost the reverse trick. i.e. start with the blue blocks, then insert the red blocks.

  28. 28. Chris Said:

    A common convention that with rings is that a pattern is not considered to be unique if it simply a rotated version of another one. In the case of permutations, you simply divide the number of permutations by the number of elements in the ring to get the number of ring-wise unique permutations.

    Put another if there are n patterns in a ring that only differ by a rotation, then those patterns are regarded as being a single ring-wise unique pattern (RWU from now). That isn’t official terminology.

    Clearly, if have an element that is unique and n elements altogether, for any given arrangement with that unique element at a certain location, you can immediately produce n-1 more copies by simply rotating the ring in n-1 steps. I’m saying that corresponds to 1 RWU pattern.

    However, when you have more than one element of a given type (And are thinking in terms of combinations), things get more complicated. You can’t simply divide by the total number of elements. That’s because some of the patterns may be reproduced many times when you completely rotate the ring.

    For the case of 3 blue and 2 red blocks, there are C(5,2) = 10 patterns. They’re easy to list out completely. There are two RWU patterns, and each appears 5 times.

    For the case of 2 blue and 2 red, we get C(4,2) = 6. And again that’s easy to list out. Again we have two RWU patterns. One is present 4 times, and the other 2 times.

    The treatment that Wiz and I have been using, has taken the rotated combinations to be distinct. I think of the ring as being orientated. Orientated rings are much easier to deal with that non-orientated rings. The maths is much easier.

    I’ve got to visit a customer now. I’ll attempt to extract all the rules. In anticipation of what I expect is going to be involved, I’ve posted A divisibility problem.

    Later: Having started to examine this, I can see it might be too difficult for me to do a decent job of it. So don’t hold your breath waiting.

  29. 29. Chris Said:

    While trying to do Blockbuster 2, I thought I’d really goofed up on how to do combinations with rings.

    Anyway, that lead me to yet another way to calculate the answer.

    Start with a fixed red block and all the blue blocks. Only one such arrangement exists. There are b-1 latent gaps for the remaining r-1 red blocks. So there are
    C(b-1,r-1)*(b+r)/r ways of combining. This can be rewritten as C(b,r)*(b+r)/b by straightforward manipulations.

  30. 30. Chris Said:

    I really have been struggling with the ring combination factor. So to convince myself that the rotation factor is right, I thought up the following. I’m only considering the cases where no two red blocks touch.

    Lay the blue blocks in a ring and insert 1 red block at a particular position, 12 o’clock say. We can only fit the remaining r-1 red blocks between the blue blocks, and that gives b-1 places. The number of ways that we can do that is C(b-1,r-1). If we now rotate any of those patterns until another red block is at the 12 o’clock position, then no new patterns will be introduced.

    The other possibility is to lay the blue blocks in a ring, and consider one to be fixed at 12 o’clock. Then we may fit a red block between any of the blue blocks. That’s b places to insert the r red blocks. So there are C(b,r) ways of adding the red blocks. If we now rotate any of those patterns until another blue block is at the 12 o’clock position, then no new patterns will be introduced.

    As there are no other possibilities for the colour of the block at 12 o’clock, we must have that the total number of combinations is: C(b-1,r-1) + C(b,r).

    Now C(b-1,r-1) = (b-1)! / ((b-r)! (r-1)!). Multiplying top and bottom by br =>
    C(b-1,r-1) = b! / ((b-r)! r!) * (r/b) = C(b,r) (r/b). The total number of combinations is, therefore, C(b,r) (r/b) + C(b,r) = C(b,r) (r+b)/b as previously claimed. Phew!

  31. 31. Chris Said:

    After re-reading this page, I’m highly embarrassed about how thick I’ve been. Although I got there in the end, I sure took my time about it – almost two weeks. Would you believe that I wasn’t completely sure of the result until after post 30 :(

    Conversely, except for silly counting mistakes, I think that Wiz had (at least substantially) got the complete solution in the very first post :)

    I’m pretty sure that slavy would have just written the solution as if it were self-evident.

  32. 32. Chris Said:

    OMG I had started to waver about this stuff being right, yet again. But I can now identify and dispel the source of my doubts.

    Consider a case with 4 blue and 2 red. There are three fundamental patterns. i.e. they cannot be rotated into one another. I’m using lower case r to emphasise the patterns.

      1 2       r r       r B       r B
     6   3     B   B     B   r     B   B
      5 4       B B       B B       B r
    

    For the first and second, we can find 5 more patterns by rotation. For the third, we can only get two more patterns by rotation. Altogether we have 15 unique patterns (counting rotational variations), but only 3 genuinely different patterns. It happens that C(4+2,2) = 15.

    If I happen to place a red block at position 1, then I am equally likely to place the second red block at position 2,3,4, 5 or 6. Positions 2 and 6 correspond the the first of the three fundamental types, positions 3 and 5 correspond to the second of the three fundamental types, but only position 4 corresponds to the third fundamental type. So the first two fundamental types are twice as likely as the third. That’s completely consistent with the 15 patterns being equally likely.

    C(6,2) = 15 isn’t divisible by 4+2 = 6. It is clear that that fact is accounted for by the fundamental types not having the same rotational symmetry. If we examine the case with 3 blue and 2 red, we find that there are 2 fundamental types, and that each has 5 rotational variations. Note that 2*5 = 10 = C(3+2,2). We also see that 10 is divisible by 3+2 = 5. I believe that that is not a coincidence. I’ve taken a look with 4 blue and 3 red. There are 5 fundamental types, and each has 7 rotational variations. Note that C(7,3) = 35 = 5*7.

    I think that, in general, b+r is prime if and only if the fundamental types have the same number, b+r, of rotational variations.

    If I consider a ring by fixing one of the blue blocks, I’d say that the number of combinations for the remaining blocks is C(b-1+r,r) = C(b+r,r) b/(b+r). If I’d instead chosen a red block to be fixed, we’d get C(b+r,r) r/(b+r). If we add those we get C(b+r,r).

    The probability of the fixed location having blue block is b/(r+b) and of having a red block is r/(b+r). That all seems to make sense. i.e. the number of combinations with a blue block in a particular position, is the total number of combinations regardless of the colour of the block, times the probability of there being a blue block in that place.

    For the b = 4, r=2 case, we get the total number of combinations with no two reds touching is C(b,r) (b+r)/b = 9. That’s 6 rotational variations of fundamental type 2 and 3 rotational variations of the fundamental type 3. so yahoo, that all seems to fit together.

    In post 30 I said that for a fixed red block that there are C(b-1,r-1) combinations where no two reds are touching, and that rotating any of them until another red is in the fixed position would introduce no new patterns. Let’s check that that is correct. With b=4, r=2, we get C(3,1) = 3. That 3 consists of 2 of the type 2 fundamental patterns and 1 of the type 3 fundamental patterns. And sure enough, my claim turns out to be true. Similarly I claimed that with B fixed there’d be 6 combinations. That turns out to be 4 of fundamental type 2 and 2 of fundamental type 3. And the claimed rotational invariance holds true also. In fact all of that is very easy to see on my diagrams above, just by choosing each B or R location to be the fixed one.

    I’m coming to the conclusion that getting old has definitely mucked up my brain. I’m finally happy that the solution to the posted problem is 105/495 = 7/33 and that I have nothing more to worry about.

  33. 33. slavy Said:

    Great to see that the site shows some symptoms of life :) I admit I didn’t read all the post above, so I apologize if I’m repeating somebody’s solution here, but let me give a fairly short (and in my opinion elegant) argument why the answer is 7/33.

    First of all, we are on a ring so we can fix the element at first position to be R. Now we are left with 11 positions that are 3 Rs and 8 Bs. All the possible permutations are C(11,3) (i.e., we choose the positions for the Reds and the remaining ones are occupied by the blues). Now, let’s count the good ones: after each red there should be a blue, therefore we can deal with a new item RB. Since we start with a red, we need to start the “new” permutations with RB. We are left with 3 more RBs and 4 Bs, thus we have C(7,3) good permutations overall. Finally, the answer is good/all = C(7,3)/C(11,3)=(5*6*7)/(9*10*11)=7/33

  34. 34. Chris Said:

    Hi slavy. I’m relieved that you didn’t come up with a different probability. Thank you so much for posting another way of doing it.

    Inspired by your comment, I also realise that we could start with a ring RBRBRBRB and then have 8 positions to insert the remaining 4 blues. But that gives me 70 (and then doubled to 140). Unfortunately, I’m just about to be picked up by a customer, and won’t be able to devote myself to taking in what you’ve done, or work out why my latest idea has gone very wonky before this evening.

  35. 35. Chris Said:

    Hi slavy. I know why my last attempt failed. I posted it too hastily.

    I can only just about grasp why your method works – in particular why the C(7,3) is right. I seem to have got into a wrong way of thinking about combinations. I keep on resorting to partitions quite unnecessarily.

    I’ve now got to retrain my brain.

  36. 36. Chris Said:

    Hi slavy. I finally understand all of your method (I really do seem to be slowing up nowadays).

    I quite like the main part of my version (middle bit of post 24) – I’ll redo it in a moment. I have to concede that yours is the best (possible?) solution. All that rotation stuff that Wiz and I did was unnecessary, but interesting. I also like the fact that you made RB pairs. It’s the first thing I thought of, but spectacularly failed to make progress with.

    Make a ring of 8 blues. (We can regard one as being in a fixed position). We can insert the 4 reds, without them touching each other, in C(8,4) ways (i.e. that’s the number of ways we can choose 4 insertion points from 8). Now start again with a fixed blue. We can add the remaining 7 blues and 4 reds in C(11,4) ways. So the probability is C(8,4)/C(11,4) = 7/33.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0