灯下 登录
番外 · 闲灯 / IMO Shortlist / C9 · combinatorics

2014 IMO Shortlist C9

题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。

IMO Shortlist 2014 C9 combinatorics

There are nn circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he reaches an intersection with another circle. Then he continues his journey on this new circle and also changes the direction of moving, i.e. from clockwise to anticlockwise or vice versa. Suppose that Turbo's path entirely covers all circles. Prove that nn must be odd.

在一张纸上画nn个圆,任意两个圆相交于两点,并且没有三个圆经过同一点。涡轮蜗牛按照以下方式沿着圆圈滑动。最初,他沿顺时针方向在其中一个圆圈上移动。 Turbo 总是沿着当前圆不断滑动,直到到达与另一个圆的交点。然后他在这个新的圆圈上继续他的旅程,并改变移动方向,即从顺时针到逆时针,反之亦然。假设 Turbo 的路径完全覆盖所有圆。证明 nn 一定是奇数。

提示 1

先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。

提示 2

找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。

提示 3

把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。

完整解答

这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2014 年 IMO Shortlist C9 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。

这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?