4
$\begingroup$

How many different sidewalks of length $n \geq 1$ can be laid using n $1 \times 1$ square tiles, given an unlimited supply of such tiles in white, blue and red colors so that no two red tiles lie next to each other?

We have that:

  • $f_1 = 3$, we can choose white, blue or red tile;
  • $f_2 = 8$, we can choose every combination from set: WW, BB, WB, BW, RB, BR, WR, RW (only RR can't be chosen);
  • $f_3 = 22$, we can choose every combinatorion ($3 \cdot 3 \cdot 3 = 27$) besides RRR $(1)$, RR[not R] $(2)$, [not R]RR $(2)$, therefore there is: $27 - 1 - 2 - 2 = 22$;
  • $f_4 = 64$, we can choose every combinatorion ($3 \cdot 3 \cdot 3 \cdot 3 = 81$) besides RRRR $(1)$, RR[not R][every possible] $(6)$, [not R][every possible]RR $(6)$, [not R]RR[not R] $(4)$ therefore there is: $81 - 1 - 6 - 6 - 4 = 60$;

Then I came up with an recursive formula: $f_n = 2f_{n-1} + 2f_{n-2}$. We take all the sequences without R on the last place - we can have W or B on the last place, therefore we have $2f_{n-1}$. Then we take all the sequences with R on the last place, those can't have R on the next-to-last place, therefore there is $2f_{n-2}$ of them. The formula works for $f_3$ and $f_4$ so I assume it's correct.

So I have:

  • $f_1 = 3$,
  • $f_2 = 8$,
  • $f_n = 2f_{n-1} + 2f_{n-2}$.

I calculate: $f_n = 2f_{n-1} + 2f_{n-2} \iff f_n - 2f_{n-1} - 2f_{n-2} = 0$

$x^2 - 2x - 2 = 0 \implies \Delta = 4 - 4 \cdot 1 \cdot (-2) = 12 \implies \sqrt{\Delta} = 2\sqrt{3}$

$x_1 = \frac{2 + 2\sqrt{3}}{2} = 1 + \sqrt{3} \ $ and $ \ x_2 = \frac{2 - 2\sqrt{3}}{2} = 1 -\sqrt{3}$

$f_n = a(1 + \sqrt{3})^n + b(1 - \sqrt{3})^n$ so:

  1. $a(1 + \sqrt{3}) + b(1 - \sqrt{3}) = 3 \iff a + \sqrt{3}a + b - \sqrt{3}b = 3$
  2. $a(1 + \sqrt{3})^2 + b(1 - \sqrt{3})^2 = 8 \iff a(1 + 2\sqrt{3} + 3) + b(1 - 2\sqrt{3} + 3) = 8 \iff 2a + \sqrt{3}a + 2b - \sqrt{3}b = 4$

By subtracting first equation from second one we get:

$a + b = 1 \iff a = 1 - b$

$1 - b + \sqrt{3}(1 - b) + b - \sqrt{3}b = 3 \iff b = \frac{1}{2} - \frac{\sqrt{3}}{3}$

$a = 1 - \frac{1}{2} + \frac{\sqrt{3}}{3} = \frac{1}{2} + \frac{\sqrt{3}}{3}$

So:

$f_n = (\frac{1}{2} + \frac{\sqrt{3}}{3})(1 + \sqrt{3})^n + (\frac{1}{2} - \frac{\sqrt{3}}{3})(1 - \sqrt{3})^n$

Is that correct?

$\endgroup$
1
  • 1
    $\begingroup$ OEIS: A028859 Number of words of length $n$ without adjacent $0$s from the alphabet $\{0,1,2\}$ $\endgroup$ Commented Aug 12, 2023 at 23:19

1 Answer 1

2
$\begingroup$

Your solution is correct. We first deduce the recurrence. The total number of ways $t_n$ we can tile the sidewalk of length $n$ with no two adjacent red tiles is $t_n = w_n + b_n + r_n$ with:

$$ w_n = w_{n - 1} + b_{n - 1} + r_{n - 1} $$ $$ b_n = w_{n - 1} + b_{n - 1} + r_{n - 1} $$ $$ r_n = w_{n - 1} + b_{n - 1} $$

where $w_n$ is the number of ways the sidewalk is tiled such that the $n$th tile is white. Similarly $b_n$ and $r_n$ are the number of ways the sidewalk is tiled such that the $n$th tiles are blue or red, respectively. We can simplify the above recurrences by noting that $w_n = b_n$ and so the system reduces to:

$$ b_n = 2b_{n - 1} + r_{n - 1} $$ $$ r_n = 2b_{n - 1} $$

which can be simplified further to:

$$ b_n = 2b_{n - 1} + 2b_{n - 2} $$

which means the total number of ways to tile the sidewalk is:

$$f_n = t_n = 2b_n + r_n = 2b_n + 2b_{n - 1} = b_{n+1}$$

with $b_1 = 1$ and $b_2 = 3$ and so we get:

$$f_n = 2f_{n - 1} + 2f_{n - 2}$$

with $f_1 = 3$ and $f_2 = 8$, which is the recurrence you obtained. You determined the solution to this recurrence to be:

$$ f_n = \left(\frac{1}{2} + \frac{\sqrt{3}}{3} \right) \left(1 + \sqrt{3} \right)^n + \left(\frac{1}{2} - \frac{\sqrt{3}}{3} \right) \left(1 - \sqrt{3} \right)^n$$

$$ f_n = \alpha \left(1 + \sqrt{3} \right)^n + \beta \left(1 - \sqrt{3} \right)^n$$

We verify the solution using induction:

$$ f_n = 2f_{n - 1} + 2f_{n - 2} $$ $$ = 2 \alpha \left(1 + \sqrt{3} \right)^{n - 1} + 2 \beta \left(1 - \sqrt{3} \right)^{n - 1} + 2 \alpha \left(1 + \sqrt{3} \right)^{n - 2} + 2 \beta \left(1 - \sqrt{3} \right)^{n - 2} $$ $$ = 2 \alpha \left( \frac{2 + \sqrt{3}}{\left( 1 + \sqrt{3} \right)^2} \right) \left(1 + \sqrt{3} \right)^n + 2 \beta \left( \frac{2 - \sqrt{3}}{\left( 1 - \sqrt{3} \right)^2} \right) \left(1 - \sqrt{3} \right)^n $$ $$ = \alpha \left(1 + \sqrt{3} \right)^n + \beta \left(1 - \sqrt{3} \right)^n$$

And so we conclude the solution to the recurrence is correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .