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

2016 IMO Shortlist C3

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

IMO Shortlist 2016 C3 combinatorics

Let nn be a positive integer relatively prime to 6 . We paint the vertices of a regular nn-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours. C4\mathbf{C 4}. Find all positive integers nn for which we can fill in the entries of an n×nn \times n table with the following properties: - each entry can be one of I,MI, M and OO; - in each row and each column, the letters I,MI, M and OO occur the same number of times; and - in any diagonal whose number of entries is a multiple of three, the letters I,MI, M and OO occur the same number of times.

nn 为与 6 互质的正整数。我们用三种颜色绘制正则 nn 边形的顶点,以便每种颜色都有奇数个顶点。证明存在一个等腰三角形,其三个顶点颜色不同。 C4\mathbf{C 4}。查找所有正整数 nn,我们可以将其填充到具有以下属性的 n×nn \times n 表的条目中: - 每个条目可以是 IMI、MOO 之一; - 在每一行和每一列中,字母IMI、MOO出现的次数相同; - 在任何条目数为三的倍数的对角线上,字母 IMI、MOO 出现的次数相同。

提示 1

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

提示 2

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

提示 3

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

完整解答

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

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