题面据 IMO Shortlist 可核档案整理;中文题意为本站自译,公式请以原始来源为准。
Let be a finite set of points in the plane such that no three of them are on a line. For each convex polygon whose vertices are in , let be the number of vertices of , and let be the number of points of which are outside . Prove that for every real number where the sum is taken over all convex polygons with vertices in . NB. A line segment, a point and the empty set are considered as convex polygons of 2,1 and 0 vertices, respectively. (Colombia)
令 为平面上的有限点集,其中没有三个点在一条直线上。对于每个顶点在内的凸多边形,设为的顶点数,设为在之外的点数。证明对于每个实数 ,其中顶点在 中的所有凸多边形的总和。注意。线段、点和空集分别被视为具有 2,1 和 0 个顶点的凸多边形。 (哥伦比亚)
提示 1
先决定对象是什么:集合、图、排列、颜色、路径,还是一次操作后的状态。
提示 2
找一个极端对象、双计数式、不变量,或把限制转成图上的局部条件。
提示 3
把局部限制累加成全局矛盾,或给出覆盖全部情形的构造。
完整解答
这页先给题面、题型和提示阶梯,完整证明留给读者逐步展开。2006 年 IMO Shortlist C3 可先归入组合:第一步把题设翻成对象、条件、目标三行;第二步沿提示寻找不变量、标准构型或关键变形;第三步补齐边界情形,并回到题目原要求核对。
这题适合先独立想一轮再打开提示。不要急着搜索完整解答,先问自己:题面里最硬的限制是哪一句?