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

PUMaC 2008 — Combinatorics (Division B) — Problem 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

解析

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)