math-ai/BlueMO

1{2    "source_file": "./raw_volume-zh/volume12/chapter2.tex",3    "problem_type": "calculation",4    "problem": "例5. 有一个团体会议,有 100 人参加.\n其中任意四个人都至少有一个人认识其他三人.\n问: 该团体中认识其他所有人的成员最少有多少?",5    "solution": "解:先把问题翻译成图论语言.\n把该团体的成员视为顶点, 其顶点全体记做 $V$. 对于任意两个顶点 $u, v$ 所代表的成员, 当且仅当彼此认识, 则在 $u, v$\n之间连一条边.\n得到一个含 100 个顶点的简单图 $G$. 已知条件是, 图 $G$ 中任意四个顶点中都至少有一顶点和其他三个顶点相邻.\n要求图 $G$ 中度为 99 的顶点个数的最小值 $m$.\n当图 $G$ 是完全图时, 每个顶点的度都是 99 , 所以有 100 个度为 99 的顶点.\n当图 $G$ 是非完全图时, 图 $G$ 中必有两个不相邻的顶点 $u$ 和 $v$. 显然 $d(u) \\leqslant 98, d(v) \\leqslant 98$. 因此图 $G$ 中度为 99 的点的个数 $l \\leqslant 98$.\n如果 $G$ 中除 $u$ 和 $v$ 外另有两个顶点 $x, y$ 不相邻, 则 $u, v, x$ 和 $y$ 中不存在和其他三个顶点都相邻的顶点, 与题意矛盾 (与图 $G$ 的性质矛盾). 因此 $G$ 中除 $u, v$ 外任意两个顶点相邻.\n这说明对 $G$ 中除 $u, v$ 外的任意点 $x$, 均有 $d(x) \\geqslant 97$.\n如果 $G$ 中除 $u 、 v$ 外的任何 $x$ 都和 $u, v$ 相邻, 则 $d(x)=99$. 此时 $G$ 中度为 99 的顶点个数为 98 .\n设 $G$ 中除 $u 、 v$ 外有个顶点 $x$ 和 $u 、 v$ 不都相邻, 则有 $G$ 的性质知, $G$ 中除 $u, v, x$ 外的任意顶点 $y$ 和 $u 、 v 、 x$ 都相邻.\n因此 $d(u) \\leqslant 98, d(v) \\leqslant 98$, $d(x) \\leqslant 98, d(y)=99$. 所以 $G$ 中度为 99 的顶点个数为 97 .\n这表明含 100 个顶点的简单图 $G$ 中, 如果任意四个顶点中必有一个顶点和其他三个顶点都相邻,那么 $G$ 中至少有 97 个度为 99 的顶点.\n回到原问题,即得: 该团体中认识其他所有人的成员最少是 97 个.",6    "remark": "注:例题中的成员数 100 改为任意的 $n$, 其他条件不变, 则结论为该团体至少有 $n-3$ 人认识其他所有人.",7    "figures": []8}