Почему нехватка ячеек гарантирует совпадение
Принцип Дирихле — простой способ доказать, что совпадение обязательно существует, даже если неизвестно, где именно. Если распределить людей по дням рождения и предположить, что в каждой из 365 ячеек сидит не больше одного человека, во всех ячейках вместе поместится не больше 365 человек. Для 366-го места уже нет: хотя бы одна ячейка должна принять второго.
Здесь важна не удача и не вероятность. Сколько бы ни менялся порядок рассадки, ограничение остаётся тем же: единственный способ избежать совпадений — использовать по одному человеку на ячейку, а ячеек меньше, чем людей.
Как этот приём работает за пределами календаря
Ячейками могут быть не только дни рождения. Например, если в коробке лежат носки нескольких цветов, а наугад достать больше носков, чем существует цветов, среди них непременно найдутся два одного цвета. Это не говорит, какие именно носки попадутся, — только доказывает, что совпадение неизбежно.
В информатике та же логика возникает, когда множество разных данных переводят в ограниченное число кодов или ячеек памяти. Несколько данных могут получить один и тот же код — возникает коллизия. Поэтому системы хранения и поиска должны уметь её обнаруживать и разбирать; само наличие коллизии ещё не означает, что данные потеряны.
Гарантия без прогноза
Принцип полезен именно тогда, когда точный результат неизвестен, но можно сравнить число объектов с числом доступных категорий. Он заменяет перебор всех вариантов коротким доказательством: если объектов больше, чем ячеек, где-то они неизбежно встретятся.
