手记

《计算机科学与数学》1.7 分情况证明

将一个复杂的证明拆分为多个情况,然后分别证明每种情况是一种共同的、有用的策略。有一个有趣的例子。

让我们一致同意给出任意两个人,要么见过,要么没见过。如果一组人中的每对人已经见过了,我们称该组为社团,如果一组人中的每对人没有见过,我们称该组为陌生人。

定理。每6个人的集合中包含3个人的社团或者3个陌生人群组。

证明。分情况分析(1)。用x表示六个人中的一个。有两种情况:

  1. 除了x之外的其他5个人中,至少3个人已经见过x。
  2. 其他5个人中,至少3个人没有见过x。

现在,我们必须确保至少两种情况中的一个一定成立(2),但那很简单:我们已经将5个人分成两组了,一组已经和x握过手了,另一组则没有,所以其中一组人至少拥有一半人。

‌ 情况一:假设至少3人已经见过x了。 ‌

该情况分为两种子案例: ‌

案例 1.1:那5个人没有一对人互相见过。那么这些人组成一个至少3 人的陌生人群组。该定理在此子案例中成立。

案例 1.2:那5个人存在某对人互相见过。那么这对人再加上x,组成一个3 人的社团群组。所以该定理在此子案例中成立。

这表明该定理在情况一中成立。

情况二:假设至少3人没有见过x。 ‌

该情况也分为两种子案例: ‌

案例 2.1:那5个人中两两之间互相见过。那么这些人组成一个至少3 人的社团群组。因此该定理在此子案例中成立。

案例 2.2:那5个人存在某对人没有互相见过。那么这对人再加上x,组成一个3 人的陌生人群组。所以该定理在此子案例中成立。

这表明该定理在情况二中成立,因此在所有情况下都成立。


(1)从开头描述你的方法有助于引导读者。

(2)案例分析论证的部分是表明你已经涵盖了所有案例。这通常是显而易见的,因为这两种情况的形式是“P”和“非P”。然而,上述情况并不是很简单地说明。

0人推荐
随时随地看视频
慕课网APP