Topic 23: Hamiltonian path
Problem: A regular octahedron is shown in the diagram below. There are 6 vertices altogether connected by a total of 12 edges. An ant starts from vertex A and moves along any edge but cannot go through any edge more than once. If the ant visits each vertex exactly once before it returns to vertex A, how many different routes are there?
Dịch đề: Cho một khối bát diện đều như hình vẽ. Bát diện có 6 đỉnh được nối với nhau bằng 12 cạnh. Một con kiến bắt đầu đi từ đỉnh A và đi trên các cạnh, nhưng không được đi cạnh nào quá 1 lần. Biết con kiến đã đi qua mỗi đỉnh đúng 1 lần trước khi quay trở về đỉnh A. Hỏi có bao nhiêu đường đi thỏa mãn?
Lời giải
Bước 1: Đi từ A đến X với X thuộc C; D; E; F. Có 4 cách đi.
Bước 2: Không mất tính tổng quát, giả sử X là điểm C trong bước 1. Để ý rằng không thể tạo ra một chu trình Hamilton từ C đi qua 3 hoặc 4 cạnh của hình vuông CDEF rồi đi xuống B. Xét 3 khả năng sau đây:
a) Từ C đi trực tiếp xuống B. Khi đó, ta có 2 chu trình là: (ACBDEFA) và (ACBFEDA).
b) Từ C đi theo 1 cạnh CD hoặc CF của hình vuông CDEF rồi đi xuống đỉnh B.
Khi đó, ta có 4 chu trình là: (ACDBEFA); (ACDBFEA); (ACFBDEA); (ACFBEDA).
c) Từ C đi theo 2 cạnh của hình vuông CDEF rồi đi xuống đỉnh B.
Khi đó, ta có 2 chu trình là (ACDEBFA) và (ACFEBDA).
Từ a); b); c) suy ra có 2 + 4 + 2 = 8 chu trình đi qua đỉnh C là đỉnh thứ 2 trong chu trình.
Bước 3: Do 4 đỉnh C, D, E, F có vai trò như nhau nên có tất cả: 8 × 4 = 32 (chu trình).
Solution
Step 1: There are 4 possible paths from A to X, with X as C; D; E; or F.
Step 2: Without loss of generality, let X be C in step 1. Note that there is no possible Hamiltonian path from C to B that passes through 3 or 4 sides of square CDEF. Thus, we only have to consider the 3 following possibilities:
a) The ant travels from C directly to B. There are 2 possible paths: (ACBDEFA) and (ACBFEDA).
b) The ant travels from C to B via side CD or CF of square CDEF. There are 4 possible paths: (ACDBEFA); (ACDBFEA); (ACFBDEA); (ACFBEDA)
c) The ant travels from C to B via 2 sides of square CDEF. There are 2 possible paths: (ACDEBFA) and (ACFEBDA).
From a); b); c); it follows that there are 2 + 4 + 2 = 8 paths in which C is the second vertex to be passed.
Step 3: Since C, D, E, F are equivalent, in total there are 8 × 4 = 32 (possible paths).