HMMT 二月 2007 · COMB 赛 · 第 8 题

英文解析

8. [ 6 ] A set of six edges of a regular octahedron is called Hamiltonian cycle if the edges in some orderconstitute a single continuous loop that visits each vertex exactly once. How many ways are there topartition the twelve edges into two Hamiltonian cycles?
   Answer: 6 . Call the octahedron ABCDEF , where A, B, and C are opposite D, E, and F, respectively. Note that each Hamiltonian cycle can be described in terms of the order it visits vertices inexactly 12 different ways. Conversely, listing the six vertices in some order determines a Hamiltoniancycle precisely when no pair of opposite vertices are listed consecutively or first-and-last. Suppose webegin with AB . If D is listed third, then the final three letters are CEF or F EC . Otherwise, C or Fis listed next, and each gives three possibilities for the final three. For example ABC is be followed by
   DEF, DF E, or EDF. Thus, there are 6 · 4 · (2 + 3 + 3) = 192 listings. These correspond to 192 / 12 = 16
   Hamiltonian cycles. Finally, the complement of all but four Hamiltonian cycles is a Hamiltonian cycle.
   For, each vertex has degree four, so is an endpoint of two edges in the complement of a Hamiltoniancycle, so is also a Hamiltonian cycle unless it describes two opposite faces. It follows that there are sixpairs of disjoint Hamiltonian cycles.