PUMaC 2008 · 组合（B 组） · 第 13 题

Combinatorics B

1. (2 points) Sarah buys 3 gumballs from a gumball machine that contains 10 orange, 6 green, and 9 yellow gumballs. What is the probability that the first gumball is orange, the second is green or yellow, and the third is also orange?
2. (2 points) How many 3-digit numbers contain the digit 7 exactly once?
3. (3 points) Draw a regular hexagon. Then make a square from each edge of the hexagon. Then form equilateral triangles by drawing an edge between every pair of neighboring squares. If this figure is continued symmetrically off to infinity, what is the ratio between the number of triangles and the number of squares?
4. (3 points) A 2008 × 2009 rectangle is divided into unit squares. In how many ways can you remove a pair of squares such that the remainder can be covered with 1 × 2 dominoes?
5. (4 points) Evaluate ( )( ) 2009 m ∑ ∑ 2009 m . m n m =0 n =0
6. (4 points) Find the sum of the values of x for which ( ) ( ) ( ) ( ) x x x x − + − · · · + = 0 . 0 1 2 2008
7. (5 points) In how many ways can Alice, Bob, Charlie, David, and Eve split 16 marbles among themselves so that no two of them have the same number of marbles?
8. (5 points) xxxx xx x x In how many ways can you fill in the xs with the numbers 1-8 so that for each x, the numbers below and to the right are higher. 1

Combinatorics B 9. (7 points) SET cards have four characteristics: number, color, shape, and shading, each of which has 3 values. A SET deck has 81 cards, one for each combination of these values. A SET is three cards such that, for each characteristic, the values of the three cards for that characteristics are either all the same or all different. In how many ways can you replace each SET card in the deck with another SET card (possibly the same), with no card used twice, such that any three cards that were a SET before are still a SET? (Alternately, a SET card is an ordered 4-tuple of 0s, 1s, and 2s, and three cards form a SET if their sum is (0 , 0 , 0 , 0) mod 3; for instance, (0 , 1 , 2 , 2), (1 , 0 , 2 , 1), and (2 , 2 , 2 , 0) form a SET. How many permutations of the SET cards maintain SET-ness?) 10. (7 points) How many spanning trees does the following graph (with 6 vertices and 9 edges) have? (A spanning tree is a subset of edges that spans all of the vertices of the original graph, but does not contain any cycles.) E D F C A B 2