Парність і принцип Діріхле

Ідея: Плануйте найгірший випадок

Гарантія це число, що працює за найневдалішого порядку, а не за ймовірного.

• $n$ предметів у $k$ скриньках, $n>k$: десь лежить $2$
• Щоб змусити $m$ в одній скриньці, подолайте $m-1$ у кожній
• Поганий розподіл має бути можливим

Формула: Принцип Діріхле

$k(m-1)+1$

Скільки предметів змусять m в одній із k скриньок: заповніть кожну до m − 1, тоді візьміть ще 1.

Приклад: Краватки в темряві

У шухляді $8$ синіх, $6$ чорних і $5$ сірих краваток, світла немає. Скільки гарантують $2$ одного кольору?

1. Найгірше без пари: по одній краватці кожного кольору
2. Це $3$ краватки, тож $3+1=4$

Швидка перевірка: Коли кольору забракне

У торбі $2$ червоні й $9$ білих кульок. Скільки витягнути, щоб гарантувати $5$ одного кольору?

Типова помилка: Відповідати ймовірним випадком

«Зазвичай вистачає $3$ спроб» не є гарантією.

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

Ідея: Парність відкидає варіанти

Парність рідко дає відповідь, але одразу відкидає половину кандидатів.

• Кінь змінює колір клітинки на кожному ході
• Кожне рукостискання додає $1$ до $2$ лічильників, тож сума парна
• $9$ гостей не можуть потиснути по $3$ руки: $9\times 3=27$ непарне

Приклад: Задача про шафки

$100$ зачинених шафок. Для кожного $k$ від $1$ до $100$ учень перемикає кожну кратну $k$. Скільки відчинено наприкінці?

1. Шафку $n$ перемикають раз на кожен дільник $n$
2. Дільники йдуть парами $d$ і $\frac{n}{d}$: непарна кількість лише в квадратів
3. Квадрати до $100$, бо $10\times 10=100$: відчинено $10$

Швидка перевірка: 3 карти у 2 мастях

Скільки карт із колоди в $52$ карти гарантують по $3$ карти у $2$ різних мастях?

Ідея: Будуйте найгірший випадок уголос

Скажіть «я можу взяти стільки й не досягти мети», потім додайте $1$.

• Перевірте, що кожна скринька поганого розподілу має досить предметів
• Найгірший випадок змінює форму, коли змінюється ціль
• Для парності назвіть величину, чия парність незмінна