Here is the link to the problem being discussed here. Everyone must read this, to understand starkly different ways of thinking about the same problem.
The problem has 8 tiles in a row, and 2 colors to paint, yellow and black. You need to find the number of ways in which the tiles can be painted so that no two adjacent tiles have the color black.
To make things clearer, you can check out the examples of different cases on the problem page.
Many readers have responded by submission form, Email, Messages and comments. Here, I am sharing the different approaches and ways of thinking about the problem.
Many different approaches have come up, with multiple ways of thinking within them as well.
- Let’s just count : As you begin to count, you see numerous patterns.
- Let’s explore: Play and Exploration are essential to Mathematics. That leads to discovery
- Let’s assume (Thinking recursively): What if we knew the answer to the problem with lesser number of tiles?
- A really unique approach shared by Chi Woo in the comments here on LinkedIn! I will try to post it here more visually and in a way accessible to everyone. But it’s a brilliant idea.
Approach 1: Lets just count!
Don’t miss out the big challenge at the end of this approach!
We can start by thinking the number of black tiles we can have. So, we can have 0, 1, 2, 3 or 4 black tiles. We can’t possibly have more than 4 black tiles. (but Why? Can you try give a clear explanation to this in the comments?) Now there can be different ways of counting.
Draw and count
On a leisurely Sunday morning, you could print strips of square tiles, and paint them. Just take this image and print multiple copies of this, paint them keeping the restriction in mind, and count how many unique combinations you could manage.
As you paint, you might actually discover some amazing patterns and see how beautiful Math looks with colors.
Reasoning (Counting forward)
Again, we count here, but in a slightly structured way, and try to observe a pattern or an underlying principle which makes the counting easier.
If there are 0 black tiles:
There is just 1 way, which is to paint all the tiles yellow.
If there is 1 black tile:
There are 8 ways, with black occupying a different tile each time and the remaining 7 tiles are colored yellow.
If there are 2 black tiles:
There can be many possible ways of doing this. Ok, so how are we going to count this? Lets label the tiles from 1 to 8.
Now, let’s list down the places which the black tiles can occupy, without being in any adjacent tiles.
(1,3), (1,4), (1,5), (1,6), (1,7), (1,8);
(2,4), (2,5), (2,6), (2,7), (2,8);
(3,5), (3,6), (3,7), (3,8);
(4,6), (4,7),(4,8);
(5,7), (5,8);
(6,8)
Number of ways :
6+5+4+3+2+1 = 21
If there are 3 black tiles:
Again, lets try to list down and observe the pattern which you see in the number of ways. Try to answer why do you see that pattern in counting.
Starting with the 1st tile:
(1,3,5), (1,3,6), (1,3,7), (1,3,8);
(1,4,6), (1,4,7), (1,4,8);
(1,5,7), (1,5,8);
(1,6,8)
Number of ways :
4+3+2+1 = 10
Starting with the 2nd tile:
(2,4,6), (2,4,7), (2,4,8);
(2,5,7), (2,5,8);
(2,6,8)
Number of ways:
3+2+1 = 6
Starting with the 3rd tile:
If you observe carefully what’s happening above, you will be able to conclude that the total number of cases here will be (2+1) = 3.
Starting with the 4th tile:
There will be just 1 case here.
So, the total number of cases with 3 black tiles are (10 + 6 + 3 + 1) = 20 cases. (Note the interesting pattern occurring here. Do you see the reason?)
If there are 4 black tiles:
Try this on your own :). You should be getting 5 different cases here.
So, altogether, we get (1+8+21+20+ 5) = 55 cases.
The Big Challenge: Using the above approach and the patterns observed here, find the numbers of ways of painting if there were 10 tiles? Can you generalise it.
Subtractive counting
Another way to think about various cases could be to consider the total number of ways of coloring 8 tiles and then subtracting the cases where blacks occur together. You should try this approach and can proceed as we did above. (Starting with 0,1,2,3,4 black tiles)
Approach 2 : Play and Experimentation
One of my students started by wondering!
What if there are just 1 tile?
There would be 2 ways to paint it.
What if there were 2 tiles?
There are 3 ways to paint them.
What if there were 3 tiles?
As you see below, there are 5 ways to paint them.
What if there were 4 tiles?
If you try this. you will see that there are 8 ways to achieve this.
As she kept on doing this, she listed the number of ways and tried to see if there was a pattern.
2, 3, 5, 8, 13 ….. Do you see here what she saw?
2+3 =5 , 3 +5 = 8, 5 + 8 =13
From the 3rd term onwards, each term is the sum of the previous 2 terms. She had discovered the famous Fibonacci Sequence. But does this pattern continue here? Can we be sure it works for 8 tiles, or 15 tiles or even if there were 100 tiles?
We can’t be sure until we are able to explain it with a proper reason, and that would lead us to our next approach. But this is a really nice way to start thinking about a problem, by making it simpler and smaller.
Approach 3: Thinking recursively
This is a completely different way of thinking about the problem, as compared to direct counting.
We have 8 tiles. The last tile can be yellow or black.
Case 1: The last tile is painted yellow.
Since the 8th tile is painted yellow, there is no restriction on the color of the 7th tile (due to the 8th tile). So, all the valid cases for coloring the 1st 7 tiles would be valid here too, with 8th tile taking the color yellow. Let the number of these cases be f(7).
Case 2: The last tile is painted black.
Since the 8th tile is black, the 7th tile has to be yellow. So the 7th and 8th tile are fixed, with no restriction on arrangements of the 1st 6 tiles, as long as they fulfil the condition. So, all the valid cases for coloring the 1st 6 tiles would be valid here too, with the 8th tiles taking the color black. Let the number of these cases be f(7).
Since there are no overlaps in case 1 and case 2, we can say:
No. of ways of coloring 8 tiles = Ways to color 6 tiles + Ways to color 7 tiles.
f(8) = f(6) + f(7)
By a similar argument, this can be generalised to say f(n) = f(n-1) + f(n-2), where f(n) is the number of valid ways of coloring n tiles.
Since in Approach 2, we already saw that f(1) = 2, f(2) = 3, we can easily find the number of ways for any number of tiles.
Post in the comments section if you find that there’s another way to think about this problem. Or what could be the possible variations to this problem. You can also try this problem where you need to represent any number as sum of 1’s and 2’s.
Note to parents and teachers: This problem is suitable for all ages 10+. We need to introduce children to problems that make them think, and dive into ideas. You just need to be comfortable with them exploring, experimenting, struggling and trying different approaches. Contact us if you need resources for this task for your classroom or home.
This approach is more elegant!
[…] Many readers have responded via Email and Messages. The starkly different approaches and ways of thinking have been discussed […]