Difference between revisions of "2018 UNCO Math Contest II Problems/Problem 10"
(→See also) |
m (→Problem) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == 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). | ||
== Solution == | == Solution == | ||
| + | a) <math>P(6) = 10</math> | ||
| + | |||
| + | b) <math>P(n) = Q(n-1) + Q(n-2) (n>=4); Q(n) = Q(n-1) + Q(n-3) (n>=4)</math> | ||
| + | |||
| + | c) <math>P(n) = P(n-1) + P(n-3) (n>=7)</math> | ||
| + | |||
| + | d) <math>P(11) = 74; P(13) = 158</math> | ||
== See also == | == See also == | ||
{{UNCO Math Contest box|year=2018|n=II|num-b=9|num-a=11}} | {{UNCO Math Contest box|year=2018|n=II|num-b=9|num-a=11}} | ||
| − | [[Category:]] | + | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 10:33, 1 December 2020
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).
Solution
a) 
b) 
c) 
d) 
See also
| 2018 UNCO Math Contest II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 9 |
Followed by Problem 11 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 | ||
| All UNCO Math Contest Problems and Solutions | ||
