Calcolatore del Principio dei Cassetti

Formula

How this is calculated

Inserisci n, il numero di elementi, e k, il numero di scatole. Per quanto abilmente distribuisci gli elementi, la scatola più piena deve contenere almeno ceil(n / k) elementi — questo è il principio dei cassetti (di Dirichlet). Se dividi in modo uniforme, ogni scatola contiene floor(n / k), e le restanti n − k·floor(n / k) scatole ricevono un elemento in più, che è esattamente il motivo per cui il massimo si arrotonda per eccesso.

L'input obiettivo m risponde alla domanda inversa: quanti elementi devi mettere prima che una scatola sia garantita contenerne almeno m. Il caso peggiore riempie ogni scatola con m − 1 elementi senza raggiungere m, per un totale di k·(m − 1); un elemento in più, k·(m − 1) + 1, forza l'm-esimo elemento in qualche scatola. Questo è il conteggio minimo che garantisce l'obiettivo indipendentemente dalla disposizione.

Tutti gli input sono trattati come interi non negativi e vengono troncati internamente, quindi le voci frazionarie sono arrotondate per difetto. Il numero di scatole k deve essere almeno 1 per evitare la divisione per zero, e l'obiettivo m deve essere almeno 1 perché il conteggio di forzatura sia definito. I risultati sono garanzie sul caso peggiore, non previsioni di una distribuzione tipica o casuale.