返回题库

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

PUMaC 2008 — Combinatorics (Division B) — Problem 11

专题
Discrete Math / 离散数学
难度
L3
来源
PUMaC

题目详情

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

解析
  1. 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?) 4 ( ANS: 1965150720 We can model the set of SET cards as points in V = ( F ) . Then a triple of 3 cards p , p , p forms a SET if and only if p + p + p = 0 in V . We are searching for SET 1 2 3 1 2 3 automorphisms of V that preserve sets (that is, permutations of the elements of V that preserve sets). Suppose we have some such automorphism f : V → V . First observe that changing f to f + v where v is any vector in V does not change whether or not f preserves sets since 3 v = 0 0 0 0 4 for all vectors v ∈ V . Thus we conclude that the total number of acceptable f ’s is 3 times the 0 total number of acceptable f ’s which additionally have the property that f (0 , 0 , 0 , 0) = (0 , 0 , 0 , 0). Now let us count these such f . Suppose f is one such automorphism. Then we see that v + (0 , 0 , 0 , 0) + − v = 0 = f ( v ) + (0 , 0 , 0 , 0) + f ( − v ) since f preserves sets. Thus we conclude that f ( − v ) = − f ( v ). Now we also see that v + w + ( − v − w ) = 0 = f ( v ) + f ( w ) + f ( − v − w ), so f ( v ) + f ( w ) = f ( v + w ). Thus we conclude that f is linear , i.e. it is a VECTORSPACE automorphism of V . Since f is one to one, we conclude f ∈ GL ( F ). Conversely, it is easy to see 4 3 that any f ∈ GL ( F ) preserves sets. Thus we wish to count the number of elements in GL ( F ). 4 3 4 3 There are various ways of computing the order of the general linear group over a finite field. One 4 4 way is to observe that there are (3 − 1) ways of choosing the first column of the matrix, (3 − 3) 4 2 ways of choosing the second column, (3 − 3 ) ways of choosing the third, etc. In general, the n n n n − 1 order of GL ( F ) is ( q − 1)( q − q ) . . . ( q − q ). Thus for our case, we find n q 4 | GL ( F ) | = 80 · 78 · 72 · 54 = 24261120. Multiplying by 3 = 81, we get 1965150720 as claimed. 4 3 CB: JVP)