培玉 · 一试
2024 年中科大少年班入围考 · 第 11 题
F3填空题组合计数综合
一只蚂蚁从边长为1的正方体的一个顶点出发，沿棱爬行，要求经过所有棱并回到出发点。 最短路径长度为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
闭路的每点总经过度为偶数，而立方体八顶点的原度均为奇数，因此至少补四次棱。再给实际闭走达到。
解答
每条棱至少走一次，先计十二次。记额外重复的棱构成多重图。闭走使每个顶点的总经过度为偶数，减去原图每点度三后，额外度在八点均为正奇数，和至少八；每条额外棱贡献两度，所以至少多走四次。路径长度至少十六。 沿通常下底 、上底 的对应标号，闭走
共十六步，覆盖全部十二棱，其中只将 各多走一次。因此最短长度为 。
复核
所列每一对相邻顶点都是原棱，末点回到起点。棱长均一，次数与长度相同；奇度约束针对每个顶点，不能只以总棱数偶数判断已可闭走。
方法总结
遍棱闭路先用顶点奇偶度数给重复次数的下界，再检查能否用匹配的补边和真实回路达到。
为什么评为 F3（会透露解法方向）
须自主把闭路进出次数转成每顶点至少四次的下界，并选择四条匹配棱达到；下界与构造围绕同一奇偶结构衔接。
已记下，谢谢！