Question

Letbe positive integers. Show that if \({n_1} + {n_2} + \cdots + {n_t} - t + 1\) objects are placed into \(t\) boxes, then for some \(i,i = 1,2, \ldots ,t\), the \(i\)-th box contains at least \({n_i}\) objects.

Short answer

The resultant answer is the total no. of objects is at most \(\sum\limits_{i = 1}^t {\left( {{n_i} - } \right.} 1\)) \( < {n_1} + {n_2} + \ldots + {n_t} - t + 1\), a contradiction.

Step-by-step solution

Given data

The given data is \({n_1},{n_2}, \ldots ,{n_t}\)which is a positive integer.

Concept of Pigeonhole principle

If the number of pigeons exceeds the number of pigeonholes, at least one hole will hold at least two pigeons, according to the pigeon hole principle.

Contradict and simplify the expression

Suppose the \(i\)-th box contains less than \({n_i}\) objects \(\forall i = 1,2, \ldots ,t\). Thus, the total no. of objects is at most \(\sum\limits_{i = 1}^t {\left( {{n_i} - } \right.} 1\)) \( < {n_1} + {n_2} + \ldots + {n_t} - t + 1\), a contradiction.