Математичні парадокси

Словник / Принцип Діріхле

Словник · принцип Діріхле

Ніхто не рахував, а збіг гарантовано?

Зазвичай, щоб сказати щось напевно про мільйони людей, їх треба порахувати або хоча б опитати вибірку, і тоді «напевно» перетворюється на «найімовірніше». Принцип Діріхле дає справжню гарантію без жодного підрахунку: якщо речей більше, ніж скриньок, у якійсь скриньці опиниться щонайменше дві. Звучить як дрібниця, яку знає кожна дитина. Проте з цієї дрібниці випливають твердження, які здаються неможливими: про волосся киян, шкарпетки в темряві й файли, які не стисне жоден архіватор.

На пальцяхкартинки, аналогії, маленькі числа

Шар «На пальцях» приховано на всіх задачах.

Волосини киян

У Києві близько трьох мільйонів мешканців. На голові в людини зазвичай 100–150 тисяч волосин, у когось більше, у когось менше, а в лисих нуль. Рахувати їх ніхто не збирається.

Чи можна, не порахувавши жодної волосини, стверджувати, що в Києві є двоє людей з рівно однаковою кількістю волосин на голові?

Спробуйте уникнути збігу

Ось скриньки і на один предмет більше, ніж скриньок. Кладіть предмети по одному, натискаючи на скриньку, і намагайтеся, щоб жодні два не опинилися разом. Ви керуєте кожним кроком, і жодна випадковість вам не заважає.

5

Найхитріша стратегія лише відкладає збіг до останнього предмета, а скасувати його не може. Зверніть увагу й на кнопку «Покласти навмання»: коли предмети падають випадково, двоє в одній скриньці зазвичай опиняються набагато раніше. Гарантія і шанс — різні речі, і нижче ми їх порівняємо.

Шкарпетки в темряві

У шухляді впереміш 10 чорних і 10 білих шкарпеток. Світла немає, на дотик вони однакові. Ви витягаєте шкарпетки навпомацки, не повертаючи назад.

Скільки шкарпеток треба витягти, щоб напевно мати пару одного кольору?
А щоб напевно мати пару саме чорних?

Обидві відповіді дає той самий прийом: уявіть найневдаліший розклад і порахуйте, скільки шкарпеток він може «з'їсти» без пари. Скриньки тут — кольори. Двох кольорів досить, щоб двоє з трьох шкарпеток збіглися. А для чорної пари скринька лише одна, і найгірший випадок спершу віддає вам усі десять білих.

Строготаблиці, графіки, формули

Шар «Строго» приховано на всіх задачах.

Що таке принцип Діріхле

Принцип Діріхле: якщо N предметів розкласти по k скриньках і N більше за k, то в якійсь скриньці опиниться щонайменше два предмети. Загальніше: у якійсь скриньці буде щонайменше ⌈N/k⌉ предметів, тобто N/k, округлене вгору. Доведення в один рядок: якби в кожній скриньці було менше, усього предметів набралося б менше за N.

⌈2 952 301 / 1 000 000⌉ = ⌈2,95…⌉ = 3 кияни з однаковою кількістю волосин · ⌈3 / 2⌉ = 2 шкарпетки одного кольору з трьох · ⌈13 / 12⌉ = 2 людини з одним місяцем народження з тринадцяти

  • Гарантія, а не ймовірністьПринцип не каже «скоріше за все». Він каже «завжди», за будь-якого розкладу, навіть найхитрішого. Тому його беруть, коли треба відповісти на питання з «напевно» чи «в найгіршому випадку».
  • Головне — вибрати скринькиСам принцип очевидний, вся хитрість у тому, що назвати скриньками: кількість волосин, кольори, дні року, результати експерименту. Вдало вибрані скриньки роблять неймовірне твердження тривіальним.
  • Доказ неможливостіЯкщо різних варіантів більше, ніж різних результатів, які ви можете побачити, два варіанти дадуть однаковий результат, і ви їх не розрізните. Так рахують, скільки щонайменше потрібно зважувань, аналізів чи питань, ще до того, як придумали сам спосіб.
  • Існує, але де — невідомоПринцип доводить, що збіг є, але не показує, де саме. Знайти двох киян з однаковим волоссям він не допоможе. Математики називають такі доведення неконструктивними.

Гарантія проти шансу

Принцип Діріхле каже, коли збіг стає неминучим. Але коли предмети падають навмання, збіг зазвичай трапляється раніше. Візьмемо 12 скриньок — місяці року. Серед 13 людей двоє гарантовано народилися в одному місяці. А з якої людини збіг місяців з'являється насправді, якщо брати людей навмання? Симуляція кидає предмети у випадкові скриньки, доки двоє не опиняться разом, і повторює це 10 000 разів.

12

частка дослідів, у яких перший збіг на цьому предметігарантія: N = скриньок + 1
Гарантія
У середньому збіг на
Збіг ще до гарантії

Різниця між стовпчиками й пунктиром — це різниця між двома питаннями. «Скільки треба, щоб збіг був неминучим?» розв'язує принцип Діріхле, і відповідь — завжди скриньки плюс один. «Скільки треба, щоб збіг був імовірним?» — питання теорії ймовірностей, і відповідь там набагато менша, бо пар, які можуть збігтися, стає дуже багато дуже швидко.

Де працює принцип Діріхле

  • Дні народженняДнів у році з 29 лютого 366, тож серед 367 людей двоє гарантовано мають спільний день народження. Скільки людей досить, щоб збіг був просто ймовірним, — окрема задача, і її відповідь дивує більшість.
  • АрхіваториЖоден архіватор без втрат не може стиснути кожен файл. Файлів завдовжки 8 біт 256, а всіх коротших рядків, від порожнього до 7-бітного, лише 1 + 2 + 4 + … + 128 = 255. Якби кожен файл став коротшим, два різні файли отримали б однаковий архів, і розпакувати обидва не вийшло б. Тож якщо архіватор щось стискає, якісь інші файли він мусить робити довшими.
  • Хеші й пароліХеш-функція SHA-256 перетворює будь-який файл на число з 256 біт. Файлів можливо нескінченно багато, а чисел скінченна кількість, тож різні файли з однаковим хешем гарантовано існують. Проте знайти бодай одну таку пару для SHA-256 досі нікому не вдалося: скриньок 2²⁵⁶. Для старішої SHA-1 з 160 біт таку пару 2017 року показали Google і нідерландський інститут CWI.
  • Скільки треба перевірокКожен аналіз чи зважування має кілька можливих результатів, а кілька перевірок дають скінченну кількість різних «історій». Якщо підозрюваних більше, ніж історій, двох із них не розрізнити за жодного плану. Так у задачах про отруєне вино і фальшиву монету рахують нижню межу ще до того, як придумали розв'язок.
Глибшеузагальнення, теорія, історія

Шар «Глибше» приховано на всіх задачах.

Двоє з однаковою кількістю друзів

У будь-якій компанії з двох і більше людей знайдуться двоє, що мають однакову кількість друзів у цій компанії. Це правда для будь-якої компанії: шкільного класу, відділу, гостей на весіллі. Скриньки — можливі кількості друзів. У компанії з n людей кожен може дружити з 0, 1, …, n − 1 іншими: n скриньок на n людей, начебто збігу може й не бути. Але скриньки 0 і n − 1 не можуть бути зайняті водночас: якщо хтось дружить з усіма, то ні в кого немає нуля друзів. Тож насправді скриньок n − 1, а людей n.

Шестеро гостей і десять чисел

  • Троє знайомих або троє незнайомихСеред будь-яких шести людей є троє попарно знайомих або троє попарно незнайомих. Візьміть одного гостя: з п'ятьма іншими він або знайомий, або ні, тож у якійсь із двох скриньок щонайменше троє. Якщо він знає трьох, то або двоє з них знайомі між собою (і разом із ним це трійка знайомих), або всі троє незнайомі між собою. Якщо ж незнайомих з ним троє, міркування те саме навпаки. Для п'яти людей це вже не так: п'ятеро за круглим столом, кожен знає лише сусідів, не дають ні того, ні іншого.
  • Десять чисел у будь-якому порядкуЗапишіть 10 різних чисел у будь-якому порядку. Серед них завжди знайдуться 4, що йдуть у порядку зростання, або 4, що йдуть у порядку спадання (не обов'язково поспіль). Пал Ердеш і Дьєрдь Секереш довели це 1935 року, і загалом n² + 1 чисел завжди містять n + 1 таких. Дев'яти чисел мало: 7 8 9 4 5 6 1 2 3 не має ні того, ні іншого.

Звідки взялася назва

  • Волосся 1622 рокуНайдавніше відоме формулювання знайшли історики Бенуа Ріто і Альбрехт Геффер (The Mathematical Intelligencer, 2014): у латинській книжці єзуїта Жана Лерешона «Selectæ Propositiones» 1622 року сказано, що двоє людей неминуче мають однакову кількість волосин чи монет. Тобто приклад з волоссям старший за саму назву на два століття.
  • Шухляди ДіріхлеІм'я принципу дав німецький математик Петер Густав Лежен Діріхле, який 1834 року назвав його Schubfachprinzip, «принципом шухляд», і застосовував у теорії чисел, зокрема щоб доводити, що будь-яке число можна добре наблизити дробом.
  • Голуби тут ні до чогоАнглійська назва pigeonhole principle походить від pigeonholes — відкритих комірок письмового столу чи шафи для листів і паперів. Голуби в клітках, з якими принцип зазвичай малюють, з'явилися пізніше, коли первісне значення слова забулося.

Де це трапляється

Ще в темі «Ігри та логіка»

Усі терміни →