9.2: Принцип «голубиного отвору»

Якщо у поштового перевізника є m листів для розподілу між n поштових скриньок (або «голубянок»)\(m > n\), причому, то зрозуміло, що хоча б в одну з поштових скриньок доведеться отримати більше однієї літери. Це важливе спостереження відоме як «Pigeonhole Принцип». (Див. Вправа\(9.3.6\) для підтвердження.) Мовою множин він може бути викладений наступним чином.

Пропозиція\(9.2.1\) (Pigeonhole Principle).

\(A_{1}, A_{2}, \ldots, A_{n}\)Дозволяти\(B\) і бути скінченними множинами. Якщо\[B \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n} ,\]

і\(\# B > n\), потім\(\# A_{i} \geq 2\), для деяких\(i\).

Ось кілька з багатьох застосувань принципу Pigeonhole. У цих реальних прикладах наші пояснення будуть трохи неформальними.

Приклад\(9.2.2\).

Шухляда для шкарпеток Боба має багато-багато шкарпеток, і вони випускаються в 4 кольорах. На жаль, світло в його кімнаті вигоріло, тому він нічого не бачить. Скільки шкарпеток він повинен захопити з шухляди, щоб він міг бути впевненим, що принаймні два з них одного кольору?

Рішення

Боб повинен захоплювати 5 (або більше) шкарпеток.

Щоб побачити це, зауважте, по-перше, що взяти 4 шкарпетки може бути недостатньо: якщо Боб схопить лише 4 шкарпетки, можливо, у нього є один носок кожного з 4 різних кольорів. Тоді у нього не було б двох шкарпеток одного кольору.

Тепер припустимо, що Боб хапає (як мінімум) 5 шкарпеток. Він може сортувати їх на 4 стопки, за кольором. Починаючи з 5 > 4, одна з паль повинна мати більше одного носка. Так що є (принаймні) 2 шкарпетки одного кольору.

Приклад\(9.2.3\).

Якщо підібрати 50 чисел від 1 до 98, то гарантовано, що два з них складуть рівно 99.

Рішення

Числа від 1 до 98 можна розділити на 49 голубиних отворів:\[\{1,98\},\{2,97\},\{3,96\}, \ldots,\{49,50\} .\]

(Таким чином, два різних числа\(x\) і\(y\) знаходяться в тому ж голубиному отворі, якщо\(x+y = 99\).) Починаючи з 50 > 49, два числа, які ми вибрали, повинні знаходитися в одній і тій же голубній лунці. Тоді сума цих двох чисел дорівнює рівно 99.

Приклад\(9.2.4\).

Якщо ви підберете 5 точок на поверхні (сферичного) апельсина, то завжди є спосіб розрізати апельсин рівно навпіл, таким чином, щоб принаймні 4 ваші точки були в одній половині. (Ми припускаємо, що будь-яка точка, яка точно знаходиться на розрізі, вважається належною обом половинам.)

Рішення

Будь-які дві точки будуть лежати на великому колі сфери, тому ми можемо вирізати апельсин так, щоб 2 точки були точно на розрізі. Решта 3 точки розподілені певним чином між двома половинами апельсина. За принципом Pigeonhole принаймні два з цих трьох точок знаходяться в одній половині. Тоді ця половина містить 2 точки на розрізі, плюс ці додаткові 2 бали, загалом (принаймні) 4 очок, які ви вибрали.

Вправа\(9.2.5\).

1. На ковзанці знаходиться десять чоловік, які грають в хокей. Поясніть, як ви знаєте, що двоє з них народилися в один день тижня.
2. Якщо в початковій школі 400 учнів, поясніть, як ви знаєте, що (принаймні) двоє з них мають однаковий день народження.
3. Якщо в компанії 700 співробітників, поясніть, як ви знаєте, що їх двоє з однаковими ініціалами. (Тобто їх імена починаються з однієї літери, а прізвища починаються з однієї літери.)
4. Відомо, що:
   • Ніхто не має більше 300 000 волосків на голові.
   • Понад мільйон чоловік проживає в Калгарі.
     Покажіть, що в Калгарі є дві людини, які мають рівно таку ж кількість волосків на голові.

На додаток до вищезазначених реальних прикладів, Принцип Pigeonhole має важливі застосування в теоретичній математиці.

Слідство\(9.2.6\).

Припустимо\(A\) і\(B\) є кінцевими множинами.

1. Якщо існує функція один-на-один\(f: A \rightarrow B\), то\(\# A \leq \# B\).
2. Якщо існує функція ono\(f: A \rightarrow B\), то\(\# A \geq \# B\).

Доказ

Нехай\(m = \# A\) і\(n = \# B\).

1. Припустимо,\(f: A \rightarrow B\) це один-на-один, і\(m > n\). Припустимо без втрати спільності\(B=\{1,2, \ldots, n\}\), що, так ми можемо дозволити\[A_{i}=f^{-1}(i) \quad \text { for } i=1,2, \ldots, n .\]
   Для будь-якого\(a \in A\), ми маємо\(a \in f^{-1}(f(a))=A_{f(a)}\), так\(a \in A_{1} \cup A_{2} \cup \cdots \cup A_{n}\). Оскільки\(a\) є довільним елементом\(A\), це має на увазі\(A \subset A_{1} \cup A_{2} \cup \ldots \cup A_{n}\). Тому що\(\# A = m > n\), ми робимо висновок, що\(\# A_{i} \geq 2\) для деяких\(i\). Це означає\(\# f^{-1}(i)>1\), що суперечить тому, що\(f\) є один-на-один.
2. Припустимо,\(f: A \rightarrow B\) є на, і\(m < n\). Немає ніякої шкоди в припущенні\(A=\{1,2, \ldots, m\}\), і тоді ми можемо дозволити\[B_{i}=\{f(i)\}\]
   \(i=1,2, \ldots, m\). Так як\(f\) це на, ми знаємо, для будь-якого\(b \in B\), є деякі\(i \in A\), такі, що\(f(i) = b\). Це означає\(b \in B_{i}\); отже,\(b \in B_{1} \cup B_{2} \cup \cdots \cup B_{m}\). Оскільки\(b\) є довільним елементом\(B\), це має на увазі\(B \subset B_{1} \cup B_{2} \cup \ldots \cup B_{m}\). Тому що\(\# B = n > m\), ми робимо висновок, що\(\# B_{i} \geq 2\) для деяких\(i\). Це суперечить тому, що\(\# B_{i} = 1\) (тому що\(B_{i}=\{f(i)\}\) має тільки один елемент).

Зауваження\(9.2.7\).

Замість\(9.2.1\) пропозиції багато математиків вважають\(9.2.6(1)\) контрапозитив слідства принципом голуба:

Якщо\(\# A > \# B\), то не існує функції один-на-один від\(A\) до\(B\).

Вправа\(9.2.8\).

1. Припустимо,\(A\) це набір з 10 натуральних чисел від 1 до 100 (включно). Показати, що дві різні підмножини\(A\) мають однакову суму. Наприклад, якщо\[A=\{2,6,13,30,45,59,65,82,88,97\} ,\]
   тоді підмножини\(\{6, 13, 45, 65\}\) і\(\{2, 30, 97\}\) обидві складають до 129. [Підказка: Порівняйте відповіді на два питання: Скільки підмножин\(A\) існує? Оскільки є всього 10 елементів\(A\), і всі вони є\(\leq 100\), скільки різних можливих сум існує?]
2. Покажіть, що якщо поставити 5 точок в рівносторонній трикутник довжиною сторони 2 см, то є дві точки, які знаходяться на відстані не більше 1 см один від одного. [Підказка: Розділіть трикутник на 4 рівносторонніх трикутника довжиною сторони 1 см.]
3. Цифри 1, 11, 111, 1111 і т.д. називаються репунітами. (Їх десяткове подання повністю складається з 1.) Покажіть, що деяка репуниця ділиться на 2017 рік. [Підказка: Якщо\(n \times 10^{k}\) ділиться на 2017 рік, для деяких\(k \in N\),\(n\) то ділиться на 2017 рік. Чому? ]
4. Покажіть,\(\# A\) що чітко визначено. Тобто якщо\(\# A = m\) і\(\# A = n\), для деяких\(m, n \in N\), то\(m = n\). [Підказка: Застосувати\(9.2.6\) наслідок\(B = A\).]
5. Шоу\(\mathbb{N}\) нескінченно. [Підказка: Доказ протиріччя. Застосувати наслідок\(9.2.6(1)\).]

Зауваження\(9.2.9\).

Ось два узагальнення принципу Pigeonhole, які часто корисні.

1. Якщо у поштового перевізника є\(m\) листи для розповсюдження по\(n\) поштових скриньках\(m > kn\), причому, то хоча б в одну з поштових скриньок доводиться отримувати більше, ніж\(k\) листів.
2. Припустимо, у оператора електронної пошти є\(m\) листи для розповсюдження серед\(n\) поштових скриньок. Якщо\[k_{1}, k_{2}, \ldots, k_{n} \in \mathbb{N} \text { and } m>k_{1}+k_{2}+\cdots+k_{n} ,\]
   тоді їх повинно бути таке\(i\), щоб в поштову\(i\) скриньку потрапляло більше, ніж\(k_{i}\) букв.

Вправа\(9.2.10\).

Стан (1) і (2) Зауваження\(9.2.9\) аналогічно:

1. Пропозиція\(9.2.1\) (тобто з точки зору набору,\(B\) що міститься в\(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\)), і
2. \(9.2.6(1)\)Слідство (тобто з точки зору функції\(f : A \rightarrow B\)).

Вправа\(9.2.11\).

1. Посилити висновок вправи\(9.2.5(4)\): показати є колекція з 4 людей в Калгарі, у всіх яких рівно однакова кількість волосків на голові.
2. Як і в прикладі\(9.2.2\), ящик для шкарпеток Боба має багато-багато шкарпеток, і вони бувають у 4 кольорах. Скільки шкарпеток він повинен захопити з шухляди, щоб він міг бути впевненим, що принаймні 12 з них одного кольору?
3. Шухляда для шкарпеток Бетті має 6 синіх шкарпеток, 10 червоних шкарпеток, 14 білих шкарпеток та 18 чорних шкарпеток. Скільки шкарпеток вона повинна захопити з шухляди, щоб вона могла бути впевнена, що принаймні 12 з них одного кольору?