2
$\begingroup$

Hints only please!

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. Find the remainder when $N$ is divided by $1000$.

Hints only please!

It is a very tricky problem, but here is what I am thinking, let $RGB$ denote the obvious colors. We must have $R + G + B = 7, R,G,B \ge 1$.

The number of solutions for this is: $\binom{6}{2} = 15$. But this doesnt seem a good idea to use, because of the grouping issue.

I could try casework but the problem is extremely complicated for that.

I would just like some hints.

$\endgroup$
2
  • $\begingroup$ Do you know how to do this when there is no restriction that all three colors are used? Do you know how to do this when the tiles are limited in size? Do you know how to do this when all tiles are the same color? $\endgroup$
    – Erick Wong
    Aug 1 '15 at 19:18
  • $\begingroup$ @ErickWong, Perhaps. When no restriction all three are used then: $(3^7 + 3^6 + 3^5 + 3^4 + 3^3 + 3^2 + 3) = 3279$ ? $\endgroup$
    – Amad27
    Aug 1 '15 at 19:30
3
$\begingroup$

Here is another approach.

Let $c(n,r)$ be the number of ways of filling an $n\times 1$ block with tiles using precisely $r$ colours.

Then $c(n+1,r)=c(n,r)+rc(n,r)+rc(n,r-1)$ where the configuration is extended to the right. The first term corresponds to extending the final block of a configuration of length $n$ so it is one unit longer. The second term involves adding a one-unit block of any colour to the right-hand end. The third term corresponds to adding a one unit block of the missing colour to a length $n$ configuration of precisely $r-1$ colours.

You can easily see that removing the right-hand cell of an $n+1$ configuration with $r$ colours gives one of these possibilities.

Here $c(7,3)=4c(6,3)+3c(6,2)$

And $c(6,2)=3c(5,2)+2c(5,1)$

And $c(5,1)=2c(4,1)$ because there are no ways of doing this with no colours.

So the recurrence enables you to compute the answer. And you can reduce modulo $1000$ as you go.

$\endgroup$
9
  • $\begingroup$ (+1), I got the recurrence that without restrictions there are: $F(n) = 4F(n-1)$ since: $F(n) = 3[F(n-1) + F(n-2) + ... F(n-7)]$ and $F(n-1) = 3[F(n-2) + F(n-3) + .. + F(n-8)]$. But since there are only $7$ terms, the last term $F(n-8)$ is eliminated. So: $F(n) = 4F(n-1)$. But this is without restrictions, now I am trying to find the complement so how many arrangements with just $1$ color and $2$ colors. for just one color it is $3$ Thus far (If $X(n)$ is the desired) we have: $X(7) = 4F(7) - 3 - G(7)$ whee $G(n)$ is the $n-$lettered sequence with two colors. $\endgroup$
    – Amad27
    Aug 1 '15 at 21:09
  • $\begingroup$ I realized that consider just the combination $RB$ (multiply by $3$ after since $RB, RG, BG$ are all valid (and have the exact same "number of options."). We could have cases: $R, \overline{RR}, \overline{RRR}, \overline{RRRR}, \overline{RRRRR}$ and same for $B$ so let $R(n) = B(n)$ ($R(n)$ begins with $R$). Suppose we start: $RBRRRRR, RBBRRRR, RBBBRRR, RBBBBRR, RBBBBBR, RBBBBBB$ we have: $\binom{6}{1} + \binom{6}{2} + .. + \binom{6}{6} = 6 + 15 + 20 + 15 + 6 + 1 = 63$. Then: $\overline{RR}BRRRR, \overline{RR}BBRRR, \overline{RR}BBBRR, \overline{RR}BBBBR, \overline{RR}BBBBB$ $\endgroup$
    – Amad27
    Aug 1 '15 at 21:24
  • $\begingroup$ Scratch this. This method doesnt work, what should I do? $\endgroup$
    – Amad27
    Aug 1 '15 at 21:26
  • $\begingroup$ Note that for any arrangement with $r$ colours there should be a factor of $r!$ representing the different arrangements of the colours. I get first $c(1,1)=1, c(2,1)=2, c(3,1)=4, c(4,1)=8$ etc and then $c(1,2)=0, c(2,2)=2, c(3,2)=10, c(4,2)=38$ and $c(3,3)=6, c(4,3)=54, c(5,3)=330$ etc $\endgroup$ Aug 2 '15 at 1:06
  • $\begingroup$ The reason this problem is hard because $2\times 1$ blue isnt the same as two $1\times 1$ blue. $\endgroup$
    – Amad27
    Aug 2 '15 at 11:18
3
$\begingroup$

There are six possible places to put a divider between tiles. If there are no dividers there is one tile and you can't have all three colours. If there is one divider there are two tiles and there cannot be three colours.

If there are two dividers, then there are three tiles. There are $\binom 62$ ways of placing the dividers, and six ways of painting the tiles using all three colours.

If there are three dividers there are four tiles and this is $\binom 63$ possibilities. Then you have to find the number of ways of painting these using all three colours. This is best done by inclusion/exclusion. There are $3^4$ ways of painting them using three colours without restriction. and $3\times 2^4$ ways of painting them with two colours (choose the colours, then do the painting) but you have to take care then about the counting of the arrangements with one colour - which I'll leave you to work out. Once you have done it, the cases for four to six dividers are easy to do similarly.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.