Question

设 $S$ 是 $\{1,2,3,\ldots,1989\}$ 的一个子集，且 $S$ 中任意两个元素之差都不等于 $4$ 或 $7$ 。 $S$ 最多能有多少个元素？

Let $S$ be a subset of $\{1,2,3,\ldots,1989\}$ such that no two members of $S$ differ by $4$ or $7.$ What is the largest number of elements $S$ can have?

答案

答案：905

知识点：极端原理图论子集

难度评级：2930

小提示：

对任意十一个连续整数，按禁差关系得到的图是一个 $11$ 环

Within any eleven consecutive integers, the forbidden-difference graph is an $11$ -cycle

大提示：

为构造达到上界的集合，寻找模 $11$ 的五个可选剩余类

For a matching construction, look for five allowable residue classes modulo $11$

解答：

在任意十一个连续整数中，若两数之差为 $4$ 或 $7$ ，就将它们相连。由于 $7=11-4$ ，所得图是一个 $11$ 环，其最大独立集的大小为 $5$ 。类似地，任意十个连续整数诱导出一条含十个顶点的路径，最多可贡献 $5$ 个元素。因为 $1989=179\cdot11+2\cdot10$ ，所以 $|S|\leq179(5)+2(5)=905$ 。

选取所有模 $11$ 的余数为 $1$ 、 $3$ 、 $4$ 、 $6$ 或 $9$ 的整数即可达到此上界。所选余数中任意两个在模 $11$ 意义下都不相差 $4$ 或 $7$ ，而从 $1$ 到 $1989$ 之间，这五个余数各出现 $181$ 次。因此最大值为 $5(181)=905$ 。

On any eleven consecutive integers, join two numbers when their difference is $4$ or $7.$ Because $7=11-4,$ this graph is an $11$ -cycle, whose largest independent set has size $5.$ Similarly, any ten consecutive integers induce a path on ten vertices and contribute at most $5.$ Since $1989=179\cdot11+2\cdot10,$ this gives $|S|\leq179(5)+2(5)=905.$

This bound is attained by taking every integer whose residue modulo $11$ is $1,$ $3,$ $4,$ $6,$ or $9.$ No two selected residues differ by $4$ or $7$ modulo $11,$ and each of these five residues occurs $181$ times from $1$ through $1989.$ Thus the maximum is $5(181)=905.$

1989 AIME 第 13 题

答案：905

难度评级：2930

小提示：

大提示：

解答：

其他年份的第 13 题