Bob is painting his tiles, and he plans to color each tile with one of 6 different colors. He paints a group of 12 tiles randomly (true random), and notices that no more than 3 distinct colors showed up on the tiles, out of the possible 6. The probability that this scenario occurs can be expressed as a/b, for coprime a and b. Enter your answer as a+b.
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.
Interesting! Wouldn't that give the total number of distinct arrangements though? I initially guessed that 6 1 2 would result in the total number of possibilities when order matters.
Log in to reply
That is actually true but because order does not matter, there are a lot of different possibilities that should be disregarded. Yes it would give the number of arrangements in one step. If you want to use the arrangements formula, you need to divide into cases... (e.g 1 color appears, 2 colors appear, 3 colors...)
Log in to reply
So I have one question that has been nagging me. If we count only the distinct arrangements (where order does not matter), wouldn't the different cases be weighted differently with regards to probability?
For instance, an outcome of 12 blues is way more rare than an outcome of 4 blue, 4 red, and 4 yellow, or for that matter, two of each color (which is the most probable outcome). So I am wondering where your solution takes the different weightings into account.
First we note that the probability depends largely on the first three tiles. I will split the problem into 3:
1) The first three tiles are different colors
2) Two of the first three are the same color and
3) All three of the first are the same color.
For the first case, note that tiles 4 – 12 all must be colored with just the colors that showed up on the first 3 tiles. Since there are 6 possibilities, each tile has a 50% chance of being the correct color. So tiles 4 – 12 bring in a factor of ( 2 1 ) 9 . The probability that the first 3 tiles have distinct colorings is 1 ∗ 6 5 ∗ 6 4 = 9 5 . So the probability for case 1 is 9 5 ∗ ( 2 1 ) 9 .
For the second case, it is more complicated. The probability that the first 3 tiles have 2 distinct colorings is 1 2 5 . Now I will define P ( 2 , n ) as the probability that a set of tiles end up with no more than 3 colors on them. The parameter 2 indicates that we have found a total of 2 distinct colors in the tiles that we have examined, and the parameter n indicates the number of tiles we have left to examine. For case 2), we are after P ( 2 , 9 ) .
It turns out that P ( 2 , n ) can best be defined iteratively. If we have n tiles left to examine, we know that 3 2 of the time the tile will be a different color than the original two colors, and that 3 1 of the time it will be the same. If it is different, then all three colors have been determined, and each of the later tiles must be one of those 3 colors. Like in part 1), this introduces a factor of ( 2 1 ) n − 1 . But the one third of the time that the tile happens to be the same color as one the two already defined colors, we are left with n − 1 spots to check and still the same two colors, which we recognize as P ( 2 , n − 1 ) . So the iterative equation is:
P ( 2 , n ) = 3 2 ∗ ( 2 1 ) n − 1 + 3 1 ∗ P ( 2 , n − 1 ) .
Since P ( 2 , 1 ) = 1 , we can make a table of results. We have:
P ( 2 , 1 ) = 1 P ( 2 , 2 ) = 3 2 P ( 2 , 3 ) = 1 8 7 P ( 2 , 4 ) = 1 0 8 2 3 P ( 2 , 5 ) = 6 4 8 7 3 P ( 2 , 6 ) = 3 8 8 8 2 2 7 P ( 2 , 7 ) = 2 3 3 2 8 6 9 7 P ( 2 , 8 ) = 1 3 9 9 6 8 2 1 2 3 , and P ( 2 , 9 ) = 8 3 9 8 0 8 6 4 3 3
So we have P ( 2 , 9 ) , but in fact, we will need all of those other P ( 2 , n ) as well.
For the last case, we can again define an iterative equation for P ( 1 , n ) . The parameter 1 indicates that there has only been one color on the tiles we have examined. Here is the equation:
P ( 1 , n ) = 6 5 ∗ P ( 2 , n − 1 ) + 6 1 ∗ P ( 1 , n − 1 ) .
This states the probability for the two cases that the next tile is a different color ( 6 5 of the time), and the probability for the case that the tile is the same color. Again, we can make a table of values, after noticing that P ( 1 , 2 ) is 1. I will just give P ( 1 , 9 ) = 5 0 3 8 8 4 8 1 5 7 6 3 for brevity.
After summing up 9 5 ∗ 2 1 9 + 1 2 5 ∗ P ( 2 , 9 ) + 3 6 1 ∗ P ( 1 , 9 ) , we get
P = 3 0 2 3 3 0 8 8 1 4 5 0 6 3
P.S. While writing the solution, I realized that P ( 1 , 1 1 ) should be equal to the total probability, since it takes all of the cases into consideration. Sure enough, P ( 1 , 1 1 ) = 3 0 2 3 3 0 8 8 1 4 5 0 6 3
Problem Loading...
Note Loading...
Set Loading...
Let x i denote the number of times that the color i appears in the set of 12 tiles where i is between 1 and 6 .
First, we will look for the total number of possibilities. We can easily observe that the total number of possibilities is the number of solutions of the equation: ∑ i = 1 6 x i = 1 2 and x i is between 0 and 1 2 . It turns out that the number of solutions that satisfy this eqution is: ( 1 2 1 7 ) .
In case you are wondering where I got the 1 7 choose 1 2 from, It comes from the generalized form ∑ i = 1 n x i = m having ( n n + m − 1 ) solutions. (You can prove this claim using strong induction on m ).
Now since we want at most 3 colors to show up, we can divide it to three cases where exactly 1 , 2 , then 3 .
Case 1 : Exactly 1 color appears. This obviously happens in 6 ways.
Case 2 : Exactly 2 colors appear. This is equivalent to x i + x j = 1 2 . The number of solutions is ( 2 1 3 ) . However this number includes the case where one of the colors is 0 and the other is 1 2 , which means that we are double counting some solutions in case 1. So the number of solutions for only 1 pair is ( 1 2 1 3 ) − 2 and because we have 15 possible pairs, the total number of ways in which EXACTLY 2 colors show up is 1 5 ( 1 2 1 3 ) − 3 0 = 1 6 5
Case 3 : Exactly 3 colors. Just like how we did for case 2, we look for the number f solutions of the equation ∑ i = 1 3 x i = 1 2 , which is b i n o m 1 4 3 . Once again we do not want any x i ′ s to equal zero because that would double count the previous cases. Here I will do something something