0

This is the question:

We have unlimited floor tiles in the colors red or blue. Every color comes in the size of $1\times 1$ or $1 \times 2.$

In how many ways we can tile a rectangle with size of $1\times 10$ without two adjacent red floor tiles? What is the recursion formula for that problem and that are the start conditions?

I have tried to think about a solution like this:

  • for rectangle size of $1 \times 1$ we have $2$ options: red or blue $1 \times 1$ floor tile

  • for rectangle size of $1\times 2$ we have $3$ options: red & blue $1 \times 1,$ $2$ blue $1 \times 1$ or $1$ blue $1 \times 2$

But later then I got stucked with comming up with a solution to Typical Polynomym

RobPratt
  • 45,619
Omri Braha
  • 109
  • I have edited my question and also changed triangle to rectangle... more so, the phrase "two adjacent red floor tiles" signify a condition that says: you can not place two red tiles one next to each other – Omri Braha Sep 26 '20 at 12:10
  • Exactly [ | | | | | | | | | ] like this - you can place in blank spaces floor tiles in the size and color above – Omri Braha Sep 26 '20 at 12:16
  • It seems to me that the thing to do is solve the problem (manually, counting by hand, with no attempt at elegance) when the row is 3 tiles long. Then see what happens if the row is 4 tiles long, then 5 tiles long. I would say at this point it is time to stop the manual work, look for a pattern re each row, form a hypothesis, and then try to prove a hypothesis. If you do this, and show your work, you will probably get a positive response from mathSE. – user2661923 Sep 26 '20 at 12:19
  • Two other suggestions: (1) This problem is similar to the Stars and Bars problem discussed at https://brilliant.org/wiki/integer-equations-star-and-bars/. Frankly, because you have a variable number of red tiles to use, and because you can use either $1x1$ blue tiles or $1x2$ blue tiles, and because we are only talking about a row of size 10, I'm not sure if this website is worth your exploring for this problem. ...see next comment – user2661923 Sep 26 '20 at 12:33
  • (2) In accordance with my earlier comment about manual exploration through row length = 5, I would consider for a given row length of either $2k$ or $(2k+1)$, breaking the exploration up into $(k+1)$ cases, where for $r ~\in ~{0,1,2,\cdots, k}$, your row contains exactly $r$ 1x2 tiles. Also, with respect to recursion, I would consider trying to recurse between $n$ and $(n+2)$, rather than between $n$ and $(n+1).$ – user2661923 Sep 26 '20 at 12:36
  • Also, however you recurse, [i.e. between $n$ and $(n+1)$ or between $n$ and $(n+2)$] you might consider attempting to break the current row tiling into 2 cases : case (A): rightmost tile is red, case (B): rightmost tile is blue. – user2661923 Sep 26 '20 at 12:43
  • I answered a similar problem here. You should be able to use coupled recurrences-how many ways to make a rectangle of length $n$ that ends in red and how many that end in blue. – Ross Millikan Sep 26 '20 at 14:04

1 Answers1

1

Notation: $R(1,1)$ is a $1\times 1$ red tile, $R(1,2)$ is a $1\times 2$ red tile and so on.

There are two reasons for which the question seems awkward.

  1. What does how many ways mean? More precisely, when tiling a $1\times 2$ rectangle, $R(1,1)+B(1,1)$ is the same as $B(1,1)+R(1,1)$? Looking at your count, it seems that you would like to consider them as representing one tiling. My answer below considers them as being distinct. To state it differently: I consider no symmetry that identifies two tilings.

  2. Your example for a $1\times 2$ rectangle is incorrect whatever way of counting you consider; you forgot the $R(1,2)$ construction.

A solution sketch. A tiling for a $1\times n$ rectangle is considered as having, either a final $R(1,i)$ or a $B(1,i)$ tile. Denote $r_n$ the number of tiling ending with a red one, and $b_n$ the number of those ending with a blue one. We need to determine these two sequences.

We have, after some moments of thought about the final tile, $b_n=b_{n-1}+r_{n-1}+b_{n-2}+r_{n-2}$ and $r_n=b_{n-1}+b_{n-2}$. Moreover, $b_1=1$ and $b_2=3$, and $r_1=1$ and $r_2=2$.

To have our count, it is sufficient to determine $(b_n)_n$. But using the two recurrent relations, $b_n=b_{n-1}+2b_{n-2}+2b_{n-3}+b_{n-4}$ with the initial conditions $b_{-3}=b_{-2}=b_{-1}=0$ and $b_0=1$. This is the sequence https://oeis.org/A123392.

For the $1\times 10$ problem, we obtain $b_8=461$, $b_9=1068$, $b_{10}=2474$, and hence $r_{10}=1529$. The sum $b_{10}+r_{10}$ is the number we are looking for.

Remark. If we want to obtain the number of tilings after the identification by reflection in the "vertical" mediator of the $1\times 10$ rectangle, the study of the tilings of the $1\times 5$ rectangle is needed and some considerations about the action of the group $\{-1,1\}$ (of the reflection) on the tilings of the $1\times 10$ rectangle.

Daniel N
  • 201