If $\sum_{i=1}^t(n_i-1)+1$ pigeons are distributed among $t$ pigeonholes, then there exists a pigeonhole that contains at least $n_i$ pigeons.

25 Views Asked by At

Full exercise description

$Proof$.
Suppose that for each $i$ the pigeonhole $h_i$ contains at most $n_i-1$ pigeons. Then the total number of pigeons at most is $(n_1-1)+(n_2-1)+\cdots+(n_t-1)=\sum_{i=1}^t\left(n_i-1\right)<\sum_{i=1}^t\left(n_i-1\right)+1$.

Is my proof valid? Also, someone told me that if proving by contrapositive or contradiction, it should be stated, is this true? I have never heard anyone else say that before.