3.5.1 抽屉原理：视频

1. 公式
   观察依据

   幻灯片文字在“从 A 到 B 的满单射意味着 |A| ≤ |B|”和“不存在从 A 到 B 的满单射”中使用了 A。

2. 声音
   观察依据

   主讲人说：“从集合 A 到集合 B。”

A

映射规则中的源集合；通俗地说，对应鸽子的集合。

有限集合；幻灯片上未明确说明其确切的有限性假设。

1. 公式
   观察依据

   幻灯片文字在“从 A 到 B 的满单射意味着 |A| ≤ |B|”和“不存在从 A 到 B 的满单射”中使用了 B。

2. 声音
   观察依据

   主讲人说：“从集合 A 到集合 B。”

B

映射规则中的目标集合；通俗地说，对应鸽巢的集合。

有限集合；幻灯片上未明确说明其确切的有限性假设。

1. 公式
   观察依据

   幻灯片展示了 |A| ≤ |B| 和 |A| > |B| 中的 |A|。

2. 声音
   观察依据

   主讲人说：“集合 A 的大小。”

|A|

集合 A 的基数或大小。

对有限集合而言是非负整数；视频未明确说明其定义域。

1. 公式
   观察依据

   幻灯片展示 |B| 在 |A| ≤ |B| 和 |A| > |B| 中。

2. 声音
   观察依据

   主讲人说：“集合 B 的大小。”

|B|

集合 B 的基数（或大小）。

对有限集而言为非负整数；本视频未明确说明其定义域。

1. 公式
   观察依据

   幻灯片展示 |A| ≤ |B|。

2. 声音
   观察依据

   主讲人说：“小于或等于。”

≤

基数之间的小于或等于关系。

作用于数（或基数）上的序关系。

1. 公式
   观察依据

   幻灯片展示 |A| > |B|。

2. 声音
   观察依据

   主讲人说：“大于。”

>

基数之间的严格大于关系。

作用于数（或基数）上的序关系。

1. 公式
   观察依据

   幻灯片显示：“至少有两个鸽子！”

2. 声音
   观察依据

   主讲人说：“至少两只鸽子。”

≥ two

‘至少两只’用于描述一个鸽巢中鸽子的数量。

关于鸽巢中鸽子占据情况的计数陈述。

1. 公式
   观察依据

   幻灯片显示：“必须有≥2张花色相同的牌。”

2. 声音
   观察依据

   主讲人说：“至少两张花色相同的牌。”

≥ 2

‘至少两张牌’用于抽牌结论中。

关于多张牌共享同一花色的计数陈述。

1. 声音
   观察依据

   主讲人说：“如果你有五张牌，那么鸽子（即牌）的数量就多于洞（即花色）的数量。”

2. 图示
   观察依据

   幻灯片标题显示“5张牌抽取”；文字标签为“5张牌（鸽子）”和“4种花色（洞）”。

5 cards

第一个例子中被分配到各类别中的对象数量。

牌的数量，为正整数。

1. 声音
   观察依据

   主讲人在讨论将牌分配到花色时，提到了“花色，即洞”。

2. 图示
   观察依据

   画面显示四个蓝色U形容器，其下方标有花色符号。

4 suits

牌被分配进去的类别或盒子的数量。

类别的数量，为正整数。

1. 声音
   观察依据

   主讲人说：“假设我有十张牌”，随后讨论将十张牌分入四个槽位。

2. 图示
   观察依据

   幻灯片标题显示“10张牌抽取”；公式中分子为10。

10 cards

推广后的牌例中对象的数量。

牌的数量，为正整数。

1. 声音
   观察依据

   主讲人说：“如果我有 n 只鸽子。”

2. 图示
   观察依据

   幻灯片文字显示：“如果有 n 只鸽子和 h 个洞。”

n

待分配的鸽子或物体的一般数量。

物体的正整数个数

1. 声音
   观察依据

   主讲人将鸽巢原理介绍为一种计数原理，并陈述其简单形式。

2. 公式
   观察依据

   幻灯片文字为：“若鸽子数多于鸽巢数”，则“那么必有某个鸽巢中至少有两个鸽子！”

3. 动画
   观察依据

   五只鸽子图像出现在四个绿色U形鸽巢上方，随后鸽子飞入鸽巢，使得其中一个鸽巢内有两只鸽子。

视频将鸽巢原理呈现为一条显而易见的计数原理：若鸽子数量多于鸽巢数量，则至少有一个鸽巢中必须容纳两只或更多鸽子。图示示例使用了五只鸽子和四个鸽巢。

1. 鸽子数量多于鸽巢数量。

2. 结论指出：至少有一个鸽巢中包含 ≥ 两只鸽子。

1. 声音
   观察依据

   主讲人称，这是对之前已在映射规则中正式学过的命题的一种非正式表述。

2. 公式
   观察依据

   幻灯片文字显示：“映射规则：从 A 到 B 的满单射意味着 |A| ≤ |B|。”

1. 幻灯片并未明确说明 A 和 B 是有限集，但讲座上下文及基数比较暗示了它们是有限集。

幻灯片上展示的形式化映射规则指出：从集合 A 到集合 B 的满单射意味着 A 的基数小于或等于 B 的基数。主讲人将鸽巢原理表述为该规则的一种非正式版本。

1. 存在从 A 到 B 的满单射。

2. A 和 B 被视为其大小可作比较的集合。

1. 非正式的鸽巢原理

1. 声音
   观察依据

   主讲人说“对该命题取逆否命题”，并解释道：若 |A| > |B|，则不可能存在从 A 到 B 的满单射。

2. 公式
   观察依据

   虚线框内的幻灯片文字为：“若 |A| > |B|，则不存在从 A 到 B 的满单射。”

通过对映射规则取逆否命题，视频得到了形式化的鸽巢原理陈述：若集合 A 的大小大于集合 B 的大小，则不存在从 A 到 B 的满射单射。主讲人将此解释为：至少有两条箭头（即两只鸽子）必须落在同一个目标元素（即同一个鸽巢）中。

1. 假设映射规则：从 A 到 B 的满射单射蕴含 |A| ≤ |B|。

2. 采用逆否推理。

3. 通过基数比较集合 A 与 B。

1. 满单射的映射规则

1. 声音
   观察依据

   主讲人解释道：“没有满射单射，意味着不存在一种关系，使得 A 中每个元素都有一条向外的箭头，且 B 中每个元素至多接收一条向内的箭头。”

2. 声音
   观察依据

   主讲人进一步指出，若 A 中每个元素都有一条向外的箭头，则必然有至少两条箭头（即两只鸽子）指向 B 中的同一个鸽巢。

1. 该视频采用基于箭头的直观解释，而非对满射函数与单射函数给出完全形式化的定义。

主讲人用箭头描述满射单射：A 的每个元素都必须有一条向外的箭头，而 B 的每个元素至多接收一条向内的箭头。若 |A| > |B|，则为 A 的每个元素分配一条向外的箭头，必然迫使两条箭头进入 B 的同一个元素，这正对应鸽巢图景。

1. 箭头表示从 A 到 B 的一种关系或映射。

2. 满射性要求 A 的每个元素都有一条向外的箭头。

3. 单射性要求每个B中的元素至多有一条箭头指向它。

1. 满单射的映射规则
2. 映射规则的逆否形式

1. 声音
   观察依据

   主讲人提到一个简单的应用：如果我有五张牌，那么其中至少有两张牌花色相同。

2. 公式
   观察依据

   幻灯片文字显示：“示例：5张牌抽取”、“5张牌的集合：”以及“必有≥2张牌花色相同。”

3. 图示
   观察依据

   后续幻灯片标注“5张牌（鸽子）”和“4种花色（鸽巢）”，并在四个蓝色鸽巢下方分别展示四种花色符号。

1. 音频在“且如果”之后中断，因此本片段中未出现该抽牌示例的任何完整形式化证明语句。

视频将鸽巢原理应用于一组五张扑克牌。这五张牌被视为鸽子，而四种花色——黑桃、红心、方块、梅花——则被视为鸽巢。由于$5 > 4$，故至少有两张牌花色相同。

1. 该集合包含5张牌。

2. 相关的分类共有4种花色。

3. 每张牌按其花色归类。

1. 非正式的鸽巢原理
2. 映射规则的逆否形式

1. 声音
   观察依据

   主讲人解释道：若手上有五张牌、四种花色，将每张牌分配至一种花色，则至少有两张牌会被分入同一花色。

2. 图示
   观察依据

   五个牌位通过箭头映射至四个花色容器。

本片段将牌视作鸽子、花色视作洞穴。由于牌数多于花色数，因此将每张牌分配至一种花色时，必有至少两张牌落入同一花色。视觉化的映射使计数论证变得具体可感。

1. 每一张5张牌都恰好被分配至4种花色之一。

2. 该结论是一个确定的下界保证，而非针对某次特定随机抽取的陈述。

1. 声音
   观察依据

   主讲人提问：在10张牌中，能保证同花色的牌至少有多少张？并指出：若每个洞穴中都少于3张牌，则总牌数至多为8张。

2. 图示
   观察依据

   幻灯片依次显示“10张牌抽取”、“每个洞穴中 < 3张牌？”，然后是公式 $\lceil 10/4 \rceil = 3$。

将10张牌分配到4种花色中时，说话人推导出必有至少3张牌属于同一花色。其推理是：若每种花色所含牌数均少于3，则每种花色至多有2张牌，总计至多为8张，这与实际共有10张牌矛盾。等价地，平均每种花色的负载为$10/4$，因此必有某种花色达到或超过该平均值的下一个整数。

1. 总共有10张牌。

2. 共有4种花色作为分类类别。

3. 每张牌恰好属于一种花色。

4. 该结果是对所有可能分布情形都成立的确定性下界。

1. 基础鸽巢原理示例，含5张牌与4种花色。

1. 声音
   观察依据

   说话人说：“这些角括号表示向上取整，即取不小于该数的最小整数。”

2. 图示
   观察依据

   注释指向包裹着$10/4$的向上取整符号。

记号 $\lceil x \rceil$ 表示将实数 x 向上取整为最近的整数。本课中，它将每种花色的平均牌数$10/4$转化为整数下界3。

1. x 是一个实数。

2. 本视频中，x 是形如$10/4$或 $n/h$ 的比值。

1. 声音
   观察依据

   主讲人陈述一般规则：如果有 n 只鸽子和 h 个鸽巢，则至少有一个鸽巢中包含不少于 ⌈$n/h$⌉ 只鸽子。

2. 图示
   观察依据

   幻灯片标题为“广义鸽巢原理”，并显示公式。

当 n 个物体被分配到 h 个盒子中时，至少有一个盒子包含不少于 ⌈$n/h$⌉ 个物体。主讲人将 $n/h$ 解释为每个鸽巢的平均鸽子数，然后向上取整，因为鸽巢中的实际数量必须是整数。

1. n 和 h 是正整数。

2. 每只鸽子恰好被分配到一个鸽巢中。

3. 结论断言：至少存在一个鸽巢，其鸽子数量达到该下界。

1. 10张牌与4种花色的广义鸽巢原理计算
2. 广义鸽巢原理中使用的向上取整记号

1. 公式
   观察依据

   幻灯片显示文字“广义鸽巢原理”及公式“若〔n〕只鸽子与〔h〕个鸽巢，则必有某个鸽巢中至少有〔$\lceil n/h \rceil$〕只鸽子。”

2. 声音
   观察依据

   主讲人陈述：“鸽巢原理可表述为：至少有一个洞所含鸽子数大于或等于平均数。这就是广义鸽巢原理。”

广义鸽巢原理指出：若共有 n 只鸽子和 h 个鸽巢，则至少有一个鸽巢中所含鸽子的数量大于或等于每个鸽巢平均鸽子数（$n/h$）的上取整。

1. n 和 h 均为正整数

1. 声音
   观察依据

   主讲人陈述了鸽巢原理的简单形式。

2. 公式
   观察依据

   幻灯片文字写道：“若鸽子数多于鸽巢数，则必有某个鸽巢中至少有两只鸽子！”

如果鸽子数量多于鸽巢数量，那么至少有一个鸽巢中包含不少于两只鸽子。

1. 鸽子数量多于鸽巢数量。

存在性结论：某个鸽巢中鸽子数 ≥ 二。

1. 声音
   观察依据

   主讲人将此识别为其中一条映射规则。

2. 公式
   观察依据

   幻灯片文字显示：“映射规则：从 A 到 B 的满单射意味着 |A| ≤ |B|。”

1. 视频未明确说明 A 和 B 是否必须为有限集，但使用大小比较暗示了有限集。

如果存在从 A 到 B 的满单射，则 |A| ≤ |B|。

1. 存在从 A 到 B 的满单射。

2. A 和 B 是基数可比较的集合。

对所有满足该前提条件的集合 A 和 B 成立。

1. 声音
   观察依据

   主讲人说“对该命题取逆否命题”，并陈述所得条件。

2. 公式
   观察依据

   幻灯片文字显示：“若 |A| > |B|，则不存在从 A 到 B 的满单射。”

若 |A| > |B|，则不可能存在从 A 到 B 的满单射。

1. 集合 A 的元素个数大于集合 B 的元素个数。

对所有满足 |A| > |B| 的集合 A 和 B 成立。

1. 声音
   观察依据

   主讲人指出：一副五张牌的集合中，必有至少两张牌花色相同。

2. 公式
   观察依据

   幻灯片文字显示：“5张牌的集合：必有 ≥ 2张牌花色相同。”

3. 图示
   观察依据

   幻灯片将5张牌标记为“鸽子”，将4种花色标记为“鸽巢”。

1. 视频片段在主讲人说完“且如果”后尚未完成解释性句子时即结束。

任意5张扑克牌的集合中，必包含至少两张花色相同的牌。

1. 该集合包含5张卡片。

2. 卡片分为4种花色。

在由5张卡片构成的集合上使用全称量词；得出存在性结论：某种花色至少出现两次。

1. 声音
   观察依据

   主讲人总结道：“至少有两只鸽子在同一鸽巢中，至少有两张牌花色相同，也可能更多。”

2. 图示
   观察依据

   箭头表示多张牌指向同一个花色容器。

如果5张牌被分配到4种花色中，那么至少有一种花色包含不少于2张牌。

1. 共有5张牌。

2. 共有4种花色。

3. 每张牌恰好属于一种花色。

对于将5张牌分配到4种花色的任意方式，总存在一种花色，其包含的牌数至少为2张。

1. 声音
   观察依据

   说话人说：“我得把它们归拢起来，使得同一种花色的牌至少有三张。”

2. 图示
   观察依据

   公式表述为 ⌈$10/4$⌉ = 3。

若将10张牌分配到4种花色，则至少有一种花色包含至少3张牌。

1. 共有10张牌。

2. 共有4种花色。

3. 每张牌恰好属于一种花色。

对于将10张牌分配到4种花色的任意方式，总存在一种花色，其包含的牌数至少为3张。

1. 声音
   观察依据

   说话人用自然语言陈述该一般性定理。

2. 图示
   观察依据

   幻灯片展示广义公式。

若将 n 只鸽子分配到 h 个鸽巢中，则至少有一个鸽巢包含不少于 $\lceil n/h \rceil$ 只鸽子。

1. n 是一个正整数。

2. h 是一个正整数。

3. 每只鸽子恰好被分配到一个鸽巢中。

对于任意一种将 n 只鸽子分配到 h 个鸽巢的方式，总存在一个鸽巢，其中至少包含 $\lceil n/h \rceil$ 只鸽子。

1. 声音
   观察依据

   说话者从映射规则出发，并说“对该规则取逆否命题”。

2. 公式
   观察依据

   幻灯片同时展示了“从A到B的满单射意味着|A| ≤ |B|”以及“若|A| > |B|，则不存在从A到B的满单射”。

1. 公式

   $$\text{total injection from } A \text{ to } B \implies |A| \le |B|$$
   解释

   从幻灯片上显示的映射规则开始。

   步骤依据

   观察幻灯片上的公式及说话者对映射规则的陈述。

   视频直接表达
2. 公式

   $$|A| > |B| \implies \text{no total injection from } A \text{ to } B$$
   解释

   取逆否命题，从而得到本视频中所用的形式化鸽巢原理表述。

   步骤依据

   说话者明确说出“对该命题取逆否命题”；幻灯片在虚线框内展示了该逆否命题。

   视频直接表达
3. 公式

   $$\text{every element of } A \text{ has an outgoing arrow, but some element of } B \text{ receives two arrows}$$
   解释

   用箭头语言解释满单射的失败：若A的所有元素都必须映射出去，而B的元素更少，则必有两条箭头指向B的同一元素。

   步骤依据

   说话者将‘不存在满单射’解释为：不存在一种关系，使得A中每个元素都有一条向外的箭头、且B中每个元素至多只有一条向内的箭头；进而指出，B中必有至少两个箭头指向同一个鸽巢。

   视频直接表达

非正式的鸽巢原理被表述为全单射映射规则的逆否命题。

1. 声音
   观察依据

   主讲人提问“为什么？”，并回答：共有四种花色，即黑桃、红心、方块和梅花。

2. 公式
   观察依据

   幻灯片显示：“5张牌的集合：必有至少2张牌花色相同。”

3. 图示
   观察依据

   幻灯片标注：“5张牌（鸽子）”和“4种花色（鸽巢）。”

1. 最后的口语从句在“且如果”之后被截断，因此该片段未包含此推导过程的完整结尾句。

1. 公式

   $$\text{5 cards}$$
   解释

   将五张牌确定为被分配的对象。

   步骤依据

   幻灯片标注：“5张牌（鸽子）”，主讲人说：“如果我有一组五张牌。”

   视频直接表达
2. 公式

   $$\text{4 suits}$$
   解释

   将四类花色——黑桃、红心、方块和梅花——确定为分类依据。

   步骤依据

   主讲人依次说出四种花色；幻灯片标注：“4种花色（鸽巢）”，并展示四种花色符号。

   视频直接表达
3. 公式

   $$5 > 4$$
   解释

   比较牌的数量与花色的数量。

   步骤依据

   这正是‘鸽子数多于鸽巢数’这一情形的具体数值实例。

   依据视频推导
4. 公式

   $$\text{at least two cards have the same suit}$$
   解释

   得出结论：某一种花色中必然至少包含这五张牌中的两张。

   步骤依据

   这是此前视频片段中所述鸽巢原理的直接推论。

   视频直接表达

由于五张牌被分配到四种花色类别中，因此任意五张牌的集合中必有至少两张牌属于同一花色。

1. 声音
   观察依据

   主讲人从“每个鸽巢中少于三张牌”出发，通过反证法推理，得出“至多八张牌”，进而推出必有一个鸽巢中至少有三张牌。

2. 图示
   观察依据

   幻灯片显示问题：“每个鸽巢中少于3张牌？”随后给出公式 $\lceil 10/4 \rceil = 3$。

1. 公式

   $$$$
   解释

   假设（反证法）每种花色的牌数都少于3张。

   步骤依据

   这是主讲人明确检验的假设。

   视频直接表达
2. 公式

   $$$$
   解释

   由于牌的数量是整数，每种花色少于3张意味着每种花色至多有2张。

   步骤依据

   取整数值的计数使得“< 3”等价于“≤ 2”。

   依据视频推导
3. 公式

   $$4 \times 2 = 8$$
   解释

   共有4种花色，且每种花色至多有2张牌，则牌的总数至多为8。

   步骤依据

   将每洞最大数量乘以洞的个数，即可得到该假设下的最大总数。

   视频直接表达
4. 公式

   $$$$
   解释

   但实际上共有10张牌，与“所有花色都少于3张”的假设矛盾。

   步骤依据

   所假设的上界8小于给定的总数10。

   视频直接表达
5. 公式

   $$\left\lceil \frac{10}{4} \right\rceil = 3$$
   解释

   因此，必有某种花色至少包含3张牌；等价地说，平均值$10/4$向上取整后得到整数下界3。

   步骤依据

   说话者将$n/h$识别为每洞的平均鸽子数，并应用向上取整函数，因为最终结果必须是整数。

   视频直接表达

在任意 10 张牌分配给 4 种花色的情况下，至少有一种花色包含不少于 3 张牌。

1. 声音
   观察依据

   说话者指出$n/h$可理解为每洞的平均鸽子数，然后向上取整。

2. 图示
   观察依据

   幻灯片显示⌈$n/h$⌉为一般性上界。

1. 公式

   $$$$
   解释

   将 n 只鸽子分配到 h 个鸽巢中。

   步骤依据

   这是幻灯片和讲解中所陈述的设定。

   视频直接表达
2. 公式

   $$\frac{n}{h}$$
   解释

   计算每个鸽巢中的平均鸽子数量。

   步骤依据

   主讲人明确将 $n/h$ 解释为每个鸽巢的平均负载。

   视频直接表达
3. 公式

   $$$$
   解释

   不可能所有鸽巢的鸽子数都低于这个平均值，因此至少有一个鸽巢的鸽子数达到或超过该平均值。

   步骤依据

   这是主讲人所采用的平均值直觉。

   视频直接表达
4. 公式

   $$\left\lceil \frac{n}{h} \right\rceil$$
   解释

   由于鸽巢中的鸽子数量是整数，因此可保证的下界是该平均值的上取整。

   步骤依据

   主讲人指出，角括号表示向上取整到最近的整数。

   视频直接表达

至少有一个鸽巢包含不少于 $\lceil n/h \rceil$ 只鸽子。

1. 声音
   观察依据

   主讲人称这是鸽巢原理一个更为朴素的应用，并陈述了关于五张牌的断言。

2. 公式
   观察依据

   幻灯片标题为“例：5张牌抽取”，正文为“由5张牌组成的集合：其中必有≥2张牌花色相同。”

3. 图示
   观察依据

   幻灯片展示了五个标为‘鸽子’的牌占位符，以及四个分别标有黑桃、红心、梅花、方块的‘鸽巢’。

1. 视频在主讲人说完‘且如果’之后尚未完成最终解释性短语时即结束。

证明：任意一组5张扑克牌中，必有至少两张牌花色相同。

1. 存在一组5张牌。

2. 共有4种花色：黑桃、红心、方块、梅花。

3. 每张牌恰好属于一种花色。

证明至少有两张牌花色相同。

1. 公式

   $$\text{pigeons} = \text{5 cards}$$
   解释

   将这些牌视为要放入各类别中的物品。

   步骤依据

   幻灯片明确标注“5张牌（鸽子）”。

   视频直接表达
2. 公式

   $$\text{holes} = \text{4 suits}$$
   解释

   将花色视为鸽巢。

   步骤依据

   幻灯片明确标注“4种花色（鸽巢）”，并展示四种花色符号。

   视频直接表达
3. 公式

   $$5 > 4$$
   解释

   牌的数量多于花色的种类数。

   步骤依据

   依据题目所给数量进行的数值比较。

   依据视频推导
4. 公式

   $$\text{some suit contains } \ge 2 \text{ cards}$$
   解释

   根据鸽巢原理，至少有一个类别会收到两张或更多张牌。

   步骤依据

   应用本视频片段前文所述的非正式鸽巢原理。

   视频直接表达

五张牌中至少有两张花色相同。

幻灯片的视觉模型将5张牌（鸽子）放入4个花色鸽巢中，使该结论成为“鸽子数多于鸽巢数”的直接实例。

1. 声音
   观察依据

   主讲人引入了五张牌与四种花色的情形。

2. 图示
   观察依据

   幻灯片标题为“5张牌抽取”，并标注“5张牌（鸽子）”和“4种花色（鸽巢）”。

已知有5张牌和4种花色，关于同花色的牌，能保证什么结论？

1. 共有5张牌。

2. 共有4种花色。

3. 每张牌被分配到一种花色中。

求同一种花色中必然存在的最少牌数。

1. 公式

   $$$$
   解释

   将5张牌视为鸽子，将4种花色视为鸽巢。

   步骤依据

   幻灯片标注与旁白明确建立了这种对应关系。

   视频直接表达
2. 公式

   $$$$
   解释

   由于5大于4，将所有牌分配到花色中，必然导致至少一种花色中出现拥挤。

   步骤依据

   这是说话人所陈述的基本鸽巢原理比较。

   视频直接表达
3. 公式

   $$$$
   解释

   因此，至少有一种花色包含至少2张牌。

   步骤依据

   这是音频中说出的结论。

   视频直接表达

至少有2张牌具有相同的花色。

主讲人指出“可能更多”，确认2是每个分布都保证成立的下界，而非精确计数。

1. 声音
   观察依据

   主讲人提问：“假设我有十张牌……我至少能保证拿到多少张同花色的牌？”

2. 图示
   观察依据

   幻灯片标题为“10张牌抽取”，随后显示 $\lceil 10/4 \rceil = 3$。

已知有10张牌和4种花色，问某种花色中至少能保证有多少张牌？

1. 共有10张牌。

2. 共有4种花色。

3. 每张牌恰好属于一种花色。

求某种花色中必然达到的最大整数下界。

1. 公式

   $$$$
   解释

   询问是否可能在每种花色中都少于3张牌。

   步骤依据

   幻灯片明确提出问题：“每种花色都少于3张牌？”。

   视频直接表达
2. 公式

   $$4 \times 2 = 8$$
   解释

   如果每种花色都少于3张牌，那么每种花色至多有2张，总共至多有8张牌。

   步骤依据

   这是讲师所作的反证法论述。

   视频直接表达
3. 公式

   $$$$
   解释

   但共有10张牌，因此该假设不成立。

   步骤依据

   10超出了假设下允许的最大值8。

   视频直接表达
4. 公式

   $$\left\lceil \frac{10}{4} \right\rceil = 3$$
   解释

   因此，某种花色中至少包含3张牌；等价地说，对平均值$10/4$向上取整。

   步骤依据

   幻灯片上的公式与讲解均指出了向上取整这一步骤。

   视频直接表达

至少有3张牌具有相同的花色。

主讲人补充道：‘当然，你可以验证我无需再多取任何一张牌’，表明3在此设定下是精确的、可保证的下界。

1. 图示
   观察依据

   标题页显示“计算机科学中的数学”、“麻省理工学院$6.042J/18.062J$”以及“鸽巢原理”，底部署名阿尔伯特·R·迈耶与四月24日，2013年。

1. 标题文字

2. 课程标识符

3. 主讲人姓名与日期

4. 小窗口摄像头画面

5. 鼠标光标

1. 静态标题页在主讲人介绍主题时显示。

1. 数学内容仅通过口头讲解引入；此时尚未展示任何公式。

本段确立本次讲座的主题为抽屉原理。

1. 动画
   观察依据

   文字分阶段出现：“若鸽子数量更多”，随后出现五只鸽子图像，接着出现“而鸽巢数量更少”，再出现四个绿色U形鸽巢。

2. 动画
   观察依据

   约在14秒时，幻灯片切换为“则必有某个鸽巢中至少有两只鸽子！”，同时五只鸽子被分配到四个鸽巢中，其中一个鸽巢内有两只鸽子。

1. 五只鸽子的图片

2. 四个绿色U形鸽巢

3. 文字：“如果鸽子数量多于鸽巢数量，”

4. 文字：“那么必有某个鸽巢中至少有两只鸽子！”

1. 鸽子首先出现在空鸽巢上方。

2. 随后鸽子向下移动进入四个鸽巢。

3. 其中一个鸽巢最终容纳了两只鸽子，其余每个鸽巢各容纳一只鸽子。

1. 鸽子的数量始终保持为5。

2. 鸽巢的数量始终保持为4。

该动画直观地展示了：将5个物体分配到4个容器中，必然导致至少一个容器中包含2个物体。

1. 图示
   观察依据

   幻灯片显示：“映射规则：从A到B的满单射意味着|A| ≤ |B|。”

2. 图示
   观察依据

   一个虚线粉色框内写着：“若|A| > |B|，则不存在从A到B的满单射。”

1. 集合符号 A 和 B

2. 基数记号 |A| 和 |B|

3. 不等号 ≤ 和 >

4. 围绕逆否命题语句的虚线框

1. 此前的鸽子动画被形式化的集合映射记号所取代。

2. 虚线框突出了逆否命题形式。

1. 该幻灯片同时保持原始映射规则及其逆否命题可见。

视觉过渡将非形式化的鸽巢图示与关于满单射及基数的正式陈述联系起来。

1. 图示
   观察依据

   标题为“例：5张牌抽取”的幻灯片显示“5张牌的集合：”及一手五张扑克牌。

2. 公式
   观察依据

   文字出现：“必有 ≥ 2 张同花色的牌。”

3. 图示
   观察依据

   下一张幻灯片标注“5张牌（鸽子）”，含五个蓝色牌占位符；以及“4种花色（鸽巢）”，含四个蓝色U形鸽巢，分别位于黑桃、红心、梅花和方块符号上方。

1. 第四张牌的花色符号在采样视图中被右上角的网络摄像头小窗部分遮挡，但说话人明确指出是方块，且后续布局也表明共有四种花色。

1. 五张扑克牌占位符

2. 四个花色孔

3. 黑桃符号

4. 红心符号

5. 梅花符号

6. 方块符号

7. 文字“5张牌（鸽子）”

8. 文字“4种花色（洞）”

1. 该例题首先陈述关于五张牌的结论。

2. 然后将牌重新表述为鸽子，将花色重新表述为洞。

3. 鼠标光标指向花色孔附近，同时讲解者报出各花色名称。

1. 在整个示例中，始终存在5张牌对象和4种花色类别。

该示例将抽象的鸽巢结构映射到扑克牌上：牌是鸽子，花色是鸽巢。

1. 图示
   观察依据

   五张浅蓝色牌占位符位于四个标有花色符号的蓝色U形容器上方；箭头从牌指向容器。

1. 5张牌占位符

2. 4个花色容器

3. 黑桃、红心、梅花、方块符号

4. 箭头

1. 从卡片行向下画出箭头，指向花色容器。

2. 多个箭头表示可能有多张卡片落入同一个容器中。

1. 在整个片段中，始终剩余5张卡片和4种花色。

2. 分配模型是一张卡片对应一种花色。

该图示直观呈现了鸽巢原理的设定：将物体放入比物体数量更少的类别中，从而必然导致重叠。

1. 图示
   观察依据

   画面切换至“10张牌抽取”，随后显示问题“每个洞中少于3张牌？”，接着出现公式$\lceil 10/4 \rceil = 3$，并附有对向上取整符号的说明。

1. 标题“10张牌抽取”

2. 问题文字：“每个洞中少于3张牌？”

3. 四个花色容器

4. 公式$\lceil 10/4 \rceil = 3$

5. 注释：“向上取整，即向上舍入”

1. 幻灯片首先提出问题：是否每个洞中的卡片数都少于3张？

2. 随后，该问题被替换为已计算出的下界公式。

3. 一条注释指向向上取整符号，解释其含义。

1. 花色总数仍为4种。

2. 卡片总数仍为10张。

视觉序列展示了从直观的矛盾性问题，到使用向上取整函数的紧凑通用公式的演进过程。

1. 图示
   观察依据

   最后一张幻灯片标题为“广义鸽巢原理”，并以符号形式展示该原理，含变量 n、h 和 $\lceil n/h \rceil$。

1. 标题：“广义鸽巢原理”

2. 变量 n 和 h

3. 公式 $\lceil n/h \rceil$

1. 具体的卡片示例被一个完全符号化的陈述所取代。

1. 结构与前面的例子一致：将对象分配到盒子中，且某个盒子有下限约束。

最后一张幻灯片将前述数值例子抽象为一般性定理。

1. 图示
   观察依据

   一张静态幻灯片，左上角展示一个带编号的网格图，右下角显示主讲人的网络摄像头画面，中间呈现广义鸽巢原理的定义。

1. 文字

2. 公式

3. 网格图

4. 网络摄像头画面

1. 此时间段内幻灯片内容保持静止

画面呈现该原理的正式数学表述，与主讲人讲解内容一致。

1. 图示
   观察依据

   屏幕变为黑色，中央显示白色文字“幻灯片放映结束，单击退出。”，并显示鼠标光标。

1. 黑色背景

2. 白色文字

3. 鼠标光标

表示本视频片段结束。

1. 声音
   观察依据

   讲解者称鸽巢原理“实际上只是对我们早已正式学过的某个结论的一种非正式表述”，随后又说：“因此我们其实早已知道这条规则。”

有人可能因鸽子与鸽巢的表述听起来不够严谨，而将鸽巢原理视作一个独立且令人惊讶的定理。

视频阐明：这一非正式的鸽巢陈述，实为已知映射规则的逆否命题——即从 A 到 B 的满单射意味着 |A| ≤ |B|。

1. 声音
   观察依据

   讲解者用箭头来定义满单射的失败：不存在一种关系，使得 A 中每个元素都有一条向外的箭头，且进入 B 的每条箭头至多只有一条。

1. 该解释采用直观的、基于箭头的方式，而非对函数与单射给出完全形式化的定义。

有人可能认为，“不存在满单射”仅意味着 A 中某些元素缺少向外的箭头。

视频强调：若 A 中每个元素都必须有向外的箭头，而 B 的元素个数更少，则单射必然失败，因为至少有两条箭头会进入 B 的同一个元素。

1. 声音
   观察依据

   主讲人说：“它们不可能全都低于平均值。”

人们可能认为每个抽屉所含物品数都可少于平均值 〔$n/h$〕。

主讲人明确否定了这种可能性：如果所有鸽巢的鸽子数都低于平均值，则总数无法达到 n，因此至少有一个鸽巢的鸽子数必须达到或超过平均值，从而达到向上取整后的值。

1. 声音
   观察依据

   主讲人澄清道：“这些角括号表示向上取整到最近的整数。”

2. 图示
   观察依据

   注释将这些括号标注为“上限符号，表示向上取整”。

学习者可能将 〔$n/h$〕误读为普通分组符号或向下取整。

视频将该括号定义为上限运算，即向上取整到最近的整数；这一定义对于将平均值转化为有效的整数下界至关重要。

1. 声音
   观察依据

   主讲人指出，非正式的鸽巢原理是一种将映射规则中形式化内容通俗表达的方式。

2. 公式
   观察依据

   幻灯片将鸽子动画替换为文字：“映射规则：从 A 到 B 的满单射意味着 |A| ≤ |B|。”

视频将非正式的鸽巢原理呈现为对满单射映射规则的非正式表述。

1. 声音
   观察依据

   主讲人说：“对该命题取逆否命题。”

2. 公式
   观察依据

   虚线框内写着：“若 |A| > |B|，则不存在从 A 到 B 的满单射。”

形式化的鸽巢原理是通过对映射规则取逆否命题而得到的。

1. 声音
   观察依据

   主讲人通过从 A 指向 B 的箭头图示，并展示两条箭头指向 B 中同一元素，来解释“不存在满单射”的含义。

箭头图示揭示了逆否命题中“不存在从 A 到 B 的满单射”的具体含义。

1. 声音
   观察依据

   主讲人引入“鸽巢原理一个更为朴素的应用”，并将其应用于五张牌与四种花色的情形。

2. 图示
   观察依据

   幻灯片将5张牌标记为鸽子，将4种花色标记为鸽巢。

五张牌的例子通过将牌视为较大集合的元素、将花色视为较小集合的元素，应用了形式化的鸽巢原理。

1. 公式
   观察依据

   牌面幻灯片显示：“必有 ≥ 2 张牌花色相同。”

2. 图示
   观察依据

   该视觉模型直接对应此前的“五只鸽子、四个洞”动画。

卡片示例是如下非正式表述的一个具体特例：5张牌多于4种花色，因此至少有一种花色包含至少两张牌。

1. 声音
   观察依据

   主讲人将10张牌的情形称为5张牌情形的“稍作推广”。

2. 图示
   观察依据

   幻灯片内容从“5张牌抽取”逐步过渡到“10张牌抽取”。

10张牌的例子将鸽巢原理中最小情形（5个物体放入4个盒子）所用的相同推理，推广至需取平均负载上取整的更大情形。

1. 声音
   观察依据

   主讲人从具体的10张牌计算，过渡到“更一般地，若我有n只鸽子……”。

2. 图示
   观察依据

   最后一张幻灯片以符号形式陈述了广义鸽巢原理。

10张牌、4种花色的结果，对应于一般定理 ⌈$n/h$⌉ 中 $n=10$、$h=4$ 的特例。

1. 声音
   观察依据

   主讲人在陈述一般公式前，刚刚定义了上取整符号。

2. 图示
   观察依据

   该定理使用了 ⌈$n/h$⌉。

理解上取整符号，是正确解读广义鸽巢原理界限的前提。

1. 声音
   观察依据

   主讲人陈述鸽巢原理的简单形式。

2. 公式
   观察依据

   幻灯片文字给出该原理的非正式表述。

1. 非正式的鸽巢原理

1. 动画
   观察依据

   五只鸽子被分配到四个洞中，其中有一个洞容纳了两只鸽子。

1. 非正式的鸽巢原理
2. 五只鸽子与四个鸽巢的动画演示

1. 声音
   观察依据

   主讲人指出，鸽巢原理是非正式地表达了一条映射规则，并取其逆否命题。

2. 公式
   观察依据

   幻灯片展示了该映射规则及其逆否命题。

1. 满单射的映射规则
2. 映射规则的逆否形式
3. 通过取逆否命题推导形式化的鸽巢原理。

1. 声音
   观察依据

   主讲人通过从集合 A 出发的箭头、以及至多一个箭头指向集合 B 中每个元素的方式，解释不存在完全单射。

1. 满射单射的箭头解释
2. 映射规则的逆否形式

1. 声音
   观察依据

   主讲人指出，任意五张牌组成的集合中，至少有两张牌花色相同。

2. 图示
   观察依据

   幻灯片将5张牌标记为鸽子，将4种花色标记为鸽巢。

1. 五张牌抽取的应用
2. 例：5张牌抽取
3. 将鸽巢原理应用于五张牌

1. 图示
   观察依据

   幻灯片明确标注“5张牌（鸽子）”和“4种花色（鸽巢）”。

1. 五张牌抽取的应用
2. 五张牌抽牌可视化模型

1. 声音
   观察依据

   主讲人解释：5张牌与4种花色必然导致至少两张牌属于同一花色。

2. 图示
   观察依据

   标题为“5张牌抽取”的幻灯片，将牌映射到花色。

1. 基础鸽巢原理示例，含5张牌与4种花色。
2. 五张牌中至少有两张花色相同。
3. 示例：5张牌抽取

1. 声音
   观察依据

   主讲人通过反证法和对 10 张牌计算 $10/4$ 的向上取整，推导出该界。

2. 图示
   观察依据

   幻灯片显示 $\lceil 10/4 \rceil = 3$。

1. 10张牌与4种花色的广义鸽巢原理计算
2. 十张牌中，至少有三张牌花色相同。
3. 推导10张牌的鸽巢原理下界
4. 示例：10张牌抽取

1. 声音
   观察依据

   主讲人指出角括号表示向上取整至最近的整数。

2. 图示
   观察依据

   注释将该括号标注为“上取整，即向上取整”。

1. 广义鸽巢原理中使用的向上取整记号
2. 混淆上限符号与普通圆括号或下限符号

1. 声音
   观察依据

   主讲人陈述了n只鸽子与h个鸽巢的一般规则。

2. 图示
   观察依据

   幻灯片标题为“广义鸽巢原理”，并附公式 $\lceil n/h \rceil$。

1. 广义鸽巢原理
2. 广义鸽巢原理的下界
3. 从平均负载到广义鸽巢原理的上界

1. 公式
   观察依据

   广义鸽巢原理的公式被展示。

1. 广义鸽巢原理定义