## Blockbuster 2

Posted by Chris on April 24, 2013 – 11:30 am

This is a non-trivial extension to the previous blockbuster problem.

Use b blue, 3 green and 3 red blocks, to form a ring. If no reds are allowed to touch each other, and no greens are allowed allowed to touch each other, how many unique patterns can you form?

To keep things simple, rotated versions of a pattern are to be regarded as distinct (just as was assumed in the previous blockbuster problem).

April 24th, 2013 at 7:13 pm

I have simplified the problem, but it’s still fairly hard.

Later: There is a chance that the highly desirable generalisation to b blue, r red and 3 greens may not be as hard as I thought.

Later still: The generalisation is possible, but it would involve “placeholder” functions. The placeholders would have to be evaluated for each particular number of green blocks.

I am not going to add a four colour version of this problem.

May 1st, 2013 at 3:54 pm

This problem is much tougher than the first Blockbuster. If we, say, start with just the blue and green blocks, then we have to consider cases where the green blocks do touch. The red blocks can be used to split the touching green blocks apart, later.

Unless I’ve made a major error in my reasoning, we have to consider each possible value of g (the number of green blocks) as a special case. That’s because there is no simple way to state the various possible ways that we could divide the green blocks up when an arbitrary number of blue and/or red blocks are to be considered. For instance, if we had 5 green blocks, they could initially be inserted into a ring (assuming loads of blue blocks) in 7 fundamentally different ways. That’s because 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1. The 5 would actually form a ring if there were no blue blocks. The number of ways is given by the partition function, and the partition function is very far from simple. Not only are the number of partitions difficult to determine, we actuallly need to know every partition completely and for each one we have to consider the sequence of writing as relevant too. See partition function

The method I’m going to use is, essentially, to consider the possible arrangements of the blue and green blocks, then add in the red blocks. But I might look ahead for some cases. The extension to higher value of g should be almost obvious.

Because g = 3 = 2+1 = 1+1+1, we have up to 4 starting points, depending on the number of blue blocks. i.e. b = 0 => we must have a ring of 3 mutuallly touching green blocks. b > 0 then we cannot have a ring of 3 mutually touching green blocks. b = 1 => GGG is the only possibility. b = 2 => GGG or GG+G are the only possibilities. b ≥ 3 => GGG or GG+G or G+G+G are possible. NB in more complex cases, we’d have to consider e.g. G+GG to be distinct from GG+G (that doesn’t kick in until g ≥ 6)

To be able to satisfy the problem we need b+g ≥ r and b+r ≥ g. Together that => b ≥ Abs(g-r). If that condition isn’t met, then there are no possible combinations. If b = 0, then we must have r = g = 3 and only two patterns are possible (due to the orientation of the ring).

Case of we have GGG and b ≥ 1. We have to fit red blocks in the GGG to get GRGRG. Any extra red blocks can be fitted anywhere else, subject to no two touching. Now consider the GRGRG as being at a fixed position, and note that there can only be one such sequence. With b blue blocks, we have b+1 possible insertion points for the remaining r-2 red blocks (make a sketch to help see that is so). There are C(b+1,r-2) ways to do that. The rotation factor is simply (b+r+3). Altogether that gives us C(b+1,r-2)(b+r+3) combinations.

Case of having GG+G (and b ≥ 2). Then 1 red block must be inserted between the GG pair, to give GRG. (In fact we must have the sequence BGRGB). The remaining blue blocks and green block complete the ring. The remaining G must be outside the BGRGB sequence, and the remaining r-1 reds must be outside the GRG sequence. Before the extra reds are added, the G could be in any of b-1 locations (a sketch will confirm that). Then the reds can be fitted into any one of b+2 locations (again a sketch will confirm that’s right – bear in mind that the green block now behaves as a blue block). So there are C(b+2,r-1) distinct ways of fitting the remaining r-1 reds. Then the whole pattern can be rotated through (b+r+3) orientations. Altogether that gives (b-1) C(b+2,r-1) (b+r+3) combinations.

Case of G+G+G and b ≥ 3. Consider one of the blue blocks to be fixed. With b blue blocks we have b possible insertion points for the green blocks, and so there are C(b,3) ways in which we could have inserted them. For each of those ways we now have b+3 possible insertion points for the red blocks, and so may fit the red blocks in C(b+3,r) ways. Include the rotation factor to get C(b,3)C(b+3,r)(b+r+3)/b

Altogether, over the three cases we have, for b ≥ 3 and r ≥ 3, that the number of combinations is:

C(b+1,r-2)(b+r+3) + (b-1) C(b+2,r-1) (b+r+3) + C(b,3)C(b+3,r)(b+r+3)/b

= (b+r+3)(C(b+1,r-2) + (b-1)C(b+3,r-1) + C(b,3)C(b+3,r)/b)

unique ways of combining.