I don't want 1 0 1 and 1 1 1 .
Let
a
n
be the number of words of
0
−
1
strings of length
n
such that neither
1
0
1
nor
1
1
1
occur as 3-digit blocks. Find
a
1
6
.
Note: This is an old IMO problem.
The answer is 3025.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Great solution! But what if I'm colorblind? :)
See that the recurrence relation will be
a n = a n − 1 + a n − 3 + a n − 4 a 0 = 1 , a 1 = 2 , a 3 = 6
Then see that the Generating, G ( x ) = 1 − x − x 3 − x 4 1 + x + 2 x 2 + x 3
Then,decompose by method of partial fractions and see that G ( x ) = 5 1 ( 1 − x − x 2 7 + 4 x − 1 + x 2 2 + x )
The generating function for Fibonacci numbers is 1 − x − x 2 x .
Using this see that the co-efficient a n of x n is
5 7 F n + 1 + 4 F n − 2 ( − 1 ) n / 2 when n is even
5 7 F n + 1 + 4 F n − ( − 1 ) ( n − 1 ) / 2 when n is odd.
One may see that 7 F n + 1 + 4 F n = F n + 5 + F n + 3
One can use wolfram alpha to calculate the Fibonacci numbers.
There may be other types of solutions(without using generating function method).
I think the numeric answer for the checker does not match your answer. I got 3 0 2 5 for a 1 6 from my method (using matrices) and from plugging in n = 1 6 into your equation for even n .
Log in to reply
I believe that @Souryajit Roy 's mistake was that he forgot the divide out by 5. I've updated the answer to 3025.
To type equations in Latex, you just need to add \ ( \ ) (no space) around your math code. I've edited your comment so that you can refer to it
Log in to reply
Ok, thanks! :)
I am very sorry for the wrong ans...i just forgot to divide 15125 by 5
(And the answer from the checker is 15125)
3025 is the correct answer which can be reached simply by recursion. At n=16 the break-up of strings ending with 00 is 1156, 01/10 is 714, and 11 is 441. Answer is 1156 + 714 + 714 + 441 = 3025.
Will someone please explain Roy's method of generating functions? How did he deduct G(x) from the original recurrence relation? I arrived at 3025 using the same recursion but had to go through a morass of arithmetic.
Log in to reply
Let G ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + a 4 x 4 + . . . . . . . . .
Hence, G ( x ) ( 1 − x − x 3 − x 4 ) = a 0 + ( a 1 − a 0 ) x + ( a 2 − a 1 ) x 2 + ( a 3 − a 2 − a 0 ) x 3 = 1 + x + 2 x 2 + x 3
Can you include an explanation of how the recurrence relation arises?
Log in to reply
Consider a n- string.
Case 1.1 is the first place.
If I place 1 after 1, then I must place 0 in the third place and again 0 in the 4th place.So there will be a n − 4 ways.
If I place 0 after 1, then I must place 0 in the third place also and then there will be a n − 3 ways.
Case 2. If 0 is in the first place, then there are a n − 1 ways.
But a4=8, against the recursion
Same way as I did, but I used matrices:
\mathfrak{A_{n}}=\left[\array{a_{n} \\a_{n-1}\\ a_{n-2}\\a_{n-3}}\right]=\left[\array{a_{n-1} +a_{n-3}+a_{n-4}\\a_{n-1}\\ a_{n-2}\\a_{n-3}}\right]=\left(\array{1&0&1&1\\1&0&0&0\\0&1&0&0\\0&0&1&0}\right)\left[\array{a_{n-1}\\a_{n-2}\\a_{n-3}\\a_{n-4}}\right]=M\mathfrak{A_{n-1}}
Therefore:
A n = M n A 0 A 1 6 = M 1 6 A 0 = M 1 2 A 4
Now you calculate M 1 2 , by using that M 1 2 = ( M 6 ) 2 , M 6 = ( M 3 ) 2 and M 3 = M M 2
Color the 16 positions alternately green and red. A string will fail if you get two consecutive ONES of the same color. Then, you need to fill 8 green spaces with 1 and 0 so you don't get consecutive ones. That's known to be the 10th fibonacci number = 55.
Likewise you get 55 ways to fill the red positions.
Therefore you get 5 5 2 ways to choose the 16 numbers