# Ⅳ：抽屉原理简介
本文介绍**抽屉原理**（也叫**鸽巢原理**，Pigeonhole Principle）。
在之前的内容里，我们不少用到了抽屉原理的思想。
例如在融合待定数组里，我们知道因为有 $$n$$ 个单元格里要填入 $$n$$ 种不同的数字，因为数字不能出现重复项，因此每一种数字都必须出现恰好一次；更进一步地，由于存在 $$n$$ 种数字要填入到 $$n + 1$$ 个单元格里，所以为了确保数字均能填入，有一种数字必须出现两次才能满足条件。
另外，数组的显隐性互补里我们也知道，由于两个数组互补，他们只能位于同一个区域下，所以规格的和一定是小于等于 9 的。所以不论哪一个超过 5，则必有另外一侧互补的数组的规格小于 5，因此数组实际做题中是不存在五数组及以上规格的情况的。
这种用法参考和借鉴了抽屉原理的主旨思想。
## 基础定义
这个说法起源自**狄利克雷**（Dirichlet），就是提出那个狄利克雷函数的那个人。这个人是德国一名数学家，它最初将问题描述成这样：
若有 $$n$$ 个笼子和 $$n + 1$$ 只鸽子，如果所有的鸽子都会被关进鸽笼里的话，那么至少会有一个笼子里会有两只鸽子。
这个例子里，它是显然的。因为鸽子要关进去，每一个笼子都分配最少一只鸽子，怎么着都会剩下一只鸽子尚未归入笼子里。所以它必须放入任何一个已经有一只鸽子的笼子里去，所以这便就有了这个结论。
## 使用场景
### 问题 1：鸽巢原理推广
假设我们把前面的例子稍加改动。如有 $$n$$ 个笼子和 $$kn + 1$$ 只鸽子（其中 $$k$$ 是整数）。因为每一只鸽子都需要进笼，所以最次的分配方式是每一个笼子逐个让鸽子进去，一个一个地用完全部的笼子。用完之后继续让鸽子从第一个笼子开始，保证笼子内的鸽子数量尽量少地去分配。那么这样分配下来，$$kn$$ 只鸽子就刚好用完全部所有的笼子 $$k$$ 次。
于是，我们再多加一只鸽子进去，不论加在哪一个笼子，笼子里都会多一只鸽子。原本全部都是 $$k$$ 只，现在肯定就变成了 $$k + 1$$。所以，如果鸽子数量是 $$kn + 1$$ 的话，则必有至少一个笼子会有 $$k + 1$$ 只鸽子。
### 问题 2：发量问题
一个正常人的头发数量是 10 万根左右。倘若我们不让这个数过大（比如一个人有 100 万根头发什么的），那么，像是北京这样的城市里，由于人口数显然超过 100 万，所以必然能找得到两个人会有完全相同的发量。
### 问题 3：握手问题
如果有一个派对里有 $$n$$ 个人（假设 $$n \ge 2$$）。我们随意地让这些人进行两个人互相握手的操作。因为每一个人最终握手的次数都介于 $$\[0, n - 1]$$ 这个区间内（就是说要么不握手，要么跟 1 个人握，要么 2 个人握手，这么一直下去，最多可以是跟其他所有 $$n - 1$$ 人都握过手）。但是，总的人数却有 $$n$$ 个，所以至少会有两个人，他们跟别人握手的人数数量是一样的。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://sudoku.kazusa.tech/appendix/01-pigeonhole-principle.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.