HMMT 二月 2007 · COMB 赛 · 第 8 题

HMMT February 2007 — COMB Round — Problem 8

[ 6 ] A set of six edges of a regular octahedron is called Hamiltonian cycle if the edges in some order constitute a single continuous loop that visits each vertex exactly once. How many ways are there to partition the twelve edges into two Hamiltonian cycles?

解析

[ 6 ] A set of six edges of a regular octahedron is called Hamiltonian cycle if the edges in some order constitute a single continuous loop that visits each vertex exactly once. How many ways are there to partition the twelve edges into two Hamiltonian cycles? Answer: 6 . Call the octahedron ABCDEF , where A, B, and C are opposite D, E, and F, respec- tively. Note that each Hamiltonian cycle can be described in terms of the order it visits vertices in exactly 12 different ways. Conversely, listing the six vertices in some order determines a Hamiltonian cycle precisely when no pair of opposite vertices are listed consecutively or first-and-last. Suppose we begin with AB . If D is listed third, then the final three letters are CEF or F EC . Otherwise, C or F is 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 Hamiltonian cycle, so is also a Hamiltonian cycle unless it describes two opposite faces. It follows that there are six pairs of disjoint Hamiltonian cycles.