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

Combinatorics

1. 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? 9 ( ANS: . There is a 10 in 25 chance for the first part to work, a 15 in 24 chance for the second 92 one to work, and a 9 in 23 chance for the last one. CB: EK, TW, ACH)
2. How many 3-digit numbers contain the digit 7 exactly once? ( ANS: 225: if the 7 is the first digit, there are 81 choices for the other two digits, if the 7 is second or third, there are 72 choices, as a three digit number cannot start with 0. None of these numbers are the same, as the 7 is in a different place each time. CB: ACH, RH, PR)
3. 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? 2 ( ANS: . Each vertex is next to 2 squares, 1 triangle, and 1 hexagon. Since the number of 3 2 1 1 vertices on a square is 4, = of the polygons are squares. Similarly, of the polygons are 4 2 3 1 2 triangles and of the polygons are hexagons, yielding as the answer. CB: AP) 6 3
4. 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? ( ) 2 2008 × 2009 ( ANS: , if you color the rectangle’s squares so that every white square only borders 2 black squares and vise-versa, you see that the two removed squares have to be on different colors. If they’re of different colors: Color the board like a checkerboard. It is clear that a domino covers one black square and one red, so the two pieces removed must be different colors. An m x 1 rectangle can be filled in by dominoes if m is even. Therefore an m by n rectangle can be filled in with dominoes if mn is even, by giving all dominoes the same orientation. Start with this tiling. Without loss of generality, say that the number of rows is even and that the dominoes are laid down 2 units tall and one unit wide. Given a path from one of the removed squares to the other, such that the path never crosses itself, and the first square of any domino in the path is consecutive with the second, we can create a new tiling. If the removed spaces are at different heights but on dominoes of the same height, then they are opposite corners of a 2 x odd rectangle, which with the two corners removed becomes two 1 x even rectangles, and the old tiling is easy to replace. If the removed tiles are at the same height, 1

Combinatorics then the two affected dominos and those in between now form two 1 x even rectangles and can be trivially filled in. Two spaces removed in the same column can be removed and the rest filled in with all vertical dominoes or two horizontal ones in that column and an adjacent column. Now, if the two affected dominoes are not on the same column or pair of rows, we can reduce to a few cases: Case 1: The removed spaces differ by an even number of rows. Then, WLOG, say both of the removed spaces are top halves of the dominoes of the original tiling, and we have a path moving down from the higher spot to the lower column and snakewise horizontally to the other. Case 2: They differ by an odd number of rows, and the higher domino is in the top half of its cell. Then a path exists by moving within the column from the lower domino to the height of higher one and then snakewise horizontally. Case 3: They differ by an even number of rows, and the higher domino is in the bottom half of its cell. Then shift horizontally one column from the remaining space of the affected domino in the direction of the other removed space, we have reduced to case 1. CB: AL12, IAF) 5. Evaluate ( )( ) 2009 m ∑ ∑ 2009 m . m n m =0 n =0 2009 ( ANS: 3 . ( )( ) ( ) ( ) ( ) 2009 m 2009 m 2009 ∑ ∑ ∑ ∑ ∑ 2009 m 2009 m 2009 m 2009 2009 = = (1 + 1) = (1 + 1 + 1) = 3 m n m n m m =0 n =0 m =0 n =0 m =0 CB: GL) 6. Find the sum of the values of x for which ( ) ( ) ( ) ( ) x x x x − + − · · · + = 0 . 0 1 2 2008 ( ANS: 2017036. The numbers n with 1 < n < 2008 satisfy that, as, for those n , we have that the n sum is (1 − 1) . Moreover, that is it, as the sum is a 2008 degree polynomial and we have provided 2008 roots. CB: AL, ACH) 7. In how many ways can Alice, Bob, Charlie, David, and Eve split 18 marbles among themselves so that no two of them have the same number of marbles? 2

Combinatorics ( ANS: 2160: Suppose we have a valid 5-tuple a < b < c < d < e . Let A = a , B = b − a − 1, C = c − b − 1, D = d − c − 1 and E = e − d − 1. Now we have A, B, C, D ≥ 0 and A + B + C + D + E = 8 We can just enumerate the solutions: for 18: 10100 10011 10003 02000 01101 01020 01012 01004 00210 00202 00121 00113 00105 00040 00032 00024 00016 00008 so there are 18 ∗ 5! solutions CB: AP) 8. 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? ( ANS: 1200: Suppose we have a valid 5-tuple a < b < c < d < e . Let A = a , B = b − a − 1, C = c − b − 1, D = d − c − 1 and E = e − d − 1. Now we have A, B, C, D ≥ 0 and 3

Combinatorics A + B + C + D + E = 6 We can just enumerate the solutions: for 16: 10001 01010 01002 00200 00111 00103 00030 00022 00014 00006 yielding that there are 10 ∗ 5! solutions. CB: AP) 9. 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. ( ANS: 90 ABCD EF G H Clearly A = 1. Now either B or E is 2, so we may assume B = 2 and then double the number we get. We now have three cases: 12 CD 3 F G H 4

Combinatorics 12 CD 4 F G H 12 CD 5 F G H ( E cannot be 6 or higher since F, G, H are all larger than E .) For the first case, there are 5 ( ) 4 choices for F among 4 , 5 , 6 , 7 , 8, and then ways to split the remaining numbers between C, D 2 and G, H . Thus we get 5 · 6 = 30 possibilities. ( ) 4 For the second case, there are ways of choosing F, G, H among 5 , 6 , 7 , 8, and then three 3=4 ways of choosing F among F, G, H , making for 4 · 3 = 12 possibilities (after choosing F, G, H , the rest is forced). For the last case, there are three choices for F among 6 , 7 , 8, and once F is chosen, the rest is forced. Thus we get 3 possibilities. In total, we have 30 + 12 + 3 = 45 possibilities. Doubling this, we get 90 as claimed. CB: AP) 10. Joe makes two cubes of sidelengths 9 and 10 from 1729 randomly oriented and randomly arranged unit cubes, which are initially unpainted. These cubes are dipped into white paint. Then two cubes of sidelengths 1 and 12 are formed from the same unit cubes, again randomly oriented and randomly arranged, and these cubes are dipped into paint remover. Joe continues to alternately dip cubes of sides 9 and 10 into paint and cubes of sides 1 and 12 into paint remover ad nauseam. What is the limit of the expected number of painted unit cube faces immediately after dipping in paint remover? Cube painting question 2974267296 ( ANS: Let a be the number of faces painted on the paint stage. Let b be the number of 537409 faces erased at the paint remover stage. Let X be the limit of the expected number of painted faces after the paint stage. Let Y be the limit of the expected number of painted faces after the paint remover stage. Then we have the following system of equations: 6 · 1729 − b 6 · 1729 − a Y = XX = a + Y (1) 6 · 1729 6 · 1729 10374 10374 − a We wish to find Y . Solving these, we find Y = a + Y . Thus 10374 − b 10374 2 10374 Y = a (10374 − b )10374 + (10374 − a )(10374 − b ) Y . Simplifying, we have: 10374 a (10374 − b ) Y = (2) 10374( a + b ) − ab 5

Combinatorics 2 2 2 2 Now we calculate a = 6 ∗ (9 + 10 ) = 1086 and b = 6 ∗ (1 + 12 ) = 870. Substituting this into our equation for Y , we find: 2974267296 Y = (3) 537409 as claimed. CB: JVP) 11. 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) 12. 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.) 6

Combinatorics E D F C A B ( ANS: 75, 1 possible solution: Establish that a spanning tree includes 5 edges; less does not cover all vertices and more must include a cycle. There are 9 choose 5 = 126 arbitrary sets of 5 edges. We need to count 5-edge sets that do not contain cycles, which are connected because they hit all vertices in some order. There are 2 cycles with 3 edges, 3 cycles with 4 edges, and 6 cycles with 5 edges. Up to 1 cycle can occur in an arbitrary set of 5 edges. Given a cycle, arbitrarily choose remaining edges: 2 * 15 + 3 * 5 + 6 = 51 edge sets containing a cycle, so there are 126 - 51 = 75 edges without cycles. Thus there are 75 spanning trees. CB: AP, VT, ACH) 13. In his youth, Professor John Horton Conway lived on a farm with 2009 cows. Conway wishes to move the cows from the negative x axis to the positive x axis. The cows are initially lined up in order 1 , 2 , . . . , 2009 on the negative x axis. Conway can give two possible commands to the cows. One is the PUSH command, upon which the first cow from the negative x axis moves to the lowest position on the positive y axis. The other is the POP command, upon which the cow in the lowest position on the y axis moves to the positive x axis. For example, if Conway says PUSH POP 2009 times, then the resulting permutation of cows is the same, 1 , 2 , . . . , 2009. If Conway says PUSH 2009 times followed by POP 2009 times, the resulting permutation of cows is 2009 , . . . , 2 , 1. How many output permutations are possible after Conway finishes moving all the cows from the negative x axis to the positive x axis? ( ) 4018 1 ( ANS: Conway can call any sequence of 2009 PUSHs and 2009 POPs as long as at no 2010 2009 point in time does the number of POPs exceed the number of POPs. The number of such ( ) 2 n 1 sequences is well known to be the 2009th Catalan number C where C = . It is also 2009 n n +1 n easy to see that different sequences of PUSH and POP lead to different output permutations. ( ) 4018 1 Thus the answer is as claimed. CB: JVP) 2010 2009 7