(8 分)将圆的一组 等分点分别涂上红色或蓝色,从任意一点开始,按逆时针方向依次记录 ()个点的颜色,称为该圆的一个“ 阶色序”,当且仅当两个 阶色序对应位置上的颜色至少有一个不相同时,称为不同的 阶色序。若某圆的任意两个“ 阶色序”均不相同,则该圆中等分点的个数最多可有个。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先以所有长度3的二进制串给上界,再给达到上界的循环。
三阶色序只有 种,且每个圆周顶点都对应一个起点,所以 。以0、1表示两种颜色,沿圆周依次排成
八个起点的三阶串依次为 ,互不相同。因此 。
串的末尾按圆周接回开头;最后两个串分别是110、100,不能遗漏环接窗口。
计数上界必须配合覆盖全部局部模式的循环构造。
学生需把任意连续三点颜色看作 种状态,先证上界再给出长度为 的构造,属于标准计数与构造,因此评为 F2。
已记下,谢谢!