Barcode

For this question, I understand the first half of this solution,
but for the second half, I would just like to reword the points the way I understand (from "Now that we have all possible cases we can use nCr..") so someone can check I havent made any mistakes (q + ans posted in below post).

1. We are not considering colour of each strip as the "colour info" is already represented by the top equations (ie: a = even, b=odd and 2a+b=12)
2. for (10,1) since there are 10 little strips and 1 big strip, the big strip can go in the front, second, third....... last so there are 11 gaps for it, so its 11 possible options.
3. for (6,3) and (2,5), there are 9 and 7 gaps respectively by the same logic, but since the order of each big strip doesnt matter, ie: if the big strips are (b1,b2,b3) then the case of b1,b2,b3 is the same as b3,b2,b1 etc. and there are 6 ways to arrange the big strip like this, so we use a combination rather than a permutation.

Thank you to anyone willing to clarify anything.

(edited 1 year ago)

Reply 1

mosaurlodon

q and a:

Reply 2

mqb2766

Original post by mosaurlodon

For this question, I understand the first half of this solution,
but for the second half, I would just like to reword the points the way I understand (from "Now that we have all possible cases we can use nCr..") so someone can check I havent made any mistakes (q + ans posted in below post).
1. We are not considering colour of each strip as the "colour info" is already represented by the top equations (ie: a = even, b=odd and 2a+b=12)
2. for (10,1) since there are 10 little strips and 1 big strip, the big strip can go in the front, second, third....... last so there are 11 gaps for it, so its 11 possible options.
3. for (6,3) and (2,5), there are 9 and 7 gaps respectively by the same logic, but since the order of each big strip doesnt matter, ie: if the big strips are (b1,b2,b3) then the case of b1,b2,b3 is the same as b3,b2,b1 etc. and there are 6 ways to arrange the big strip like this, so we use a combination rather than a permutation.
Thank you to anyone willing to clarify anything.

•

The colour has to go black-white-black-white-black (or something like that). They have to alternate and its really the width of the strips that gives the different combinations

•

The two spaces could occur in 11 different places starting at column 1 (black), then column 2 (white), then column 3 (black), ... up to column 11. So 11C1

•

For (6,3), we could consider it as a choice of 3 single bars out of 9 (as 12-3=9 and pretend the double bars are single bars). Similarly for (2,5) is a choice of 5 from 7 which is the same as 2 from 7.

Reply 3

mqb2766

Original post by mosaurlodon

For this question, I understand the first half of this solution,
but for the second half, I would just like to reword the points the way I understand (from "Now that we have all possible cases we can use nCr..") so someone can check I havent made any mistakes (q + ans posted in below post).
1. We are not considering colour of each strip as the "colour info" is already represented by the top equations (ie: a = even, b=odd and 2a+b=12)
2. for (10,1) since there are 10 little strips and 1 big strip, the big strip can go in the front, second, third....... last so there are 11 gaps for it, so its 11 possible options.
3. for (6,3) and (2,5), there are 9 and 7 gaps respectively by the same logic, but since the order of each big strip doesnt matter, ie: if the big strips are (b1,b2,b3) then the case of b1,b2,b3 is the same as b3,b2,b1 etc. and there are 6 ways to arrange the big strip like this, so we use a combination rather than a permutation.
Thank you to anyone willing to clarify anything.

An alternative way to approach the question would be a fibonacci / inductive / recursive way. So imagine the number of all sequences of length n which
a) start and end with black - B(n)
b) start with black and end with white - W(n)
after youve got the first couple of values for n=1,2, its relatively easy to argue that
B(n) = W(n-1)+W(n-2)
W(n) = B(n-1)+B(n-2)
and simply iterate through n up to 12.

Edit - Other "similar" fibonacci puzzles
https://r-knott.surrey.ac.uk/Fibonacci/fibpuzzles.html
https://r-knott.surrey.ac.uk/Fibonacci/fibpuzzles2.html

(edited 1 year ago)

Reply 4

mosaurlodon

tbh, I havent really covered recursive sequences yet (as you can prob tell from the below), is it covered in edexcel maths/fm?

I have a couple of qs about this

is length n the "width" as expressed by the question or is it the number of alternate colours?

I may be completely misunderstanding - but i dont really get how B(n) and W(n) work - since the q says "start and end with black" isnt it always just B(n)?

but anyways heres my go (assuming n is the width):
B(1) = 1 (since one black means the start and end is black) and W(1) = 0 (since the start is black but theres no white).
B(2) = 1 (BB is only option) and W(2) = 1 (BW is only option)
B(3) = 1 (BWB is only option) and W(3) = 2 (BBW or BWW)
I get your equations? (I think)?

but im pretty sure this is wrong/im misunderstanding because I cant really see how this can be applied to the problem.

(edited 1 year ago)

Reply 5

mqb2766

Original post by mosaurlodon

tbh, I havent really covered recursive sequences yet (as you can prob tell from the below), is it covered in edexcel maths/fm?
I have a couple of qs about this

is length n the "width" as expressed by the question or is it the number of alternate colours?

I may be completely misunderstanding - but i dont really get how B(n) and W(n) work - since the q says "start and end with black" isnt it always just B(n)?

but anyways heres my go (assuming n is the width):
B(1) = 1 (since one black means the start and end is black) and W(1) = 0 (since the start is black but theres no white).
B(2) = 1 (BB is only option) and W(2) = 1 (BW is only option)
B(3) = 1 (BWB is only option) and W(3) = 2 (BBW or BWW)
I get your equations? (I think)?
but im pretty sure this is wrong/im misunderstanding because I cant really see how this can be applied to the problem.

Its really just fibonacci which you should have met, even if youve not really done recursive/difference equations. The basic idea is that to get B(n) so the sequences of length n and starting and ending with black you can

•

add a black strip width 1 to the end of W(n-1) sequences

•

add a black strip width 2 to the end of W(n-2) sequences

and thats it, so B(n) = W(n-1)+W(n-2). Similarly you add white strips to sequences ending in black so W(n) = B(n-1)+B(n-2)

Then B(1)=1, B(2)=1 and W(1)=0, W(2)=1 and keep iterating for n=3,4,5....12 to get B(12) which is what you want.

Reply 6

mosaurlodon

ohhhh that makes so much sense because the number of black cases B(n) only depends on the previous number of white cases W(n) before the final black strip and vice versa.

that is an awesome solution I didnt even know you could do maths like that

Thank you for that :smile:

Reply 7

mqb2766

Original post by mosaurlodon

ohhhh that makes so much sense because the number of black cases B(n) only depends on the previous number of white cases W(n) before the final black strip and vice versa.
that is an awesome solution I didnt even know you could do maths like that
Thank you for that :smile:

It may even be what the problem setter had in mind as the original fibonacci problem was rabbits breeding every month and the aim was to get the number at the end of the year so n=12.
https://en.wikipedia.org/wiki/Fibonacci_sequence
and its a relatively elementary way to get B(12) if you think about it inductively/recursively, so start small and whats the rule for generating larger solutions.

Reply 8

mqb2766

Original post by mosaurlodon

ohhhh that makes so much sense because the number of black cases B(n) only depends on the previous number of white cases W(n) before the final black strip and vice versa.
that is an awesome solution I didnt even know you could do maths like that
Thank you for that :smile:

A similar way to the above (different reasoning but "same" equation) would be to note that the problem would be the same flipping black and white (so start and finish with white, ignoring the obvious visual difficulty). Then
B(n) = B(n-2) + 2B(n-3) + B(n-4)
as, for example, you can get B(12) from

•

a flipped B(10) and add black strips of width 1 at the start and end

•

a flipped B(8) and add black stripts of width 2 at the start and end

•

a flipped B(9) and add black strips of width 1 and 2 at the start/end and end/start.

If you eliminated W from the B equation in the previous post, youd get this relationship. Obviously you need 4 starting values for B, so while it doesnt involve W its pretty much the same complexity, just a different way of thinking about how to get the equation.

Reply 9

DFranklin

Original post by mosaurlodon

ohhhh that makes so much sense because the number of black cases B(n) only depends on the previous number of white cases W(n) before the final black strip and vice versa.
that is an awesome solution I didnt even know you could do maths like that
Thank you for that :smile:

To take things a little further, suppose you define a sequence of vectors

V_n = (B_n, W_n, B_{n-1}, W_{n-1})

. Then we can write V_{n+1} in terms of V_n, and in fact we can find a 4x4 matrix A with AV_n= V_{n+1}.

But then it's easy to see V_n = A^(n-2) V_2.

Where this gets interesting is that you can find A^1024 by simply squaring A 10 times. So you can find the nth term with k log_2(n) operations.

This trick is sometimes actually useful.

(edited 1 year ago)

Quick Reply

Related discussions

Latest

Trending

Try out the app

Continue on web