Калькулятор принципа Дирихле
Распределите n предметов по k ячейкам и узнайте, что гарантирует принцип Дирихле относительно самой заполненной ячейки.
At least this many items must share one box (ceil(10 / 3))
- 1
Items ÷ boxes
10 ÷ 3 = 3,3333The raw average — how many items each box would hold if distributed perfectly evenly. - 2
Guaranteed minimum in fullest box
⌈10 ÷ 3⌉ = 4
Как работает этот калькулятор?
Принцип Дирихле гарантирует, что при распределении n предметов по k ячейкам самая заполненная ячейка содержит не менее ceil(n / k) предметов. Чтобы гарантировать наличие m предметов в какой-либо ячейке, необходимо не менее k·(m − 1) + 1 предметов. Это гарантии для наихудшего случая, действительные при любом распределении.
Формула
How this is calculated
Введите n — количество предметов — и k — количество ячеек. При любом распределении самая заполненная ячейка обязательно содержит не менее ceil(n / k) предметов — таков принцип ящиков Дирихле. При равномерном распределении каждая ячейка вмещает floor(n / k) предметов, а оставшиеся n − k·floor(n / k) ячеек получают по одному дополнительному предмету — именно поэтому максимум округляется вверх.
Параметр m отвечает на обратный вопрос: сколько предметов нужно разместить, чтобы гарантировать m предметов хотя бы в одной ячейке. В наихудшем случае все ячейки заполняются m − 1 предметами, не достигая m, что суммарно даёт k·(m − 1); один дополнительный предмет, k·(m − 1) + 1, вынуждает m-й предмет попасть в какую-либо ячейку. Это минимальное число, которое гарантирует достижение целевого значения при любом распределении.
Все входные данные интерпретируются как неотрицательные целые числа и округляются вниз. Число ячеек k должно быть не менее 1 во избежание деления на ноль, а целевой параметр m — не менее 1 для определения принудительного числа. Результаты представляют собой гарантии для наихудшего случая, а не прогнозы типичного распределения.
Часто задаваемые вопросы
Если бы каждая ячейка содержала меньше ceil(n / k) предметов, их общее количество было бы меньше n — противоречие. Следовательно, хотя бы одна ячейка должна достигать округлённого вверх среднего.
Необходимо k·(m − 1) + 1. В наихудшем случае m − 1 предметов попадает в каждую ячейку, не достигая m; один дополнительный предмет вынуждает какую-либо ячейку достичь m.
Нет. Принцип Дирихле — это гарантия для наихудшего случая, которая действует при любом распределении независимо от способа размещения предметов.
Также известен как
TG we-Calculate Editorial Team. (2026). Калькулятор принципа Дирихле [Online calculator]. TG we-Calculate. https://we-calculate.com/ru/calculator/pigeonhole-principle-calculator
TG we-Calculate Editorial Team. "Калькулятор принципа Дирихле." TG we-Calculate. 2026. https://we-calculate.com/ru/calculator/pigeonhole-principle-calculator.
TG we-Calculate Editorial Team, "Калькулятор принципа Дирихле," TG we-Calculate, 2026. [Online]. Available: https://we-calculate.com/ru/calculator/pigeonhole-principle-calculator
@misc{wecalculate_pigeonhole_principle_calculator, title = {Калькулятор принципа Дирихле}, author = {{TG we-Calculate Editorial Team}}, howpublished = {\url{https://we-calculate.com/ru/calculator/pigeonhole-principle-calculator}}, year = {2026}, note = {TG we-Calculate} }
Этот калькулятор вам помог?