Good Fences Make Good Neighbors

Let n be an even number. We will now calculate the number of ways we can build the fence of size 6*n. Let f(n) be such number of ways. We can easily find that f(0)=1; f(2)=1; f(4)=2. Now for $n \geq 6$ we have that:

• If we use a vertical board on top of the fence, we must use other vertical boards to fit the uppermost 6 6 square of the fence: We can do this in 3 ways (using a 2 6 board on the left and the 4 6 board on the right, or using a 2 6 board on the right and the 4 6 board on the left, or use three 2 6 boards). The rest of the fence can be built in f(n-6) ways. Thus in this case, there are 3.f(n-6) ways to build the fence.

• If we use a horizontal 6*2 board on top of the fence, the rest of it can be built in f(n-2) ways.

• If we use a horizontal 6*4 board on top of the fence, the rest of it can be built in f(n-4) ways.

Thus, we get that: f(n)=3.f(n-6)+f(n-4)+f(n-2)

• Using the above recursion formula, we can get that:

f(0)=f(2)=1; f(4)=2; f(6)=6; f(8)=11; f(10)=23; f(12)=52; f(14)=108; f(16)=229 and f(18)=493.

• Hence, the desired number is 493.

Let $F_n$ be the number of ways to build a fence 6 feet high and n feet long with the boards above. Consider the arrangement of boards on the left most side of the fence.

Case 1: The leftmost board is 6 feet high and 2 feet wide. The size of the remaining fence to be built is 6 feet high and $n-2$ feet wide and there are $F_{n-2}$ ways to build it.

Case 2: The leftmost board is 6 feet high and 4 feet wide. The size of the remaining fence to be built is 6 feet high and $n-4$ feet wide and there are $F_{n-4}$ ways to build it.

Case 3: The leftmost column contains boards which are all 6 feet wide. There are 3 ways to do it, either 3 boards with a height of 2 feet, 1 board with height 4 feet on top of a board with height 2 feet and 1 board with height 2 feet on top of a boards of height 4 feet. The size of the remaining fence to be built is 6 feet high and $n-6$ feet wide and there are $F_{n-6}$ ways to build it and since there are 3 ways for the leftmost column to be arranged, it corresponds to a total of $3F_{n-6}$ for this case.

One can check that all these cases are mutually exclusive and exhaust all the possibilities. Hence, we can construct the recurrence relation $F_n = F_{n-2}+F_{n-4}+3F_{n-6}$ and we can now proceed to find $F_{18}$

Firstly, $F_0 = 1$ which is no boards at all, $F_2 = 1$ which corresponds to one 2 by 6 board and $F_4 = 2$ which corresponds to two 2 by 6 boards or one 4 by 6 board. We proceed by repeatedly applying the recurrence relation.

$F_6 = F_4+F_2+3F_0 = 6$

$F_8 = F_6+F_4+3F_2 = 11$

$F_{10} = F_8+F_6+3F_4 = 23$

$F_{12} = F_{10}+F_8+3F_6 = 52$

$F_{14} = F_{12}+F_{10}+3F_8 = 108$

$F_{16} = F_{14}+F_{12}+3F_{10} = 229$

$F_{18} = F_{16}+F_{14}+3F_{12} = 493$

Hence the required answer is 493.

First of all, we can simplify the problem a bit by noting that there is a 1-1 correspondence between the possible tilings of a 6 x 18 fence using 2 x 6 and 4 x 6 boards, and the possible tilings of a 3 x 9 fence using 1 x 3 and 2 x 3 boards.

The proof of this is straightforward: For every tiling of a 6 x 18 fence using 2 x 6 and 4 x 6 boards, we can merge each of the 27 constituent 2 x 2 boxes of the fence into a 1 x 1 box to get a tiling of a 3 x 9 fence using 1 x 3 and 2 x 3 boards. Conversely, for every tiling of a 3 x 9 fence using 1 x 3 and 2 x 3 boards, we can split each of the 27 constituent 1 x 1 boxes of the fence into a 2 x 2 box to get a tiling of a 6 x 18 fence using 2 x 6 and 4 x 6 boards.

Thus, the problem has been reduced to finding the number of tiling of a 3 x 9 fence using 1 x 3 and 2 x 3 boards. To do this, we introduce an important lemma:

$\textbf{Lemma.}$ Let $N(3, m)$ denote the number of ways to tile a $3\times m$ fence using $1\times 3$ and $2 \times 3$ boards. Then for every $m\ge 4$ , $N(3, m)=3\cdot N(3, m-3)+N(3, m-2)+N(3, m-1)$ $\textbf{Proof.}$ Consider the upper left box of the $3\times m$ fence. It is either covered by a $1\times 3$ board or a $2\times 3$ board. Furthermore, each board can by oriented in two different ways to cover the upper left box.

$\textbf{ Case 1: A 1 x 3 board is oriented so that the "3 side" is vertical}$ In this case the problem is reduced to finding $N(3, m-1)$ .

$\textbf{ Case 2: A 1 x 3 board is oriented so that the "1 side" is vertical}$ Clearly the only way to fill in the lower left 2 x 3 "gap" is to fill it with two 1 x 3 boards or one 2 x 3 board. Once that has been filled, the problem reduces to finding $N(3, m-3)$ . Thus this case gives $2\cdot N(3, m-3)$ tilings.

$\textbf{ Case 3: A 2 x 3 board is oriented so that the "3 side" is vertical}$ In this case the problem is reduced to finding $N(3, m-2)$ .

$\textbf{ Case 4: A 2 x 3 board is oriented so that the "2 side" is vertical}$ Clearly the only way to fill in the lower left 1 x 3 "gap" is to fill it with a 1 x 3 board. Thus this case gives $N(3, m-3)$ tilings.

Adding up all our cases gives the desired $N(3, m)=3\cdot N(3, m-3)+N(3, m-2)+N(3, m-1)$ . This completes the proof.

Starting with $N(3, 1)=1, N(3, 2)=2, N(3, 3)=6$ , it is now straightforward to use our recursive equation to compute that $N(3, 9)=\boxed{493}$ .

For convenience's sake, let's say the $2\times 6$ feet board type 1 and the $4\times 6$ board type 2 . Also define $f(x)$ as the number of ways to cover a fence that is $6$ feet high and $2x$ feet wide. The answer to this problem is simply $f(9)$ . Now consider the lowest and rightmost board.

If it is a type 1 board aligned vertically, then the number of ways to cover the rest of the fence is $f(x-1)$ . Similarly, if it is a type 2 board aligned vertically, then the number of ways is $f(x-2)$ .

For $x > 3$ , if it is a type 1 board aligned horizontally, then the board above it must be aligned horizontally, too. There are two ways to cover the empty space above it: using one type 2 board, or using two type 1 boards. Since the number of ways to cover the rest of the fence is $f(x-3)$ , then there are $2\times f(x-3)$ ways.

Similarly, if it is a type 2 board aligned horizontally, then the board above it must be a type 1 board and it must be aligned horizontally, too. Then the number of ways is $f(x-3)$ ways.

So, we get the recursive formula of $f$ : $f(x) = f(x-1) + f(x-2) + 3f(x-3)$ for $x > 3$ .

Counting manually, we will see that $f(1) = 1, f(2) = 2$ , and $f(3) = 6$ . So,

• $f(4) = f(3) + f(2) + 3f(1) = 11$
• $f(5) = f(4) + f(3) + 3f(2) = 23$
• $f(6) = f(5) + f(4) + 3f(3) = 52$
• $f(7) = f(6) + f(5) + 3f(4) = 108$
• $f(8) = f(7) + f(6) + 3f(5) = 229$
• $f(9) = f(8) + f(7) + 3f(6) = 493$

Hence the desired answer is 493.

Since all dimensions in the question are even we can divide them all by 2. Then the question can be rephrased to say, "How many ways are there to tile a 3x9 board with 1x3 and 2x3 dominoes if they can be rotated and no dominoes can go off of the board or overlap?"

Let a n be the number of ways that an 3xn board can be tiled using 1x3 and 2x3 dominoes. Then for all n>=4 we will determine an expression for a n in terms of a_k where k<=n. So we consider the number of ways to cover the rightmost square in the middle row. You can either cover it with a 1x3, 3x1, 2x3, or 3x2.

1st case: If you cover the square with a 1x3. Then the the rightmost squares in the top and bottom rows must be covered by 1x3s as well. So we have covered the rightmost 3x3. So there are a_(n-3) ways to cover the rest of the squares.

2nd case: If you cover the square with a 3x1. Then There are a_(n-1) ways to cover the rest of the squares.

3rd case: If you cover the square with a 2x3. Then it can either also cover the rightmost square in the top row or the rightmost square in the bottom row. So to cover the other of the two squares you must use a 1x3. Then there are a_(n-3) ways to cover the rest, but we must multiply by 2 because there are 2 ways to cover the 3x3.

4th case: If we cover the square with a 3x2. Then there are a_(n-2) ways to cover the rest.

So the recursion is a n=a (n-3)+a (n-1)+2a (n-3)+a (n-2)=a (n-1)+a (n-2)+3a (n-3). Now we have that a 1=1, a 2=2, and a 3=6. Using the recursion we eventually find that a 9=493.

For simplicity, let's divide every dimension by 2. Hence, the fence is 3 feet by 9 feet, and the boards are 1 feet by 3 feet and 2 feet by 3 feet. This clearly doesn't change the final answer.

Let $f(n)$ be the number of different ways one can build a 3 by n fence. Our goal is to find $f(9)$ .

Let's find a recursion for $f(n)$ (assume $n \ge 3$ ). Suppose we are building the fence from left to right. The first board can be placed either horizontally or vertically. If we place it vertically, we get $f(n-1)$ ways to build the fence using the 1 by 3 board, and $f(n-2)$ ways using the 2 by 3 board.

If we place the first board horizontally, then the whole leftmost 3 by 3 square has to be filled with horizontal boards. We can do this in 3 ways: one way using only 1 by 3 boards and two ways using both 1 by 3 and 2 by 3 boards. This adds $3f(n-3)$ ways to build the fence.

We covered every case, so we have $f(n) = f(n-1) + f(n-2) + 3f(n-3)$ , with trivial base cases $f(0) = 1, f(1) = 1$ and $f(2) = 2$ . Solving the recursion (since 9 is small, one can find every value of $f$ from 0 to 9), we find $f(9) = 493$ , and that's the answer to our problem.

Let f_n be the number of ways to tile a 6 feet high and n feet wide fence.

Case 1: We place a 2 x 6 board such that it is 6 feet high at the beginning of the fence. Hence we have f_(n-2) ways left to build the fence.

Case 2: We place a 4 x 6 board such that it is 6 feet high at tyhe beginning of the fence. Hence we have f_(n-4) ways left to build the fence.

Case 3: We place the boards sideways so that it is 6 feet wide at the beginning. We can do this in 3 ways. We can use three boards of 2 x 6, a 2 x 6 board on top of a 4 x 6 board, or a 4 x 6 board on top of a 2 x 6 board. In each case we have f_(n-6) ways left to build the fence.

Therefore

f n = f (n-2) + f (n-4) + 3f (n-6) for sufficiently large n (which in this case is n => 8). I say sufficiently large because some cases clearly do not apply for a fence that is not wide enough.

Note that f 2 = 1 f 4 = 2 f_6 = 6

From here we can compute recursively for f 18. f 18 = 493

For simplicity, scale everything down by a factor of 2, so that Trahen is building a 3" by 9" fence with 1" by 3" and 2" by 3" boards.

Let f n be the number of ways to build a 3" by n" fence. We will find a recursion by expressing f n in terms of other f_i. Now, divide the fence into 3n squares. Consider the middle square of the left most column. There are two cases: it may a part of a 1" by 3" board, or it may be a part of a 2" by 3" board.

Case 1: Part of 1" by 3" board The board may be oriented horizontally (1" as width, 3" as length), in which case the top and bottom squares of the left most column are parts of 2 other horizontal 1" by 3" boards. This leaves a 3" by (n-3)" fence, so there are f (n-3) ways. However, if the board is oriented vertically, we have a 3" by (n-1)' fence, so there are f (n-1) ways.

The total for this case is f (n-1)+f (n-3).

Case 2: Part of 2" by 3" board The board may be oriented vertically (3" as width, 2" as length), in which case there remains a 3" by (n-2)" fence, for which there are f_(n-2) ways. However, if the board is oriented horizontally, it may either include the top square of the leftmost row, or it may include the bottom row. These are 2 ways to do it, and the remaining square must be filled with a 1" by 3" board, leaving a 3" by (n-3)" board. Thus, there are 2*f(n-3) ways.

The total for this case is f (n-2)+2*f (n-3).

Now, we have the recursion f n=f (n-1)+f (n-2)+3*f (n-3). We then see that f 0= 1 (only one way - don't do anything!), f 1=1 (just one 1" by 3" board), and f 2=2 (either two 1" by 3" boards, or one 2' by 3" board). This implies f 3=2+1+3=6, which can also be confirmed through casework. Proceeding in this manner, we find f 4=11, f 5=23, and so on, until we reach f_9=493.

a 0=1,a 1=1,a_1=2

This problem can be solved via a systematic counting of all possibilities. Let the 2x6 boards be called "thin" boards and 4x6 be "wide" boards.

We consider first the cases where all boards are placed vertically (i.e. the 6 foot length is used for the fence's height), so the sum of the widths of the boards used is 18 feet. Listing out the possible combinations of the boards used: $4w + 1t: \frac{5!}{4!}=5$

$3w + 3t: \frac{6!}{3!3!}=20$

$2w + 5t: \frac{7!}{2!5!}=21$

$1w + 7t: \frac{8!}{7!}=8$

$9t: 1$

Giving a total of $5+20+21+8+1=55$ ways where all boards are vertical.

Now, we consider what happens when boards are placed horizontally. If any board is placed horizontally, it can only have other horizontal boards on top of it to make the 6 foot height of the wall. Additionally, the horizontal boards must be flush against each other and not stacked with overlap (like a brick wall), or the finished fence would not be rectangular. Thus, any horizontal boards must be part of some 6x6 section of fence made out of only horizontal boards.

Considering 1 such 6x6 section of fence, it can be made from 3 thin boards, or a thin board on top of a wide one, or a wide one on top of a thin. So there are 3 possible constructions of a "horizontal" 6x6 section of fence.

Now we consider the number of ways the fence can be built with a number of "horizontal" (notated as h below) sections, again with the total length of the fence coming to 18 feet.

3 horizontal sections: $3^3=27$ ways,

2 horizontal sections:

$2h + 1w + 1t: \frac{4!}{2!}=12$

$2h + 3t: \frac{5!}{2!3!}=10$

Giving $9\times(12+10)=198$ ways,

1 horizontal section:

$1h + 3w: \frac{4!}{3!}=4$

$1h + 2w + 2t: \frac{5!}{2!2!}=30$

$1h + 1w + 4t: \frac{6!}{4!}=30$

$1h + 6t: \frac{7!}{6!}=7$

Giving $3\times(4+30+30+7)=213$ ways.

So there are $27+198+213=438$ ways with horizontal boards.

And we thus get a grand total of $55+438=493$ ways of building the entire fence.

Let $s_n$ be the number of ways to build a fence of height 6 and width $2n$ . Let us consider the leftmost end of the fence. This can have either a vertical $6 \times 2$ board, a vertical $6 \times 4$ board, 3 horizontal $6 \times 2$ boards, or one horizontal $6 \times 2$ board and one horizontal $6 \times 4$ board stacked in two different ways. This gives the recurrence relation $s_n = s_{n-1} + s_{n-2} + 3s_{n-3}$ . There is one way to build a fence of width 2, and 2 ways to build a fence of width 4. There are 6 ways to build a fence of width 6 (2 using only $2 \times 6$ boards, and 4 using 1 of each board). From here, we recursively calculate the following table of values:

$\begin{array}{c|ccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline s_n & 1 &2 &6&11&23&52&108&229&493\\ \end{array}$

Thus there are 493 ways to build a fence with width 18.

Note: There is 1 way to build a fence of width 0, which give $s_3 = s_2 + s_1 + 3 s_0 = 6$ .