2018 UNCO Math Contest II Problems/Problem 10

Problem

The Seripians have seen the error of their ways and issued new pit-coins in 2-pit and 3-pit denominations, containing 2 and 3 serigrams of gold. One of the new coins is in the shape of a domino (two adjoining squares) and the other two are in the shape of triominoes (three adjoining squares), shown above. To celebrate the new coins, the Seripians have announced a contest. Seripian students can win fame and glory and 100 of each of the new Seripian pit-coins by successfully completing quests (a)-(d) below. Call a tiling by pit-coins prime if there is no vertical line that splits the tiling into tilings of two smaller shapes without cutting across any of the coins. The 2x5 tiling above on the left is prime and the 2x5 tiling on the right is not prime. Define P(n) to be the number of distinct prime tilings of a horizontal 2xn grid. For example, P(4) = 6, and the six distinct prime 2x4 tilings are shown at left. Define Q(n) to be the number of distinct prime tilings of the two 2xn grids with one unit corner square missing at the right end. Q(3) = 4 and the four prime tilings are shown to the left. We wish you success on the Seripian Quests. Show your work. (a) Determine P(6). (b) Determine formulas for P(n) and Q(n) in terms of Q(n 1), Q(n 2), and/or Q(n 3) that are valid for n 4. (c) Determine a formula for P(n) that does not use Q. You may use P(n 1), P(n 2), P(n 3), . . .. Specify how large n must be for your formula to work. (d) Determine explicitly P(11) and P(13).

See also

[[Category:]]