Question

一个房间里有 $N$ 个人，其中 $N\gt3$ ，且至少有一人没有与房间里的所有其他人握过手。房间里可能与所有其他人都握过手的人数最多是多少？

In a room containing $N$ people, $N\gt3,$ at least one person has not shaken hands with everyone else in the room. What is the maximum number of people in the room that could have shaken hands with everyone else?

$0$

$1$

$N-1$

$N$

以上都不是

none of these

答案：E

知识点：图论极端原理

难度评级：1780

小提示：

一次未发生的握手总会涉及两个人

A missed handshake always involves two people

大提示：

先求出上界，再用仅少一次握手的情形实现这个上界

Find an upper bound, then realize it by omitting just one handshake

解答：

若一人少握了一次手，那么这次未握手所涉及的另一人也没有与所有人握过手。因此，至多有 $N-2$ 人与所有其他人都握过手。让恰好两个人彼此不握手，而其余握手全部发生，就能达到这个上界。由于选项中没有 $N-2$ ，答案是“以上都不是”。

因此，正确答案是 E。

If one person has missed a handshake, the other person in that missed pair also has not shaken hands with everyone. Thus at most $N-2$ people can have shaken hands with everyone. This is attainable when exactly two people fail to shake hands with each other and every other handshake occurs. Since $N-2$ is not listed, the answer is “none of these.”

Therefore, the correct answer is E.

1978 AMC 12 第 16 题

答案：E

难度评级：1780

小提示：

大提示：

解答：

其他年份的第 16 题