(New page: Category:MA375Spring2009Walther) |
|||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
[[Category:MA375Spring2009Walther]] | [[Category:MA375Spring2009Walther]] | ||
| + | [[Category:MA375]] | ||
| + | [[Category:math]] | ||
| + | [[Category:discrete math]] | ||
| + | [[Category:problem solving]] | ||
| + | |||
| + | =[[MA375]]: [[MA_375_Spring_2009_Walther_Week_5| Solution to a homework problem from this week or last week's homework]]= | ||
| + | Spring 2009, Prof. Walther | ||
| + | ---- | ||
| + | 7.1 | ||
| + | |||
| + | 42. How many ways can a 2 x n board be filled by tiles two squares in size? | ||
| + | |||
| + | a) To solve this problem, divide how you can place the upper right dominoe into two cases | ||
| + | |||
| + | Case 1: Vertical-if you place a vertical tile in the upper right of the board, you can only place another vertical tile on the left to fill up the open space. After doing this, you have a 2 x (n-2) space to fill. (a_n-2) | ||
| + | |||
| + | Case 2: Horizontal-if you place a horizontal tile at the top of the board, you are left with a 2 x (n-1) space to fill. (a_n-1) | ||
| + | |||
| + | Adding these two cases, we find: a_n = a_n-1 + a_n-2 | ||
| + | |||
| + | b) There is one way to fill a 2 x 1 board with a 2 square tile, so a1 = 1. A 2 x 2 board can be filled with two horizontal tiles or two vertical tiles, so a2 = 2. | ||
| + | |||
| + | c) To find a17 just repeat the recursion, starting with the initial conditions, until a17 = a16 + a15 is reached. | ||
| + | ---- | ||
| + | [[MA375_%28WaltherSpring2009%29|Back to MA375, Spring 2009, Prof. Walther]] | ||
Latest revision as of 08:22, 20 May 2013
MA375: Solution to a homework problem from this week or last week's homework
Spring 2009, Prof. Walther
7.1
42. How many ways can a 2 x n board be filled by tiles two squares in size?
a) To solve this problem, divide how you can place the upper right dominoe into two cases
Case 1: Vertical-if you place a vertical tile in the upper right of the board, you can only place another vertical tile on the left to fill up the open space. After doing this, you have a 2 x (n-2) space to fill. (a_n-2)
Case 2: Horizontal-if you place a horizontal tile at the top of the board, you are left with a 2 x (n-1) space to fill. (a_n-1)
Adding these two cases, we find: a_n = a_n-1 + a_n-2
b) There is one way to fill a 2 x 1 board with a 2 square tile, so a1 = 1. A 2 x 2 board can be filled with two horizontal tiles or two vertical tiles, so a2 = 2.
c) To find a17 just repeat the recursion, starting with the initial conditions, until a17 = a16 + a15 is reached.
