鴿子洞原理

作者：由彭文博發表于書法時間：2020-01-01

1. 同餘模(Congruence modulo)

(例題1.1)

：（“費馬最小定理”）如果對於整數

有

$x^{3}+y^{3}=z^{3}$

，那麼這三個整數當中，至少有一個是七的倍數。

證明：如果方程

$x^{3}+y^{3}=z^{3}$

成立，那麼我們得到同餘方程

$x^{3}+y^{3}\equiv z^{3}\ (mod\ 7)$

，給定x的值為0，1，2，3，4，5，6，我們檢驗得到

$x^{3}\equiv 0,1,-1\ (mod\ 7)$

。

情形1：

$z^{3}\equiv 0\ (mod\ 7)$

，這意味著z是7的倍數。

情形2：

$z^{3}\equiv 1\ (mod\ 7)\Rightarrow x^{3}+y^{3}\equiv 1\ (mod\ 7)$

，唯一的組合方式為0和1。我們有

$x^{3}\equiv 0\ (mod\ 7)，y^{3}\equiv 1\ (mod\ 7)$

或者

$x^{3}\equiv 1\ (mod\ 7)，y^{3}\equiv 0\ (mod\ 7)$

，這兩種情況，要麼x是7的倍數，要麼y是七的倍數。

情形3：

$z^{3}\equiv -1\ (mod\ 7)$

，類似於情形2。

(例題1.2)

：令

，如果a和b為使得n=ab的正整數，證明a+b可以被24整除

證明：因為24=3

$\cdot$

8，並且3和8互質，所以我們證明a+b可以既可以被3也可以被8整除即可。

第一步：

$ab\equiv24k-1\equiv2 \ (mod\ 3)$

，所以只存在兩種可能：

$a\equiv1\ (mod\ 3) ，b\equiv 2 \ (mod\ 3)$

或者

$a\equiv 2\ (mod\ 3) ，b \equiv1\ (mod\ 3)$

，這兩種情況均意味著a+b可以被3整除。

第二步：

$ab\equiv24k-1\equiv7 \ (mod\ 3)$

，存在以下四種可能：

$a\equiv1\ (mod\ 8) ，b\equiv 7 \ (mod\ 8)$

，

$a\equiv3\ (mod\ 8) ，b\equiv 5\ (mod\ 8)$

，

$a\equiv5\ (mod\ 8) ，b\equiv 3 \ (mod\ 8)$

，

$a\equiv7\ (mod\ 8) ，b\equiv 1 \ (mod\ 8)$

，這四種情況均意味著a+b可以被8整除。

(引理1.3)

：如果

$n\in \mathbb{N}$

，那麼

$n\equiv f(n)\ (mod\ 9)$

（f（n）即為例題1。4的f（n））

(例題1.4)

：對於任意正整數n，定義f（n）為其每一位數字之和（f（1234）=1+2+3+4=10），（1）考慮整數序列 f（n），f（f（n）），f（f（f（n）））。。。，解釋為什麼序列最終一定會收斂為一個常數？（2）證明任意一對孿生素數之積出現在第一問中，一定會收斂到8。

證明：（1）透過觀察，對於任意大於或等於10的正整數m，我們有f（m）f（n）>f（f（n））>f（f（f（n）））。。。。因此，一個有下界的非遞增整數序列最終一定會收斂為常數。（2）這個序列的極限是1到9之間的某個數，所以證明該極限

$\equiv8\ (mod\ 9)$

就足夠了。此外，透過引理1。3，我們證明

$p(p+2)\equiv8\ (mod\ 9)$

就足夠了

方法1：由於p為質數，那麼

$p\equiv1\ (mod\ 3)$

或者

$p\equiv2\ (mod\ 3)$

。如果，

$p\equiv1\ (mod\ 3)$

，那麼

$(p+2)\equiv0\ (mod\ 3)$

，這與p+2為素數相矛盾。因此，

$p\equiv2\ (mod\ 3)\Rightarrow (p+1)\equiv 0\ (mod\ 3)\Rightarrow{(p+1)}^{2}\equiv 0\ (mod\ 9)$

$\Rightarrow {p}^{2}+2p+1\equiv 0\ (mod\ 9)\Rightarrow {p}^{2}+2p\equiv 8\ (mod\ 9) \Rightarrow p(p+2)\equiv8\ (mod\ 9)$

方法2：由於p為質數，那麼

$p\equiv1，2，4，5，7，8\ (mod\ 9)$

。此外，

$p\equiv1\ (mod\ 9)\Rightarrow p+2\equiv3\ (mod\ 9)，p\equiv4\ (mod\ 9)\Rightarrow p+2\equiv6\ (mod\ 9)，$

$p\equiv7\ (mod\ 9)\Rightarrow p+2\equiv0\ (mod\ 9)$

，因此

$p\equiv2，5，8\ (mod\ 9)$

。

$p\equiv2，5，8\ (mod\ 9) \Rightarrow p+2\equiv4，7，1\ (mod\ 9)\Rightarrow p(p+2)\equiv8\ (mod\ 9)$

(例題1.5)

：數字

$2^{29}$

是一個九位數，並且每一位數字均不一樣，這意味著缺少0到9中的其中一個數字，缺少的是哪一個？

解：定義缺少的那位數字為y，那麼根據引理1。3，我們有

$f(2^{29})=(\sum_{0}^{9}{x})-y=45-y\Rightarrow 2^{29}\equiv45-y\equiv -y \ (mod\ 9)$

，

$2^{3}=8\equiv(-1)\ (mod\ 9)\Rightarrow 2^{27}=(2^{3})^{9}\equiv (-1)^{9}\equiv(-1)\ (mod\ 9)$

，

$2^{29}=2^{27}\cdot 2^{2}\equiv(-1)\cdot4\equiv(-4)\ (mod\ 9)\Rightarrow x=4$

(例題1.6)

：證明方程

$x^{2}+y^{2}+z^{2}=2xyz$

在整數範圍內沒有除 x=y=z=0 之外的解。

證明：假設該方程有另外一個解，那麼

$x^{2}+y^{2}+z^{2}\equiv 0\ (mod\ 2)$

，因此

$x，y，z\equiv 0\ (mod\ 2)$

或者其中一個

$\equiv 0\ (mod\ 2)$

，另外兩個

$\equiv 1\ (mod\ 2)$

在不失一般性的情況下，假設

$x\equiv 0\ (mod\ 2)，y,z\equiv 1\ (mod\ 2)$

，我們有

$x^{2}\equiv0\ (mod\ 4),y^{2}\equiv1\ (mod\ 4),z^{2}\equiv1\ (mod\ 4)\Rightarrow x^{2}+y^{2}+z^{2}\equiv 2\ (mod\ 4)$

但是此時，

$2xyz\equiv0 \ (mod\ 4)$

，我們得到矛盾。

如果

$x，y，z\equiv 0\ (mod\ 2)$

，令

$x=2x_{1},y=2y_{1},z=2z_{1}\ (x_{1}.y_{1},z_{1}\in Z)$

，代入原方程得到

$4x_{1}^{2}+4y_{1}^{2}+4z_{1}^{2}=2\cdot8x_{1}y_{1}z_{1}\Rightarrow x_{1}^{2}+y_{1}^{2}+z_{1}^{2}=4x_{1}y_{1}z_{1}$

，用同樣的辦法，我們會得到

$x_{1},y_{1},z_{1}$

全為偶數，或者其中一個為偶數，剩下兩個為奇數，因此，我們有

$4x_{2}^{2}+4y_{2}^{2}+4z_{2}^{2}=4\cdot8x_{2}y_{2}z_{2}\Rightarrow x_{2}^{2}+y_{2}^{2}+z_{2}^{2}=8x_{2}y_{2}z_{2}$

。用同樣的辦法重複這一過程，我們最終會得到

$x_{k}^{2}+y_{k}^{2}+z_{k}^{2}=2\cdot 2^{k}x_{k}y_{k}z_{k}$

，直到

$x_{k},y_{k},z_{k}$

其中一個為偶數，另外兩個為奇數。這時，我們得到與之前相似的矛盾。

(引理1.7)

：如果

$x\in \mathbb{Z}$

，那麼

$x^{2}\equiv0 / 1\ (mod \ 4)$

並且

$x^{2}\equiv0 / 1/4\ (mod \ 8)$

(例題1.8)

：想象一個邊長為2米的正方形檯球桌。球被放入桌子的中心被擊中了，開始繞著桌子移動，撞在牆上直到它落在桌子四角的四個杯子中的一個。證明這個球走過的距離不是整數米。

這個問題需要一個有獨創性的想法。有趣的是，這樣一個幾何問題需要利用同餘模來解決。

證明：假設這個方形檯球桌位於一個非常大的房間（需要多大就有多大）。這個房間有一個標準的座標系統，當a和b是奇數時，直線x=a和y=b是可見的。這些線條在房間裡形成網格。假設臺球桌的中心是原點，那麼檯球桌的邊沿是x=1， x=-1， y=1和y=-1。

需要的原始思想如下：想象一下，除了在牆壁上實際反彈的球，還有一個虛構的球開始從桌面的中心沿著與實際的球相同的方向，但穿過牆壁，並且繼續沿著同一方向移動。假設它和實際的球以相同的速度移動。

圖1

當虛構的球分別到達直線x=a以及y=b時，實際的球正好分別擊中桌子的垂直邊以及水平邊，因為它們以相同的速度移動。因此，當虛構的球到達可見座標線的交點時，實際的球正好落在四個杯子中的一個。這樣的一個點有一個整數座標（a，b），並且a和b均為奇整數。實際的球所經過的距離與虛構的球此時與桌面中心的距離相等，也就是（0，0）與（a，b）之間的距離，這個距離等於

$\sqrt{a^{2}+b^{2}}$

。然而，因為a和b均為奇數，

$a^{2}+b^{2}\equiv1+1\equiv2\ (mod\ 4)$

。所以，根據引理1。7，

$a^{2}+b^{2}$

一定不是一個完全平方數。

(引理1.9)

：

$a,b\in N$

，那麼

$2^{b}\equiv 1\ mod\ (2^{a}-1)$

當且僅當

$a\ |\ b$

。

(例題1.10) [普特南 2018 B3]

：

$n\ |\ 2^{n}，n-1\ |\ 2^{n}-1，n-2\ |\ 2^{n}-2$

並且

$n<10^{100}$

，找到所有這樣的正整數

。

（第一步：確定整數n的特徵形式）由於

$n\ |\ 2^{n}$

，我們可以令

$n=2^{m}(0\leq m\leq n)$

。根據引理1。9，我們可以得到

$2^{m}-1\ |\ 2^{2^{m}}-1\Rightarrow m\ |\ 2^{m}$

，以及

$2^{m}-2\ |\ 2^{2^{m}}-2\Rightarrow 2^{m-1}-1\ |\ 2^{2^{m}-1}-1\Rightarrow m-1\ |\ 2^{m}-1$

，因此

$m\ |\ 2^{m}，m-1\ |\ 2^{m}-1$

。令

$m=2^{l}$

，重複上述過程，我們會得到

$l\ |\ 2^{l}$

。再令

$l=2^{k}$

，綜合以上，

$n=2^{2^{2^{k}}}$

，我們還需要確定k的取值範圍。

（第二步：確定整數k的取值範圍）

$n,n-1,n-2>0\Rightarrow n>2\Rightarrow 2^{m}>2\Rightarrow m>1\Rightarrow m\geq2$

$2^{m}=n<10^{100}<16^{100}=2^{400}\Rightarrow m<400\Rightarrow 2\leq m<400$

$2\leq 2^{l}<400\Rightarrow 1\leq l\leq8\Rightarrow 1\leq 2^{k}\leq8\Rightarrow 0\leq k\leq3$

2.鴿子洞原理(The Pigeonhole Principle)

(定義2.1)鴿子洞原理：

如果在n個盒子中放置超過n個物品，那麼必有一個盒子放置了至少兩個物品。

例如，如果你把四個球放在三個盒子裡，那麼就有一個盒子裡至少不止有一個球（至少有兩個球）。如果你把九個球放在四個盒子裡，那麼其中一個盒子裡至少不止有兩個球（至少有三個球）。還有一個更通用的原則：如果在n個盒子中放置超過kn個球，那麼其中一個盒子裡至少不止有k個球（至少有（k+1）個球）。

鴿子洞原理不需要進一步的解釋，但並不意味著大家總是清楚如何應用它。要把它應用到一個數學問題上，你必須決定什麼應該扮演盒子的角色，什麼應該扮演物品的角色。

(例題2.2)

：證明存在一個十進位制形式只有1整數（111111……）是2019的倍數。

證明：考慮下列整數：

（2019位數），將這些整數標記為球。用除以2019之後所得的餘數0，1，2，…… ，2018標記這些盒子。如果其中一個整數餘數為0，證明完成。如果不是，根據鴿子洞原理，這些數字中至少有兩個整數a和b （a>b），除以2019之後有相同的餘數，也就是a-b可以被2019整除。

$a-b=111...100...=111...1\cdot 10^{k}$

（k為整數b的位數）。因為10與2019互質，所以2019能被111。。。1 （（b-a）位數）整除。

(例題2.3)

：n人參加會議。證明他們中至少有兩人認識相同數量的人。（在這裡假設，如果X認識Y，那麼Y認識X）。

每個人都可能認識1到n個參會者，所以這道題看起來似乎不能應用鴿子洞原理。在應用鴿子洞原理之前，我們透過觀察得到一個結論：如果某人認識其他所有人，那麼每個人至少認識會議上的兩個人（他們自己和那個認識其他所有人的人）。因此，在這種情況下，每個人都認識2到n個參與者。否則，如果沒有人認識其他所有人，那麼每個人都認識1到n個參會者。讓我們來考慮這兩種情況。

情形1：某人認識其他所有人。將盒子標記為2到n的整數，將球標記為參會者的名字。如果參會者X認識m個參會者，則把標記為X的球放入標記為m的盒子中。因為有n個人出席了會議，我們有n個球。所以根據鴿子洞原理，至少有一個盒子內放置了兩個球。如果盒子m放置了標記為X和Y的球，那麼參會者X和Y認識相同數量的參與者。

情形2：沒有人認識其他所有人。將盒子標記為1到n-1的整數，將球標記為參會者的名字。剩下的論證與情形1相同。

(例題2.4)

：設X是由n個不同的整陣列成的集合。證明存在一個X的非空子集Y，使得Y中的元素之和可以被n整除。

令

$x_{1},x_{2},...,x_{n}$

是集合X中的整數，如果我們想應用鴿子洞原理，那麼很自然地把n個同餘類作為盒子。這確實是我們應該做的，但現在需要有一個原創的想法。對於每個子集Y，我們可以考慮它的元素的和。集合X有

$2^{n}-1$

個非空子集，所以我們用這種方法得到的整數遠遠大於n個。但是，並不能保證其中一個能被n整除。

實際上，我們不需要考慮集合X所有可能的子集，我們原創的想法是，考慮一個遞增子集鏈：

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ X_{1}\subset X_{2}\subset \cdot \cdot \cdot \subset X_{n}\subset X$

證明：令

$X_{i}={\left\{ x_{1},...,x_{i} \right\}}$

，若存在某一整數i，

$x_{1}+x_{2}+\cdot\cdot\cdot+x_{i}\equiv0\ (mod\ n)$

那麼證明完成。如果不存在，將整數和

$x_{1}+x_{2}+\cdot\cdot\cdot+x_{i}\ (i=1,...,n)$

標記為球，整數和除以n之後得到的餘數

標記為盒子。根據鴿子洞原理，至少有兩個球放置於同一盒子中，也就是

$x_{1}+x_{2}+\cdot\cdot\cdot+x_{j}\equiv x_{1}+x_{2}+\cdot\cdot\cdot+x_{i}\ (mod\ n)$

$(j>i)\Rightarrow x_{i+1}+x_{i+2}+\cdot\cdot\cdot+x_{j}\equiv0\ (mod\ n)\Rightarrow Y=\left\{ x_{i+1},x_{i+2},...,x_{j} \right\}$

下面來看一道與上面相似的競賽真題。

[普特南 2006 A2]

：證明對於每個由n個實陣列成的集合

$X={\left\{ x_{1},...,x_{i} \right\}}$

，存在一個

的非空子集

，和一個整數

使得

$|m+\sum_{s\in S}^{}{s}|\leq\frac{1}{n+1}$

證明：令

$S_{i}={\left\{ x_{1},...,x_{i} \right\}}$

，

$s_{i}=\sum_{s\in S_{i}}^{}{s}$

。考慮

$s_{i}$

的小數部分

，如果其中一個數

$s_{j}$

的小數部分在區間

$[0,\frac{1}{n+1})$

或者

$[\frac{n}{n+1},1)$

之中，那麼我們可以直接令

$m=-⌊s_{j}⌋$

或者

$-⌈s_{j}⌉$

。否則，這n個數的小數部分屬於n-1個

$[\frac{i}{n+1},\frac{i+1}{n+1})$

這樣的區間之中，其中

$1\leq i \leq n-1$

。根據鴿子洞原理，至少有兩個數的小數部分屬於同一區間，我們令這兩個數為

$s_{l}$

和

$s_{k}$

，那麼

$|\left\{ s_{l} \right\}-\left\{ s_{k} \right\}|\leq\frac{1}{n+1}$

，那麼令

$m=-⌊s_{l}⌋+⌊s_{k}⌋$

，此時

$S=S_{l}$

$S_{k}$

。

(例題2.5)

：證明存在三個絕對值小於

$10^{6}$

且不都為0的整數a，b，c使得

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |a+b\sqrt{2}+c\sqrt{3}|<10^{-11}$

證明：考慮所有形式為

$r+s\sqrt{2}+t\sqrt{3}$

的數

$(0\leq r,s,t\leq 10^{6}-1，r,s,t\in Z)$

一共有

$10^{18}$

這樣的數，且

$0\leq r+s\sqrt{2}+t\sqrt{3}< (1+\sqrt{2}+\sqrt{3})10^{6}<5\cdot 10^{6}$

，我們將區間

$[0,5\cdot 10^{6}]$

細分為

$(10^{8}-1)$

個長度相等的子區間。根據鴿子洞原理，其中一個子區間一定包含這樣形式的兩個數。如果這兩個數為

$r_{1}+s_{1}\sqrt{2}+t_{1}\sqrt{3}$

和

$r_{2}+s_{2}\sqrt{2}+t_{2}\sqrt{3}$

，那麼令

$a+b\sqrt{2}+c\sqrt{3}=(r_{1}+s_{1}\sqrt{2}+t_{1}\sqrt{3})-(r_{2}+s_{2}\sqrt{2}+t_{2}\sqrt{3})$

，也就是

$a=r_{1}-r_{2}，b=s_{1}-s_{2}，c=t_{1}-t_{2}$

，那麼

$|a+b\sqrt{2}+c\sqrt{3}|\leq\frac{5\cdot 10^{6}}{10^{18}-1}<\frac{10^7}{10^{18}}=10^{-11}$

下面這道題是一道與例題2。5很相似，但是沒有應用鴿子洞原理的競賽題。

[普特南 1980 A4]

：證明存在三個絕對值小於

$10^{6}$

且不都為0的整數a，b，c使得

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |a+b\sqrt{2}+c\sqrt{3}|>10^{-21}$

證明：由於

$|a|,|b|,|c|<10^{6}$

，所以

$|a\pm b\sqrt{2}\pm c\sqrt{3}|\leq |a|+|b|\sqrt{2}+|c|\sqrt{3}<10^{6}\cdot(1+2+2)<10^{7}$

令

$A_{1}=a+b\sqrt{2}+c\sqrt{3}，A_{2}=a-b\sqrt{2}+c\sqrt{3} \\A_{3}=a+b\sqrt{2}-c\sqrt{3}，A_{4}=a-b\sqrt{2}-c\sqrt{3}$

因為

$\sqrt{2},\sqrt{3},\sqrt{6}$

均為無理數，所以

$A_{1},A_{2},A_{3},A_{4}$

均不為零。考慮乘積

$P=A_{1}A_{2}A_{3}A_{4}$

為一個整數（乘在一起的表示式會消去根號），因此

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A_{1}\geq\frac{1}{|A_{2}A_{3}A_{4}|}>(10^{-7})^{-3}=10^{-21}$

(例題2.6)

：二維平面上的點以任意方式塗成紅色和藍色，證明存在一個頂點顏色相同的矩形。

方法一：考慮一條直線

上的七個點。根據鴿子洞原理，其中至少有四個是相同的顏色，我們令他們為紅色，並記為

$P_{1},P_{2},P_{3},P_{4}$

（實際上，也可以不用鴿子洞原理直接得到這個結論，因為一條直線上有無窮多個點。這裡提供一種應用鴿子洞原理的思路）。考慮兩條平行於直線

的直線

$l_{1},l_{2}$

以及點

$P_{1},P_{2},P_{3},P_{4}$

在直線

$l_{1},l_{2}$

上的正交投影點，我們將他們分別記為

$Q_{1},Q_{2},Q_{3},Q_{4}$

和

$R_{1},R_{2},R_{3},R_{4}$

（如圖2所示）。

圖2

如果

$Q_{1},Q_{2},Q_{3},Q_{4}$

（或

$R_{1},R_{2},R_{3},R_{4}$

）當中有兩個點為紅色，那麼我們可以得到四個頂點均為紅色的矩形。如果不是，那麼

$Q_{1},Q_{2},Q_{3},Q_{4}$

（和

$R_{1},R_{2},R_{3},R_{4}$

）當中至少有三個點的顏色為藍色，我們可以得到四個頂點均為藍色的矩形。

方法二：考慮三條水平的直線

$l_{1},l_{2},l_{3}$

，以及七條垂直的直線

$l_{A},l_{B},l_{C},l_{D},l_{E},l_{F},l_{G}$

。將球標記為七條垂直的直線

$l_{A},l_{B},l_{C},l_{D},l_{E},l_{F},l_{G}$

，將盒子標記為集合

$\left\{ l_{i},l_{j},color \right\}$

中的六個元素

$(i,j\in\left\{ 1,2,3 \right\},color\in\left\{ red,blue \right\})$

（如圖3所示）。

圖3

如果

$l_{X}\cap l_{i}$

與

$l_{X}\cap l_{j}$

$(X\in\left\{ A,B,C,D,E,F,G \right\})$

所得的兩個交點顏色均為Y

$(Y\in\left\{ red,blue \right\})$

，那麼將

$l_{X}$

放入盒子

$\left\{ l_{i},l_{j},Y \right\}$

中。根據鴿子洞原理，至少有兩個球放置於同一盒子之中，也就是

$l_{A},l_{B},l_{C},l_{D},l_{E},l_{F},l_{G}$

當中至少有兩條直線著色情況相同，那麼這兩條直線中的顏色相同且數量較多的點形成一個四個點顏色相同的矩形。

標簽：整數例題盒子證明鴿子

上一篇:怎麼樣才能把字練好 ?

下一篇：年是年，卻不是屬於我的年。

鴿子洞原理

猜你喜歡

再世追兇-第十章-隱藏的巨獸

我這需求，選擇廣電機頂盒還是智慧機頂盒？

《鴿子》春光同人

為什麼很少人像研究數論一樣研究別的環？

半小時解決高數上微分方程問題