Словник / Принцип Діріхле
Зазвичай, щоб сказати щось напевно про мільйони людей, їх треба порахувати або хоча б опитати вибірку, і тоді «напевно» перетворюється на «найімовірніше». Принцип Діріхле дає справжню гарантію без жодного підрахунку: якщо речей більше, ніж скриньок, у якійсь скриньці опиниться щонайменше дві. Звучить як дрібниця, яку знає кожна дитина. Проте з цієї дрібниці випливають твердження, які здаються неможливими: про волосся киян, шкарпетки в темряві й файли, які не стисне жоден архіватор.
Шар «На пальцях» приховано на всіх задачах.
У Києві близько трьох мільйонів мешканців. На голові в людини зазвичай 100–150 тисяч волосин, у когось більше, у когось менше, а в лисих нуль. Рахувати їх ніхто не збирається.
Чи можна, не порахувавши жодної волосини, стверджувати, що в Києві є двоє людей з рівно однаковою кількістю волосин на голові?
Гарантовано. Ба більше: однакову кількість волосин мають щонайменше троє киян.
Візьміть із величезним запасом: ні в кого немає мільйона волосин. Тоді можливих чисел рівно мільйон, від 0 до 999 999. Уявіть мільйон скриньок, підписаних цими числами, і кожен киянин стає у свою. Якби в кожній скриньці стояло щонайбільше двоє, у скриньки вмістилося б лише 2 000 000 людей. А киян 2 952 301 (оцінка міської статистики на 1 січня 2022 року). Отже, хоча б в одній скриньці щонайменше троє. Хто саме ці люди і скільки в них волосин, принцип не каже. Він каже лише, що вони існують.
Ось скриньки і на один предмет більше, ніж скриньок. Кладіть предмети по одному, натискаючи на скриньку, і намагайтеся, щоб жодні два не опинилися разом. Ви керуєте кожним кроком, і жодна випадковість вам не заважає.
Найхитріша стратегія лише відкладає збіг до останнього предмета, а скасувати його не може. Зверніть увагу й на кнопку «Покласти навмання»: коли предмети падають випадково, двоє в одній скриньці зазвичай опиняються набагато раніше. Гарантія і шанс — різні речі, і нижче ми їх порівняємо.
У шухляді впереміш 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 разів.
Різниця між стовпчиками й пунктиром — це різниця між двома питаннями. «Скільки треба, щоб збіг був неминучим?» розв'язує принцип Діріхле, і відповідь — завжди скриньки плюс один. «Скільки треба, щоб збіг був імовірним?» — питання теорії ймовірностей, і відповідь там набагато менша, бо пар, які можуть збігтися, стає дуже багато дуже швидко.
Шар «Глибше» приховано на всіх задачах.
У будь-якій компанії з двох і більше людей знайдуться двоє, що мають однакову кількість друзів у цій компанії. Це правда для будь-якої компанії: шкільного класу, відділу, гостей на весіллі. Скриньки — можливі кількості друзів. У компанії з n людей кожен може дружити з 0, 1, …, n − 1 іншими: n скриньок на n людей, начебто збігу може й не бути. Але скриньки 0 і n − 1 не можуть бути зайняті водночас: якщо хтось дружить з усіма, то ні в кого немає нуля друзів. Тож насправді скриньок n − 1, а людей n.
Варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші.
Знижка вигідна кав'ярні, хоч би що зробила сусідня, але коли знижують обидві, кожна заробляє втричі менше, ніж якби обидві тримали ціну.
Набір стратегій, у якому нікому не вигідно змінити свою, поки інші не змінюють своїх.
У дилемі в'язня обидва зраджують, хоча мовчати вигідніше обом: рівновага не означає найкращий результат.
Розв'язування гри з кінця: спершу останній хід, потім передостанній, і так до першого.
У грі-стоніжці логіка велить забрати копійки на першому ж ході, хоча, граючи довше, обидва отримали б сотні, і живі люди так майже не роблять.
Усі знають факт, усі знають, що всі знають, і так без кінця.
Два генерали можуть обмінятися тисячею підтверджень і все одно не мати спільного знання, тож жоден не наважиться атакувати першим.
Величина, яку не змінює жоден дозволений хід: якщо на старті й у цілі вона різна, мети не досягти.
З шахівниці вирізали два протилежні кути, і 31 доміно вже не накриє 62 клітинки, хоч як їх класти.