0
$\begingroup$

Problem where i was encountered was this :

A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap.

Each tile may cover any number of consecutive squares, and each tile lies completely on the board.

Each tile is either red, blue, or green.

Let $N$ be the number of tilings of the $7 \times 1$ board in which all three colors are used at least once.

For example, a $1 \times 1$ red tile followed by a $2 \times 1$ green tile, a $1 \times 1$ green tile, a $2 \times 1$ blue tile, and a $1 \times 1$ green tile is a valid tiling.

Note that if the $2 \times 1$ blue tile is replaced by two $1 \times 1$ blue tiles, this results in a different tiling.

What i did was cases made for total number of tiles:

like for 3 tiles by doing $x_1$+ $x_2$+$x_3$= 7 , where $x_1$,$x_2$,$x_3$ represents lengths of each tile , which should some up to 7 and then multiply by 3! For 3 colours from this method for cases more than 3 tiles ,

i seems like counting wrong always, like for example for 5 tiles i did first $x_1$+...$x_5$ = 7 this tells the number of tiles combinations possible to be 6C4 , and now the tiles can be of two types (1,1,3) ,(1,2,2) , where each represents the colour combinations from three colours .

Now for first type its like choosing 1 , then another 1 ,then 3 so its this: 5C1 * 4C1 * 3C3 and then 3! Mulitpilcation For three colours , similairy next type it would be 5C1 * 4C2 * 2C2 * 3! .

But ik i am making some couting mistake like i need to do some number division or multiplicatiom here which leads to correct answer for every case. Can anyone tell whats wrong in this case of 5 tiles ?

$\endgroup$
2
  • $\begingroup$ To get subscripts, use an underscore. $x_1$ gives $x_1$. $\endgroup$ – saulspatz Mar 18 at 13:32
  • $\begingroup$ Yeah i have done the editing Sir $\endgroup$ – user900638 Mar 18 at 13:38
1
$\begingroup$

You've over-counted by a factor of $2$ at the end. You shouldn't be multiplying by $3!$ but by $3$. When you assign colors in the pattern $(1,1,3)$, for example, you only need to decide which color occurs $3$ times; after that there's no choice. In the pattern $(2,2,1)$, you only need to decide which color occurs once.

Another way to do this part of the problem is inclusion-exclusion. There are $3^5$ ways to color $5$ tiles with $3$ colors. We must subtract the ways that only use $2$ colors, so we have $3^5-3\cdot2^5$. Now what about a coloring with one color? It's been counted once originally, and subtracted twice, since one of the two-colorings doesn't include it, so we need to add it back in. This gives a final answer of $$3^5-2\cdot2^5+3=150$$ Note that this is the same as $$\binom51\binom41\cdot3+\binom51\binom42\cdot3=150$$

$\endgroup$
5
  • $\begingroup$ Sir tbh i got the PIE approach but still didnt get the 3 not 3! thing , reason being we r also arranging the tiles too , so shouldnt the other two can change their arrangements ? Hence 3 * 2 * 1? Like RBGGG , BRGGG r different isnt (setup of tiles in that 7 * 1 board)? $\endgroup$ – user900638 Mar 18 at 14:38
  • 1
    $\begingroup$ Yes, those colorings are different, but you've taken care of that in the first part of the calculation. Suppose we have $1$ red, $1$ blue, $3$ green. When you calculate $\binom51\binom41\binom33$, you're saying, "Choose a tile to color red, then a tile to color blue, then color the others green." We don't want to also say, "Choose a tile to color blue, then a tile to color red, etc." Personally, I find inclusion-exclusion much less error-prone for problems like this. $\endgroup$ – saulspatz Mar 18 at 14:46
  • $\begingroup$ Oo i now see so by saying the second thing of Choose a tile to color blue, then a tile to color red," we r actually doubling the counting right Sir ? And for which specific type of problems u meant to use PIE better than other ways like case bash , graph etc. $\endgroup$ – user900638 Mar 18 at 14:53
  • 1
    $\begingroup$ Yes, that's right. I can't be very specific about when I like PIE, but I guess it's in problems like this where we have multiple stages of counting, and it's easy to make mistakes in how they interrelate. When I find myself getting confused, I try to fall back on PIE. In this case, I immediately thought you were overcounting by a factor of $2$, but I wasn't really sure till I confirmed it with PIE. Full disclosure: even then, I checked it again with a python script that constructed all colorings of five tiles. $\endgroup$ – saulspatz Mar 18 at 15:03
  • $\begingroup$ Thx a lot Sir got your pt :) , thx for this great help 🙂 $\endgroup$ – user900638 Mar 18 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy