HMMT 二月 2009 · 冲刺赛 · 第 36 题

HMMT February 2009 — Guts Round — Problem 36

个人笔记

[ ≤ 25 ] Euler’s Bridge: The following figure is the graph of the city of Konigsburg in 1736 - verticesrepresent sections of the cities, edges are bridges. An Eulerian path through the graph is a path whichmoves from vertex to vertex, crossing each edge exactly once. How many ways could World War IIbombers have knocked out some of the bridges of Konigsburg such that the Allied victory parade couldtrace an Eulerian path through the graph? (The order in which the bridges are destroyed matters.)
Your score on this problem will be the larger of 0 and 25 − b d/ 10 c , where d is the positive differencebetween your answer and the correct answer. 5

解析

[ ≤ 25 ] Euler’s Bridge: The following figure is the graph of the city of Konigsburg in 1736 - verticesrepresent sections of the cities, edges are bridges. An Eulerian path through the graph is a path whichmoves from vertex to vertex, crossing each edge exactly once. How many ways could World War IIbombers have knocked out some of the bridges of Konigsburg such that the Allied victory parade couldtrace an Eulerian path through the graph? (The order in which the bridges are destroyed matters.)
Your score on this problem will be the larger of 0 and 25 − b d/ 10 c , where d is the positive differencebetween your answer and the correct answer.
Answer: 13023 9